fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. string str ;
  6. string tmp = "";
  7.  
  8. int dp[20][10][2][2][2];
  9. int f(int pos, int last, bool flag, bool valid,bool dup)
  10. {
  11.     if(pos == str.size())
  12.     {
  13.         return dup;
  14.     }
  15.  
  16.     int &d = dp[pos][last][flag][valid][dup];
  17.     if(d != -1) return d;
  18.  
  19.     int lim = 9;
  20.     if(flag==false) lim = str[pos]-'0';
  21.     int res = 0;
  22.  
  23.     for(int i = 0; i <= lim; i++)
  24.     {
  25.         if(valid)
  26.         {
  27.             if((last == i))
  28.             {
  29.                 res += f(pos+1,i,((i < lim) | flag),true,true);
  30.             }else 
  31.             {
  32.                 res += f(pos+1,i,((i < lim) | flag),true,dup);
  33.             }
  34.         }else 
  35.         {
  36.             if(i)
  37.             {
  38.                 res += f(pos+1,i,((i < lim) | flag), true,dup);
  39.             }else 
  40.             {
  41.                 res += f(pos+1,i,((i < lim) | flag),false,dup);
  42.             }
  43.         }
  44.     }
  45.     return d = res;
  46. }
  47.  
  48. void solve()
  49. {
  50.     int n;
  51.     cin >> n;
  52.  
  53.     int l = 1; int r = 1e18;
  54.     int ans = 0;
  55.     while(l <= r)
  56.     {
  57.         int mid = l + (r-l)/2;
  58.         memset(dp,-1,sizeof dp);
  59.         str = to_string(mid);
  60.         int good = f(0,0,false,false,false);
  61.         if(mid-good < n)
  62.         {
  63.             l = mid+1;
  64.         }else 
  65.         {
  66.             ans = mid;
  67.             r = mid-1;
  68.         }
  69.     }
  70.     cout << ans << endl;
  71.  
  72. }
  73.  
  74. int32_t main()
  75. {
  76.     int t = 1;
  77.     cin >> t;
  78.     while(t--) solve();
  79. }
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/uufPhx
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!