宽搜

#include"bits/stdc++.h"
using namespace std;
#define BT long long
BT k,j,a[5]={0,1,4,9};
queue<BT>sb;
main(){
	cin>>k;
	for(BT i=1;i<4;++i)sb.push(a[i]);
	if(k<4){cout<<a[k];return 0;}k-=3;
	while(1){
		j=sb.front();
		sb.pop();
		for(BT SB=0;SB<4;++SB)if(j*10+a[SB]){
			sb.push(j*10+a[SB]);k--;
			if(k==0){
				cout<<j*10+a[SB];return 0;
			}
		}
	}
}