Space Elevator

#include <bits/stdc++.h>
using namespace std;

typedef long long int i64;
typedef pair<int, int> ii;
typedef pair<i64, i64> ll;
typedef vector<int> vi;
typedef vector<i64> vi64;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<vi> vvi;

const double eps = 1e-9;

#define eq(a, b) (abs(a - b) < eps)
#define lt(a, b) ((a + eps) < b)
#define gt(a, b) (a > (b + eps))
#define le(a, b) (a < (b + eps))
#define ge(a, b) ((a + eps) > b)

#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ms(a, x) memset(a, x, sizeof(a))
#define len(x) (x).size()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

const int dtx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
const int dty[] = {-1, 1,  0, 0, 1, -1, -1,  1};
const int dtxc[] = {1,  1, 2,  2, -1, -1, -2, -2};
const int dtyc[] = {2, -2, 1, -1,  2, -2,  1, -1};

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+5;
const int mod = 1e9+7;

string s;

i64 timer;
i64 seen[20][2][2][11];
i64 dp[20][2][2][11];

i64 solve(int idx = 0, int can = 0, int put = 0, int last = 0) {
    if (idx == (int)s.size()) return put;
    if (seen[idx][can][put][last] == timer) return dp[idx][can][put][last];
    seen[idx][can][put][last] = timer;
    i64 ans = 0LL;
    int mx = (can ? 9 : s[idx]-'0');
    if (!put or !idx) {
        for (int i = 0; i <= mx; ++i) {
            if (i == 4) continue;
            ans += solve(idx + 1, can | (i != mx), (i != 0), i);
        }
    } else {
        for (int i = 0; i <= mx; ++i) {
            if (i == 4 or (last == 1 and i == 3)) continue;
            ans += solve(idx + 1, can | (i != mx), 1, i);
        }
    }
    return dp[idx][can][put][last] = ans;
}

unsigned long long int top, lo, hi, best, ans;

int main() {
    fastIO();
    while (cin >> top) {
        lo = 0LL;
        hi = 1e19;
        while (lo <= hi) {
            best = lo + (hi - lo)/2LL;
            ++timer;
            s = to_string(best);
            if (solve() >= top) {
                ans = best;
                hi = best - 1LL;
            } else {
                lo = best + 1LL;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}