fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug clog << "No errors!"; exit(0);
  37. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b) for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define popcount __builtin_popcountll
  44. #define BIT(x, i) (x >> i) & 1
  45. #define MASK(x) (1LL << x)
  46. #define want_digit(x) cout << fixed << setprecision(x);
  47. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  48. #define i128 __int128
  49. using namespace std;
  50. const int MOD = 1e9 + 7; // 998244353
  51. const int inf = 1e9;
  52. const ll INF = 1e18;
  53. const int N = 20;
  54.  
  55. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  56. ll random(const ll &L, const ll &R)
  57. {
  58.     return uniform_int_distribution<ll> (L, R) (rng);
  59. }
  60.  
  61. vector <int> operator + (vector <int> v, int x)
  62. {
  63.     ++v[x];
  64.     return v;
  65. }
  66.  
  67. map <vector <int>, ll> dp[N + 5];
  68. ll f(const int &pos, const bool &lower, const vector <int> &v, const str &x)
  69. {
  70.     if (!pos)
  71.     {
  72. //        cout << digit << endl;
  73.         return 1;
  74.     }
  75.  
  76.     if (lower && dp[pos].find(v) != dp[pos].end()) return dp[pos][v];
  77.  
  78.     bool check = false;
  79.     forw (i, 0, 9) if (v[i])
  80.     {
  81.         check = true;
  82.         break;
  83.     }
  84.  
  85.     int fin = lower ? 9 : x[pos - 1] - '0';
  86.     ll X = 0;
  87.  
  88.     forw (i, 0, fin)
  89.     {
  90.         if (v[i] == 2) continue;
  91.         X += f(pos - 1, lower || i < fin, (i || (!i && check)) ? v + i : v, x);
  92.     }
  93.  
  94. //    return X;
  95.     if (lower) dp[pos][v] = X;
  96.     return X;
  97. }
  98.  
  99. vector <int> base(10, 0);
  100. ll calc(const ll &x)
  101. {
  102.     str s = to_string(x);
  103.     rev(all(s));
  104.     return f(sz(s), false, base, s) - 1; // Hàm f nó tính luôn số 0
  105. }
  106.  
  107. ll k;
  108. void solve()
  109. {
  110.     cin >> k;
  111.     ll l = 1, r = INF, mid, ans = -1;
  112.     while (l <= r)
  113.     {
  114.         mid = (l + r) >> 1;
  115.         if (calc(mid) >= k)
  116.         {
  117.             ans = mid;
  118.             r = mid - 1;
  119.         }
  120.         else l = mid + 1;
  121.     }
  122.  
  123.     cout << ans << endl;
  124. }
  125.  
  126. signed main()
  127. {
  128.     ios::sync_with_stdio(false), cin.tie(nullptr);
  129.     srand(time(NULL));
  130. #define name "test"
  131.     /*
  132.     if (fopen(name".INP", "r"))
  133.     {
  134.         freopen(name".INP", "r", stdin);
  135.         freopen(name".OUT", "w", stdout);
  136.     }
  137.     */
  138.     int numTest = 1;
  139. //    cin >> numTest;
  140.     while (numTest--)
  141.     {
  142.         solve();
  143.     }
  144.     return 0;
  145. }
  146.  
Success #stdin #stdout 1.61s 62820KB
comments (?)
stdin
copy 
2025
stdout
copy 
2073
https://ideone.com/s3pFhq
language:
C++14 (gcc 8.3)
created:
8 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!