結果
問題 |
No.1953 8
|
ユーザー |
|
提出日時 | 2022-05-20 23:13:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,370 bytes |
コンパイル時間 | 2,237 ms |
コンパイル使用メモリ | 204,068 KB |
最終ジャッジ日時 | 2025-01-29 11:37:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef _RUTHEN #include "debug.hpp" #else #define show(...) true #endif using ll = long long; #define rep(i, n) for (int i = 0; i < (n); i++) template <class T> using V = vector<T>; const int c[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1}; ll f(ll x) { string s = to_string(x); int N = s.size(); V<V<V<ll>>> dpc(N + 1, V<V<ll>>(2, V<ll>(2, 0))); V<V<V<ll>>> dps(N + 1, V<V<ll>>(2, V<ll>(2, 0))); dpc[0][0][0] = 1; rep(i, N) { rep(j, 2) { rep(k, 2) { for (int d = 0; d <= (j ? 9 : s[i] - '0'); d++) { dpc[i + 1][j | (d < s[i] - '0')][k | (d != 0)] += dpc[i][j][k]; dps[i + 1][j | (d < s[i] - '0')][k | (d != 0)] += dps[i][j][k] + dpc[i][j][k] * ((k | (d != 0)) ? c[d] : 0); } } } } ll ans = dps[N][1][0] + dps[N][1][1] + dps[N][0][1]; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll K; cin >> K; // f(n) >= K となる最小のn ll ok = 99193752409910750LL, ng = 0; while (ok - ng > 1) { ll n = (ok + ng) / 2; if (f(n) >= K) { ok = n; } else { ng = n; } } if (f(ok) == K) { cout << ok << '\n'; } else { cout << -1 << '\n'; } return 0; }