stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*

 * 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;

}

// Faster C++ solution for the same problem (measured speedup: 5.114653673194317x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.169955192549341x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.018286952619453x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.3455133725594735x):
#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;

}
// Slower C++ solution:
#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; 

}

  


// Faster C++ solution for the same problem (measured speedup: 1.7260797519782098x):
#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; 

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.8218546187040738x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.8218546187040738x):
#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++) {



			bool m_ok = (lun[st] % 10 != 0);

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

			idx += m_ok;



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



			bool p_ok = (lun[st] % 10 != 9);

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

			idx += p_ok;



		}



	}



};



solve<100000> S;



int main() {



	int N;

	scanf("%d", &N);

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



	return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.1355094414045765x):
#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; }



int main() {

    int k;

    cin >> k;

    queue<long long> que;

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

    

    long long val;

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

        val = que.front();

        que.pop();

        int n = val % 10;

        if (n > 0) que.emplace(val * 10 + n - 1);

        que.emplace(val * 10 + n);

        if (n < 9) que.emplace(val * 10 + n + 1);

    }

    cout << val << endl;

    return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.1481402808067893x):
#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;

}
// Slower C++ solution:
#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]);

}


// Faster C++ solution for the same problem (measured speedup: 1.4097963300987775x):
#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;

}
// Slower C++ solution:
#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<map>

#include<stack>

#include<set>

#include<vector>

#include<functional>

using namespace std;

typedef long long LL;

inline LL read()

{

	LL kk=0,f=1;

	char cc=getchar();

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

	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}

	return kk*f;

}

LL cou=0,asd=0,len,k;

void dfs(LL now,int de)

{

	if(de==len)

	{

		cou++;

		if(cou==k)asd=now;

		return;

	}

	LL per=now%10;

	for(LL i=max(0ll,per-1);i<=min(9ll,per+1);++i)

	{

		dfs(now*10+i,de+1);

	}

}

int main()

{

	k=read();

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

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

	{

		len=i;

		dfs(j,1);

		if(cou>k)break;

	}

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

}

// Faster C++ solution for the same problem (measured speedup: 1.1359655099365018x):
#include<bits/stdc++.h>

using namespace std;

int k,tot;

void dfs(int x,long long s,int f){

	if(x==1){

		tot++;

		if(tot==k){

			cout<<s;

			exit(0);

		}

		return;

	}

	if(f>0){

		dfs(x-1,s*10+f-1,f-1);

	}

	dfs(x-1,s*10+f,f);

	if(f<9){

		dfs(x-1,s*10+f+1,f+1);

	}

}

int main(){

	cin>>k;

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

		for(long long j=1;j<=9;j++){

			dfs(i,j,j);

		}

	}

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<map>

#include<stack>

#include<set>

#include<vector>

#include<functional>

using namespace std;

typedef long long LL;

inline LL read()

{

	LL kk=0,f=1;

	char cc=getchar();

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

	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}

	return kk*f;

}

LL cou=0,asd=0,len,k;

void dfs(LL now,int de)

{

	if(de==len)

	{

		cou++;

		if(cou==k)asd=now;

		return;

	}

	LL per=now%10;

	for(LL i=max(0ll,per-1);i<=min(9ll,per+1);++i)

	{

		dfs(now*10+i,de+1);

	}

}

int main()

{

	k=read();

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

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

	{

		len=i;

		dfs(j,1);

		if(cou>k)break;

	}

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

}

// Faster C++ solution for the same problem (measured speedup: 1.1339199460540101x):
#include<bits/stdc++.h>

using namespace std;

long long a[100009];

int k;

int main(){

    cin>>k;

    int i;

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

        a[i]=i;

    }

    int temp=1;

    while(k>=i){

        if(a[temp]%10==0){

            a[i++]= a[temp]*10;

            a[i++]= a[temp]*10+1; 

        }

        else if(a[temp]%10==9){

            a[i++]=a[temp]*10+8;

            a[i++]=a[temp]*10+9;

        }

        else{

            a[i++]=a[temp]*10+a[temp]%10-1;

            a[i++]=a[temp]*10+a[temp]%10;

            a[i++]=a[temp]*10+a[temp]%10+1;

        }

        temp++;

    }

    cout<<a[k];

}
// Slower C++ solution:
#include<cstdio>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<map>

#include<stack>

#include<set>

#include<vector>

#include<functional>

using namespace std;

typedef long long LL;

inline LL read()

{

	LL kk=0,f=1;

	char cc=getchar();

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

	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}

	return kk*f;

}

LL cou=0,asd=0,len,k;

void dfs(LL now,int de)

{

	if(de==len)

	{

		cou++;

		if(cou==k)asd=now;

		return;

	}

	LL per=now%10;

	for(LL i=max(0ll,per-1);i<=min(9ll,per+1);++i)

	{

		dfs(now*10+i,de+1);

	}

}

int main()

{

	k=read();

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

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

	{

		len=i;

		dfs(j,1);

		if(cou>k)break;

	}

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

}

// Faster C++ solution for the same problem (measured speedup: 1.092613719686349x):
#include<bits/stdc++.h>

using namespace std;

queue<long long>q;

int k;

int tot=0;

int main()

{

	cin>>k;

	q.push(1);

	q.push(2);

	q.push(3);

	q.push(4);

	q.push(5);

	q.push(6);

	q.push(7);

	q.push(8);

	q.push(9);

	while(!q.empty())

	{

		long long  x=q.front();

		q.pop();

		//cout<<x<<endl;

		tot++;

		if(tot==k)

		  {

		  	cout<<x<<endl;

		  	return 0;

		  }

	 if(x%10==0)

	   {

	   	   q.push(x*10);

	   	   q.push(x*10+1);

	   }

	else if(x%10==9)

	  {

	  	q.push(x*10+8);

	  	q.push(x*10+9);

	  }

	else 

	  {

	  	q.push(x*10+x%10-1);

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

	  	q.push(x*10+x%10+1);

	  }

	}

	

}