stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

const int inf = 1<<16;

int N,x,y,z,need[100010],tot[20],ans,md[inf],all;

bool vis[inf];

int read()

{

	static int x;

	static char ch;

	x = 0;

	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());

	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';

	return x;

}

int length(int x)

{

	int len = 0; 

	while (x)

	{

		len += x & 1;

		x >>= 1;

	}

	return len;

}

int find(int now)

{

	if (!now) return 0;

	if (vis[now]) return md[now];

	vis[now] = true;

	int ret = 20,next;

	for (int i = 1;i<=15;++i)

	 if ((now >> i) & 1)

	  for (int j = 1;j<=15;++j)

	   if ((i!=j) && ((now>>j)&1))

	     {

	     	next = now ^ (1<<i) ^ (1<<j) ^ (1<<(i ^ j));

	     	if (length(next) < length(now)) ret = min(ret , find(next) + 1 + (~next >> (i ^ j) & 1));

		 }

	 return md[now] = ret;	

}

int main()

{

	N = read();

	for (int i = 1;i<N;++i)

	{

		x = read() + 1;

		y = read() + 1;

		z = read();

		need[x]^=z;need[y]^=z;

	}

	ans = 0;

	for (int i = 1;i<=N;++i) tot[need[i]]++;

	for (int i = 1;i<=15;++i) ans += tot[i] >> 1,all |= (tot[i] & 1) << i;

	ans += find(all);

	printf("%d\n",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5, MAXS = ( 1 << 16 ) + 5;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



template<typename _T>

_T MIN( const _T a, const _T b )

{

	return a < b ? a : b;

}



int f[MAXS];

int w[MAXN];

int N, cnt;

bool vis[MAXS];



bool chk( const int S, const int b ) { return S >> b & 1; }



int DFS( const int S )

{

	if( ! S ) return f[S] = 0;

	if( vis[S] ) return f[S];

	vis[S] = true;

	for( int i = 1 ; i <= 15 ; i ++ )

		for( int j = i + 1 ; j <= 15 ; j ++ )

			if( chk( S, i - 1 ) && chk( S, j - 1 ) )

			{

				int t = S ^ ( 1 << i - 1 ) ^ ( 1 << j - 1 );

				int v = i ^ j, nxt = t ^ ( 1 << v - 1 );

				f[S] = MIN( f[S], DFS( nxt ) + 1 + chk( t, v - 1 ) );

			}

	return f[S];

}



int main()

{

	read( N );

	for( int i = 1, x, y, b ; i < N ; i ++ )

		read( x ), read( y ), read( b ),

		w[x + 1] ^= b, w[y + 1] ^= b;

	int sta = 0, tot = 0;

	for( int i = 1 ; i <= N ; i ++ )

		if( w[i] )

			tot += ( sta >> w[i] - 1 ) & 1, 

			sta ^= 1 << w[i] - 1;

	memset( f, 0x3f, sizeof f );

	write( DFS( sta ) + tot ), putchar( '\n' ); 

	return 0;

}

/*

3

0 1 1

0 2 1

*/

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#include<iostream>

using namespace std;

#define clr(a,b) memset(a,b,sizeof a)

#define PII pair<int,int>

#define PI acos(-1.0)

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

typedef long long ll;

typedef unsigned long long ull;

const int INF=0x3f3f3f3f;

const int maxn=1e5+10;

int dp[1<<16],V[maxn],cnt[16];

int n,x,y,a;



int Work(int S)

{

    if(S==0) return 0;

    if(dp[S]!=-1) return dp[S];

    dp[S]=INF;

    for(int i=1;i<16;i++)

    {

    	if(S&(1<<i))

            for(int j=1;j<16;j++)

            {

            	

            	if(S&(1<<j))

                {

                    int cs=S^(1<<i)^(1<<j)^(1<<(i^j));

                    if(i!=j)

					{

						if(((1<<(i^j)) & S) == (1<<(i^j))) dp[S]=min(dp[S], Work(cs) + 2);

						else dp[S]=min(dp[S], Work(cs) + 1 ); 

					}

                }

			}

	}

    return dp[S];

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<n;i++)

    {

        scanf("%d%d%d",&x,&y,&a);

        V[x]^=a; V[y]^=a;

    }

    for(int i=0;i<n;i++) if(V[i]) cnt[V[i]]++;

    int ans=0,s=0;

    for(int i=0;i<16;i++) ans += cnt[i]/2, s^=(cnt[i]&1)<<i;

    memset(dp,-1,sizeof dp);

    ans+=Work(s);

    printf("%d\n",ans);

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5, MAXS = ( 1 << 16 ) + 5;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



template<typename _T>

_T MIN( const _T a, const _T b )

{

	return a < b ? a : b;

}



int f[MAXS];

int w[MAXN];

int N, cnt;

bool vis[MAXS];



bool chk( const int S, const int b ) { return S >> b & 1; }



int DFS( const int S )

{

	if( ! S ) return f[S] = 0;

	if( vis[S] ) return f[S];

	vis[S] = true;

	for( int i = 1 ; i <= 15 ; i ++ )

		for( int j = i + 1 ; j <= 15 ; j ++ )

			if( chk( S, i - 1 ) && chk( S, j - 1 ) )

			{

				int t = S ^ ( 1 << i - 1 ) ^ ( 1 << j - 1 );

				int v = i ^ j, nxt = t ^ ( 1 << v - 1 );

				f[S] = MIN( f[S], DFS( nxt ) + 1 + chk( t, v - 1 ) );

			}

	return f[S];

}



int main()

{

	read( N );

	for( int i = 1, x, y, b ; i < N ; i ++ )

		read( x ), read( y ), read( b ),

		w[x + 1] ^= b, w[y + 1] ^= b;

	int sta = 0, tot = 0;

	for( int i = 1 ; i <= N ; i ++ )

		if( w[i] )

			tot += ( sta >> w[i] - 1 ) & 1, 

			sta ^= 1 << w[i] - 1;

	memset( f, 0x3f, sizeof f );

	write( DFS( sta ) + tot ), putchar( '\n' ); 

	return 0;

}

/*

3

0 1 1

0 2 1

*/

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define N 100005

#define M 65540

using namespace std;

int n,s[N],S,ans,f[M],inf,sum[20];



int dfs(int S)

{

  if(!S)return 0; 

  if(f[S]<inf)return f[S];

  for(int i=0;i<16;i++)if((S>>i)&1)

    for(int j=0;j<16;j++)if(i!=j&&(S>>j)&1)

    {

      int p=i^j,x=S^(1<<i)^(1<<j)^(1<<p);

      if(S>>p&1)f[S]=min(f[S],dfs(x)+2);

      else f[S]=min(f[S],dfs(x)+1);

      //枚举每次异或的两个节点i,j,i异或掉j,j异或掉j,还剩下p=i^j

      //如果p本身存在那两个p直接消掉 

    }

  return f[S];

}



int main()

{

  int a,b,c;

  scanf("%d",&n);

  for(int i=1;i<n;i++)

    scanf("%d%d%d",&a,&b,&c),s[a]^=c,s[b]^=c;

  for(int i=0;i<n;i++)sum[s[i]]++;

  for(int i=1;i<16;i++)

    ans+=(sum[i]>>1),S+=(1<<i)*(sum[i]&1);

  memset(f,127,sizeof(f));inf=f[0];

  printf("%d\n",ans+dfs(S));

  return 0;

} 

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5, MAXS = ( 1 << 16 ) + 5;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



template<typename _T>

_T MIN( const _T a, const _T b )

{

	return a < b ? a : b;

}



int f[MAXS];

int w[MAXN];

int N, cnt;

bool vis[MAXS];



bool chk( const int S, const int b ) { return S >> b & 1; }



int DFS( const int S )

{

	if( ! S ) return f[S] = 0;

	if( vis[S] ) return f[S];

	vis[S] = true;

	for( int i = 1 ; i <= 15 ; i ++ )

		for( int j = i + 1 ; j <= 15 ; j ++ )

			if( chk( S, i - 1 ) && chk( S, j - 1 ) )

			{

				int t = S ^ ( 1 << i - 1 ) ^ ( 1 << j - 1 );

				int v = i ^ j, nxt = t ^ ( 1 << v - 1 );

				f[S] = MIN( f[S], DFS( nxt ) + 1 + chk( t, v - 1 ) );

			}

	return f[S];

}



int main()

{

	read( N );

	for( int i = 1, x, y, b ; i < N ; i ++ )

		read( x ), read( y ), read( b ),

		w[x + 1] ^= b, w[y + 1] ^= b;

	int sta = 0, tot = 0;

	for( int i = 1 ; i <= N ; i ++ )

		if( w[i] )

			tot += ( sta >> w[i] - 1 ) & 1, 

			sta ^= 1 << w[i] - 1;

	memset( f, 0x3f, sizeof f );

	write( DFS( sta ) + tot ), putchar( '\n' ); 

	return 0;

}

/*

3

0 1 1

0 2 1

*/

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



typedef long long ll;



int cnt = 0, len, k;

ll ans;



void dfs(int x, ll i) {

    if (len == x) {

        cnt++;

        if (cnt == k) {

            ans = i;

        }

        i /= 10;

        return;

    }

    ll u = i % 10;

    for (ll j = u - 1; j <= u + 1; j++) {

        if (j < 0 || j > 9)

            continue;

        else {

            len++;

            dfs(x, i * 10 + j);

            len--;

        }

    }

}



int main(int argc, const char* argv[]) {

    cin >> k;

    for (int j = 1; j <= 10; j++) {

        for (ll i = 1; i <= 9; i++) {

            len = 1;

            dfs(j, i);

        }

    }

    cout << ans << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[100010]={0,1,2,3,4,5,6,7,8,9}; 

int main()

{

	int k,id=1;scanf("%d",&k);

	for(int i=10; i<=k; )

	{

		ll x=a[id]*10,y=a[id++]%10;

		if(y==0)

		{

			a[i++]=x;

			a[i++]=x+1;

		}

		else if(y==9)

		{

			a[i++]=x+8;

			a[i++]=x+9;

		}

		else

		{

			a[i++]=x+y-1;

			a[i++]=x+y;

			a[i++]=x+y+1;

		}

	}

	printf("%lld\n",a[k]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

 * Author:  heyuhhh

 * Created Time:  2020/5/13 18:09:49

 */

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <iomanip>

#include <assert.h>

#define MP make_pair

#define fi first

#define se second

#define pb push_back

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

#define Local

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << std::endl; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

  template <template<typename...> class T, typename t, typename... A> 

  void err(const T <t> &arg, const A&... args) {

  for (auto &v : arg) std::cout << v << ' '; err(args...); }

#else

  #define dbg(...)

#endif

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 11;



ll f[N][N], g[N];



void run() {

    int k; cin >> k;

    for (int i = 0; i < 10; i++) f[i][1] = 1;

    for (int t = 2; t < N; t++) {

        for (int i = 0; i < 10; i++) {

            for (int j = max(i - 1, 0); j <= min(i + 1, 9); j++) {

                f[i][t] += f[j][t - 1];

            }

        }

    }

    for (int t = 1; t < N; t++) {

        for (int i = 1; i < 10; i++) {

            g[t] += f[i][t];

        }

    }

    int t;

    for (t = 1; t < N; t++) {

        if (g[t] < k) k -= g[t];

        else break;

    }

    ll x = 0;

    int last = -1;

    for (int i = t; i >= 1; i--) {

        if (last != -1) {

            for (int j = max(last - 1, 0); j <= min(last + 1, 9); j++) {

                if (f[j][i] < k) k -= f[j][i];

                else {

                    last = j;

                    x = x * 10 + j;

                    break;

                }

            }

        } else for (int j = 1; j < 10; j++) {

            if (f[j][i] < k) k -= f[j][i];

            else {

                last = j;

                x = x * 10 + j;

                break;

            }

        }

    }

    cout << x << '\n';

}



int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    run();

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

long long a[100010]={0,1,2,3,4,5,6,7,8,9}; 

int main()

{

	int k,id=1;scanf("%d",&k);

	for(int i=10; i<=k; )

	{

		long long x=a[id]*10,y=a[id++]%10;

		if(y==0) a[i++]=x,a[i++]=x+1;

		else if(y==9) a[i++]=x+8,a[i++]=x+9;

		else a[i++]=x+y-1,a[i++]=x+y,a[i++]=x+y+1;

	}

	printf("%lld\n",a[k]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,tot;

queue<ll>q;

int main()

{

	scanf("%lld",&n);

	for(ll i=1;i<=9;i++)q.push(i);

	while(!q.empty())

	{

		ll tx=q.front(); q.pop();

		if(++tot==n)

		{

			printf("%lld\n",tx);

			exit(0);

		}

		if(tx%10>0)q.push(tx*10+tx%10-1);

		q.push(tx*10+tx%10);

		if(tx%10<9)q.push(tx*10+tx%10+1);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

long long a[100010]={0,1,2,3,4,5,6,7,8,9}; 

int main()

{

	int k,id=1;scanf("%d",&k);

	for(int i=10; i<=k; )

	{

		long long x=a[id]*10,y=a[id++]%10;

		if(y==0) a[i++]=x,a[i++]=x+1;

		else if(y==9) a[i++]=x+8,a[i++]=x+9;

		else a[i++]=x+y-1,a[i++]=x+y,a[i++]=x+y+1;

	}

	printf("%lld\n",a[k]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define me memset

const int N=1e6+10;

const int mod=1e9+7;

using namespace std;

int k;

long long q[N],hh=1,tt=0;

int main(){

	scanf("%d",&k);

	if(k<=12){

		printf("%d\n",k);

		return 0;

	}

	for(int i=1;i<=9;++i) q[++tt]=i;

	int cnt=0;

	long long ans;

	while(cnt!=k){

		long long now=q[hh];

		hh++;

		long long res=now%10;

		if(res!=0)q[++tt]=now*10+res-1,cnt++;

		if(cnt==k-10+1){

		   ans=q[tt];

		   break;

		}

		q[++tt]=now*10+res,cnt++;

		if(cnt==k-10+1){

			ans=q[tt];

			break;

		}

		if(res!=9)q[++tt]=now*10+res+1,cnt++;

		if(cnt==k-10+1){

			ans=q[tt];

			break;

		}

	}

	printf("%lld\n",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

long long a[100010]={0,1,2,3,4,5,6,7,8,9}; 

int main()

{

	int k,id=1;scanf("%d",&k);

	for(int i=10; i<=k; )

	{

		long long x=a[id]*10,y=a[id++]%10;

		if(y==0) a[i++]=x,a[i++]=x+1;

		else if(y==9) a[i++]=x+8,a[i++]=x+9;

		else a[i++]=x+y-1,a[i++]=x+y,a[i++]=x+y+1;

	}

	printf("%lld\n",a[k]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n,t=0;

void dfs(int k,int end,string s)

{

    if(k>end)

        if(++t==n)

        {

            cout<<s;

            exit(0);

        }

        else return ;

    for(char ch=s[s.size()-1]-1;ch<=s[s.size()-1]+1;ch++)

        if(ch>='0'&&ch<='9')

            dfs(k+1,end,s+ch);

}

int main()

{

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=1;;i++)

		for(char c='1';c<='9';c++)

		{

			string s="";

			dfs(2,i,s+c);

		}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

long long a[100010]={0,1,2,3,4,5,6,7,8,9}; 

int main()

{

	int k,id=1;scanf("%d",&k);

	for(int i=10; i<=k; )

	{

		long long x=a[id]*10,y=a[id++]%10;

		if(y==0) a[i++]=x,a[i++]=x+1;

		else if(y==9) a[i++]=x+8,a[i++]=x+9;

		else a[i++]=x+y-1,a[i++]=x+y,a[i++]=x+y+1;

	}

	printf("%lld\n",a[k]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstring>

using namespace std;

int main(){

  int k; cin >> k;

  char *n = new char[11*100010]; memset(n,0,11*100010);

  for(int i=0;i<9;i++) n[i*11]='1'+i;

  int ps=0; int pe=9; int cr=1;

  do {

    int pc=pe;

    for(int p=ps;p<pe;p++){

      if( n[p*11+cr-1] == '0' ){

        for(int r=0;r<cr;r++){ n[pc*11+r]=n[p*11+r]; } n[pc*11+cr] = '0'; pc++;

        for(int r=0;r<cr;r++){ n[pc*11+r]=n[p*11+r]; } n[pc*11+cr] = '1'; pc++;

      }else if( n[p*11+cr-1] == '9' ){

        for(int r=0;r<cr;r++){ n[pc*11+r]=n[p*11+r]; } n[pc*11+cr] = '8'; pc++; 

        for(int r=0;r<cr;r++){ n[pc*11+r]=n[p*11+r]; } n[pc*11+cr] = '9'; pc++; 

      }else{

        for(int r=0;r<cr;r++){ n[pc*11+r]=n[p*11+r]; } n[pc*11+cr] = n[p*11+cr-1]-1; pc++; 

        for(int r=0;r<cr;r++){ n[pc*11+r]=n[p*11+r]; } n[pc*11+cr] = n[p*11+cr-1]; pc++; 

        for(int r=0;r<cr;r++){ n[pc*11+r]=n[p*11+r]; } n[pc*11+cr] = n[p*11+cr-1]+1; pc++; 

      }

      if( pc >= 100000 ) goto finish;

    }

    cr++;

    ps=pe;

    pe=pc;

  } while( true );

  finish:

  printf("%s\n",&n[(k-1)*11]);

  return 0; 

}

  


// Optimized solution to the same problem (faster):
#include<iostream>

#include<cstring>

using namespace std;

int main(){

  int k; cin >> k;

  char *n = new char[11*100010]; memset(n,0,11*100010);

  for(int i=0;i<9;i++) n[i*11]='1'+i;

  int ps=0; int pe=9; int cr=1;

  do {

    int pc=pe;

    for(int p=ps;p<pe;p++){

      if( n[p*11+cr-1] == '0' ){

        memcpy(&n[pc*11],&n[p*11],cr); n[pc*11+cr] = '0'; pc++;

        memcpy(&n[pc*11],&n[p*11],cr); n[pc*11+cr] = '1'; pc++;

      }else if( n[p*11+cr-1] == '9' ){

        memcpy(&n[pc*11],&n[p*11],cr); n[pc*11+cr] = '8'; pc++;

        memcpy(&n[pc*11],&n[p*11],cr); n[pc*11+cr] = '9'; pc++;

      }else{

        memcpy(&n[pc*11],&n[p*11],cr); n[pc*11+cr] = n[p*11+cr-1]-1; pc++;

        memcpy(&n[pc*11],&n[p*11],cr); n[pc*11+cr] = n[p*11+cr-1]; pc++;

        memcpy(&n[pc*11],&n[p*11],cr); n[pc*11+cr] = n[p*11+cr-1]+1; pc++;

      }

      if( pc >= k ) goto finish;

    }

    cr++;

    ps=pe;

    pe=pc;

  } while( true );

  finish:

  printf("%s\n",&n[(k-1)*11]);

  return 0; 

}

  


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cassert>

#include <cstdio>

#include <cmath>

#include <iostream>

#include <iomanip>

#include <sstream>

#include <vector>

#include <map>

#include <queue>

#include <numeric>

#include <algorithm>



using namespace std;

using lint = long long;

constexpr int MOD = 1000000007, INF = 1111111111;

constexpr lint LINF = 1LL << 60;



template <class T>

ostream &operator<<(ostream &os, const vector<T> &vec) {

	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");

	return os;

}



#ifdef _DEBUG

template <class T>

void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };

template <class Head, class... Tail>

void dump(const char* str, Head &&h, Tail &&... t) {

	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";

	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);

}

#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)

#else 

#define DMP(...) ((void)0)

#endif

template<size_t N> struct solve {



	lint ans[N];



	constexpr solve() {



		for (int i = 1; i <= 9; i++) {

			ans[i] = i;

		}

		int st = 1, idx = 10;

		while (idx <= N) {



			if (ans[st] % 10 != 0) {

				ans[idx++] = ans[st] * 10 + ans[st] % 10 - 1;

			}

			ans[idx++] = ans[st] * 10 + ans[st] % 10;

			if (ans[st] % 10 != 9) {

				ans[idx++] = ans[st] * 10 + ans[st] % 10 + 1;

			}

			st++;



		}



	}



};



solve<100000> S;



int main() {



	int N;

	scanf("%d", &N);

	printf("%lld", S.ans[N]);



	return 0;

}

// Optimized solution to the same problem (faster):
#include <cassert>

#include <cstdio>

#include <cmath>

#include <iostream>

#include <iomanip>

#include <sstream>

#include <vector>

#include <map>

#include <queue>

#include <numeric>

#include <algorithm>



using namespace std;

using lint = long long;

constexpr int MOD = 1000000007, INF = 1111111111;

constexpr lint LINF = 1LL << 60;



template <class T>

ostream &operator<<(ostream &os, const vector<T> &vec) {

	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");

	return os;

}



#ifdef _DEBUG

template <class T>

void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };

template <class Head, class... Tail>

void dump(const char* str, Head &&h, Tail &&... t) {

	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";

	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);

}

#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)

#else 

#define DMP(...) ((void)0)

#endif



template<size_t N> struct solve {



	lint lun[N + 5];



	constexpr solve() : lun() {



		for (int i = 1; i <= 9; i++) lun[i] = i;



		for (int st = 1, idx = 10; idx <= N; st++) {



			if (lun[st] % 10 != 0) lun[idx++] = lun[st] * 10 + lun[st] % 10 - 1;

			lun[idx++] = lun[st] * 10 + lun[st] % 10;

			if (lun[st] % 10 != 9) lun[idx++] = lun[st] * 10 + lun[st] % 10 + 1;

			

		}



	}



};



solve<100000> S;



int main() {



	int N;

	scanf("%d", &N);

	printf("%lld", S.lun[N]);



	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

template<class T, class U> inline bool chmax(T& a,U b) { if (a < b) { a = b; return 1; } return 0; }

template<class T, class U> inline bool chmin(T& a,U b) { if (a > b) { a = b; return 1; } return 0; }

constexpr int ten = 10;



int main() {

    int k;

    cin >> k;

    

    vector<long long> ans, buff;

    

    for (int i = 1; i < 10; i++) buff.emplace_back(i);

    while (ans.size() < k) {

        vector<long long> next;

        for (const auto &e : buff) {

            long long n = e;

            long long c = n % ten;

            if (c != 0) next.emplace_back(n * ten + c - 1);

            next.emplace_back(n * ten + c);

            if (c != 9) next.emplace_back(n * ten + c + 1);

        }

        for (const auto &e : buff) ans.emplace_back(e);

        swap(buff, next);

    }

    

    sort(ans.begin(), ans.end());

    cout << ans[k-1] << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main() {

    int k;

    cin >> k;

    

    queue<long long> que;

    for (long long i = 1; i < 10; i++) que.emplace(i);

    

    for (int _ = 0; _ < k - 1; _++) {

        long long res = que.front();

        que.pop();

        long long d = res % 10;

        if (d != 0) que.emplace(res * 10 + (d - 1));

        que.emplace(res * 10 + d);

        if (d != 9) que.emplace(res * 10 + (d + 1));

    }

    

    cout << que.front() << '\n';

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <stdio.h>



int x[110],res[110];

int a;

void solve(int k, int value, int &sum){

	 x[k] = value;

	if(k==1){

		sum++;

		if(sum==a){

            for(int i=1;i<=10;i++)

                 res[i] = x[i];

		}

		return;

	}



	if(value>=1) solve(k-1,value-1,sum);



	solve(k-1,value,sum);



	if(value<=8) solve(k-1,value+1,sum);



}

int main(){

	scanf("%d",&a);



	int sum = 0;

	for(int i=1;i<=10;i++)

		for(int j=1;j<=9;j++)

			solve(i,j,sum);



	int p = 0;

	for(int i=10;i>=1;i--)

		if(res[i]!=0){

			p = i;

			break;

		}

	for(int i=p;i>=1;i--)

          printf("%d",res[i]);

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define LL long long

using namespace std;



LL k,maxx=9;



void bfs(){

	queue<pair<LL,LL> > q;

	q.push(make_pair(1ll,1ll));

	q.push(make_pair(2ll,2ll));

	q.push(make_pair(3ll,3ll));

    q.push(make_pair(4ll,4ll));

    q.push(make_pair(5ll,5ll));

    q.push(make_pair(6ll,6ll));

    q.push(make_pair(7ll,7ll));

    q.push(make_pair(8ll,8ll));

    q.push(make_pair(9ll,9ll));

    while(!q.empty()){

    	LL djl=q.front().first;

		LL nums=q.front().second;

    	q.pop();

    	if (nums==k){

    		cout<<djl<<endl;

    		exit(0);

		}

    	if ((djl%10)-1>-1){

    		maxx++;

			q.push(make_pair(djl*10+(djl%10)-1,maxx));

		} 

    	maxx++;

		q.push(make_pair(djl*10+(djl%10),maxx));

		if ((djl%10)+1<10){

    		maxx++;

			q.push(make_pair(djl*10+(djl%10)+1,maxx));

		} 

	}

}



int main()

{

	ios::sync_with_stdio(false);

	cin>>k;

	bfs();

	return 0;

} 

// Fastest known solution for this problem: