結果
| 問題 |
No.1953 ８
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-07-17 20:38:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 14 ms / 2,000 ms |
| コード長 | 24,021 bytes |
| コンパイル時間 | 14,614 ms |
| コンパイル使用メモリ | 431,576 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-07-17 20:39:04 |
| 合計ジャッジ時間 | 18,463 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
//using mint = modint998244353;
using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
/*
わざわざ C++ で愚直を書く必要はないので Mathematica 上で愚直を書く．
wgt = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
ans = Accumulate@
Table[Total[wgt[[# + 1]] & /@ IntegerDigits[i, 10]], {i, 0,
100000}];
data = Association@
Table[key -> ans[[FromDigits[key, 10] + 1]], {len, 0, 5}, {key,
Tuples[Range[0, 9], len]}];
これを全自動スライド bitDP 学習器にぶち込んで圧縮した係数列を自動生成する．
*/
template <class VTYPE>
VTYPE solve(const string& s) {
// -------------------- 生成器からの出力を貼る --------------------
map<string, VTYPE>inis = { {"9", 6}, {"", 1}, {"8", 5}, {"80", 5}, {"7", 3}, {"70", 3}, {"6", 3}, {"60", 3}, {"5", 2}, {"50", 2}, {"4", 2}, {"40", 2}, {"3", 1}, {"30", 1}, {"2", 1}, {"20", 1}, {"1", 1}, {"10", 1}, {"0", 1}, {"00", 1} };
map<string, vector<tuple<int, string, VTYPE>>>rules = { {"99", {{2, "7", -90}, {2, "8", 180}, {2, "", -100}, {1, "", -70}}}, {"98", {{2, "7", -84}, {2, "9", -74}, {2, "", -100}, {1, "", 178}}}, {"97", {{2, "8", 156}, {2, "9", -68}, {2, "", -100}, {1, "", -68}}}, {"96", {{2, "7", -72}, {2, "9", 34}, {2, "", -100}, {1, "", 58}}}, {"95", {{2, "7", -66}, {2, "9", 43}, {2, "", -100}, {1, "", 43}}}, {"94", {{2, "8", -300}, {2, "9", 250}, {2, "", -100}, {1, "", 70}}}, {"93", {{2, "8", -324}, {2, "9", 280}, {2, "", -100}, {1, "", 64}}}, {"92", {{2, "8", -168}, {2, "9", 154}, {2, "", -100}, {1, "", 34}}}, {"91", {{2, "8", -112}, {2, "9", 108}, {2, "", -100}, {1, "", 24}}}, {"90", {{2, "8", -81}, {2, "9", 82}, {2, "", -100}, {1, "", 19}}}, {"89", {{2, "7", -89}, {2, "8", 179}, {2, "", -100}, {1, "", -70}}}, {"88", {{2, "7", -82}, {2, "9", -73}, {2, "", -100}, {1, "", 175}}}, {"87", {{2, "8", 157}, {2, "9", -69}, {2, "", -100}, {1, "", -68}}}, {"86", {{2, "7", -71}, {2, "8", 2}, {2, "9", 32}, {2, "", -100}, {1, "", 57}}}, {"85", {{2, "7", -66}, {2, "8", 1}, {2, "9", 42}, {2, "", -100}, {1, "", 43}}}, {"84", {{2, "8", -294}, {2, "9", 245}, {2, "", -100}, {1, "", 69}}}, {"83", {{2, "8", -323}, {2, "9", 279}, {2, "", -100}, {1, "", 64}}}, {"82", {{2, "8", -167}, {2, "9", 153}, {2, "", -100}, {1, "", 34}}}, {"81", {{2, "8", -111}, {2, "9", 107}, {2, "", -100}, {1, "", 24}}}, {"809", {{2, "7", 1}, {2, "8", 323}, {2, "9", -276}, {3, "", 200}, {2, "", -140}, {1, "", -26}}}, {"808", {{2, "7", 1}, {2, "8", 72}, {2, "9", -55}, {3, "", 100}, {2, "", -120}, {1, "", 3}}}, {"807", {{2, "7", 1}, {2, "8", 136}, {2, "9", -113}, {3, "", 100}, {2, "", -120}, {1, "", -3}}}, {"806", {{2, "7", 1}, {2, "8", 167}, {2, "9", -144}, {3, "", 200}, {2, "", -140}, {1, "", -2}}}, {"805", {{2, "7", 1}, {2, "8", 295}, {2, "9", -260}, {3, "", 200}, {2, "", -140}, {1, "", -14}}}, {"804", {{2, "7", 1}, {2, "8", 18}, {2, "9", -16}, {3, "", 200}, {2, "", -140}, {1, "", 19}}}, {"803", {{2, "7", 1}, {2, "8", 77}, {2, "9", -65}, {3, "", 100}, {2, "", -120}, {1, "", 8}}}, {"802", {{2, "7", 1}, {2, "8", 51}, {2, "9", -43}, {3, "", 100}, {2, "", -120}, {1, "", 12}}}, {"801", {{2, "7", 1}, {2, "8", 25}, {2, "9", -21}, {3, "", 100}, {2, "", -120}, {1, "", 16}}}, {"800", {{3, "8", 8}, {3, "9", 3}, {2, "8", -169}, {2, "9", 159}, {3, "", -100}, {2, "", -91}, {1, "", 29}}}, {"79", {{2, "7", -87}, {2, "8", 176}, {2, "", -100}, {1, "", -69}}}, {"78", {{2, "7", -79}, {2, "9", -71}, {2, "", -100}, {1, "", 170}}}, {"77", {{2, "8", 156}, {2, "9", -69}, {2, "", -100}, {1, "", -67}}}, {"76", {{2, "7", -69}, {2, "8", 2}, {2, "9", 31}, {2, "", -100}, {1, "", 56}}}, {"75", {{2, "7", -65}, {2, "9", 42}, {2, "", -100}, {1, "", 43}}}, {"74", {{2, "8", -283}, {2, "9", 236}, {2, "", -100}, {1, "", 67}}}, {"73", {{2, "8", -316}, {2, "9", 273}, {2, "", -100}, {1, "", 63}}}, {"72", {{2, "7", 1}, {2, "8", -168}, {2, "9", 153}, {2, "", -100}, {1, "", 34}}}, {"71", {{2, "7", 1}, {2, "8", -112}, {2, "9", 107}, {2, "", -100}, {1, "", 24}}}, {"709", {{2, "7", 1}, {2, "8", 126}, {2, "9", -102}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"708", {{2, "7", 3}, {2, "8", 69}, {2, "9", -54}, {3, "", 100}, {2, "", -120}, {1, "", 3}}}, {"707", {{2, "7", 3}, {2, "8", 133}, {2, "9", -112}, {3, "", 100}, {2, "", -120}, {1, "", -3}}}, {"706", {{2, "7", 1}, {2, "8", 48}, {2, "9", -36}, {3, "", 100}, {2, "", -120}, {1, "", 8}}}, {"705", {{2, "7", 1}, {2, "8", 112}, {2, "9", -94}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"704", {{2, "7", 3}, {2, "8", 15}, {2, "9", -15}, {3, "", 200}, {2, "", -140}, {1, "", 19}}}, {"703", {{2, "7", 3}, {2, "8", 74}, {2, "9", -64}, {3, "", 100}, {2, "", -120}, {1, "", 8}}}, {"702", {{2, "7", 3}, {2, "8", 48}, {2, "9", -42}, {3, "", 100}, {2, "", -120}, {1, "", 12}}}, {"701", {{2, "7", 3}, {2, "8", 22}, {2, "9", -20}, {3, "", 100}, {2, "", -120}, {1, "", 16}}}, {"700", {{3, "8", 7}, {3, "9", 4}, {2, "7", 1}, {2, "8", -169}, {2, "9", 158}, {3, "", -100}, {2, "", -91}, {1, "", 29}}}, {"69", {{2, "7", -87}, {2, "8", 177}, {2, "", -100}, {1, "", -70}}}, {"68", {{2, "7", -78}, {2, "9", -71}, {2, "", -100}, {1, "", 169}}}, {"67", {{2, "8", 159}, {2, "9", -71}, {2, "", -100}, {1, "", -68}}}, {"66", {{2, "7", -69}, {2, "9", 32}, {2, "", -100}, {1, "", 57}}}, {"65", {{2, "7", -66}, {2, "8", 3}, {2, "9", 40}, {2, "", -100}, {1, "", 43}}}, {"64", {{2, "8", -282}, {2, "9", 235}, {2, "", -100}, {1, "", 67}}}, {"63", {{2, "8", -321}, {2, "9", 277}, {2, "", -100}, {1, "", 64}}}, {"62", {{2, "8", -165}, {2, "9", 151}, {2, "", -100}, {1, "", 34}}}, {"61", {{2, "8", -109}, {2, "9", 105}, {2, "", -100}, {1, "", 24}}}, {"609", {{2, "7", 1}, {2, "8", 127}, {2, "9", -103}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"608", {{2, "7", 3}, {2, "8", 70}, {2, "9", -55}, {3, "", 100}, {2, "", -120}, {1, "", 3}}}, {"607", {{2, "7", 3}, {2, "8", 134}, {2, "9", -113}, {3, "", 100}, {2, "", -120}, {1, "", -3}}}, {"606", {{2, "7", 1}, {2, "8", 49}, {2, "9", -37}, {3, "", 100}, {2, "", -120}, {1, "", 8}}}, {"605", {{2, "7", 1}, {2, "8", 113}, {2, "9", -95}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"604", {{2, "7", 3}, {2, "8", 16}, {2, "9", -16}, {3, "", 200}, {2, "", -140}, {1, "", 19}}}, {"603", {{2, "7", 3}, {2, "8", 75}, {2, "9", -65}, {3, "", 100}, {2, "", -120}, {1, "", 8}}}, {"602", {{2, "7", 3}, {2, "8", 49}, {2, "9", -43}, {3, "", 100}, {2, "", -120}, {1, "", 12}}}, {"601", {{2, "7", 3}, {2, "8", 23}, {2, "9", -21}, {3, "", 100}, {2, "", -120}, {1, "", 16}}}, {"600", {{3, "8", 6}, {3, "9", 5}, {2, "8", -165}, {2, "9", 155}, {3, "", -100}, {2, "", -91}, {1, "", 29}}}, {"59", {{2, "7", -86}, {2, "8", 176}, {2, "", -100}, {1, "", -70}}}, {"58", {{2, "7", -76}, {2, "9", -70}, {2, "", -100}, {1, "", 166}}}, {"57", {{2, "8", 160}, {2, "9", -72}, {2, "", -100}, {1, "", -68}}}, {"56", {{2, "7", -68}, {2, "8", 2}, {2, "9", 30}, {2, "", -100}, {1, "", 56}}}, {"55", {{2, "7", -66}, {2, "9", 42}, {2, "", -100}, {1, "", 44}}}, {"54", {{2, "8", -276}, {2, "9", 230}, {2, "", -100}, {1, "", 66}}}, {"53", {{2, "8", -320}, {2, "9", 276}, {2, "", -100}, {1, "", 64}}}, {"52", {{2, "8", -164}, {2, "9", 150}, {2, "", -100}, {1, "", 34}}}, {"51", {{2, "8", -108}, {2, "9", 104}, {2, "", -100}, {1, "", 24}}}, {"509", {{2, "8", 337}, {2, "9", -288}, {3, "", 200}, {2, "", -140}, {1, "", -27}}}, {"508", {{2, "8", 86}, {2, "9", -67}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"507", {{2, "8", 150}, {2, "9", -125}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"506", {{2, "8", 181}, {2, "9", -156}, {3, "", 200}, {2, "", -140}, {1, "", -3}}}, {"505", {{2, "8", 309}, {2, "9", -272}, {3, "", 200}, {2, "", -140}, {1, "", -15}}}, {"504", {{2, "8", 32}, {2, "9", -28}, {3, "", 200}, {2, "", -140}, {1, "", 18}}}, {"503", {{2, "8", 91}, {2, "9", -77}, {3, "", 100}, {2, "", -120}, {1, "", 7}}}, {"502", {{2, "8", 65}, {2, "9", -55}, {3, "", 100}, {2, "", -120}, {1, "", 11}}}, {"501", {{2, "8", 39}, {2, "9", -33}, {3, "", 100}, {2, "", -120}, {1, "", 15}}}, {"500", {{3, "8", 5}, {3, "9", 6}, {2, "8", -163}, {2, "9", 153}, {3, "", -100}, {2, "", -91}, {1, "", 29}}}, {"49", {{2, "7", -86}, {2, "8", 177}, {2, "", -100}, {1, "", -71}}}, {"48", {{2, "7", -75}, {2, "9", -70}, {2, "", -100}, {1, "", 165}}}, {"47", {{2, "8", 163}, {2, "9", -74}, {2, "", -100}, {1, "", -69}}}, {"46", {{2, "7", -68}, {2, "9", 31}, {2, "", -100}, {1, "", 57}}}, {"45", {{2, "7", -67}, {2, "8", 3}, {2, "9", 40}, {2, "", -100}, {1, "", 44}}}, {"44", {{2, "8", -275}, {2, "9", 229}, {2, "", -100}, {1, "", 66}}}, {"43", {{2, "8", -325}, {2, "9", 280}, {2, "", -100}, {1, "", 65}}}, {"42", {{2, "7", 1}, {2, "8", -172}, {2, "9", 156}, {2, "", -100}, {1, "", 35}}}, {"41", {{2, "7", 2}, {2, "8", -119}, {2, "9", 112}, {2, "", -100}, {1, "", 25}}}, {"409", {{2, "8", 338}, {2, "9", -289}, {3, "", 200}, {2, "", -140}, {1, "", -27}}}, {"408", {{2, "8", 87}, {2, "9", -68}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"407", {{2, "8", 151}, {2, "9", -126}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"406", {{2, "8", 182}, {2, "9", -157}, {3, "", 200}, {2, "", -140}, {1, "", -3}}}, {"405", {{2, "8", 310}, {2, "9", -273}, {3, "", 200}, {2, "", -140}, {1, "", -15}}}, {"404", {{2, "8", 33}, {2, "9", -29}, {3, "", 200}, {2, "", -140}, {1, "", 18}}}, {"403", {{2, "8", 92}, {2, "9", -78}, {3, "", 100}, {2, "", -120}, {1, "", 7}}}, {"402", {{2, "8", 66}, {2, "9", -56}, {3, "", 100}, {2, "", -120}, {1, "", 11}}}, {"401", {{2, "8", 40}, {2, "9", -34}, {3, "", 100}, {2, "", -120}, {1, "", 15}}}, {"400", {{3, "8", 4}, {3, "9", 7}, {2, "7", 3}, {2, "8", -176}, {2, "9", 162}, {3, "", -100}, {2, "", -91}, {1, "", 30}}}, {"39", {{2, "7", -85}, {2, "8", 176}, {2, "", -100}, {1, "", -71}}}, {"38", {{2, "7", -73}, {2, "9", -69}, {2, "", -100}, {1, "", 162}}}, {"37", {{2, "8", 164}, {2, "9", -75}, {2, "", -100}, {1, "", -69}}}, {"36", {{2, "7", -67}, {2, "8", 2}, {2, "9", 29}, {2, "", -100}, {1, "", 56}}}, {"35", {{2, "7", -67}, {2, "9", 42}, {2, "", -100}, {1, "", 45}}}, {"34", {{2, "8", -269}, {2, "9", 224}, {2, "", -100}, {1, "", 65}}}, {"33", {{2, "8", -324}, {2, "9", 279}, {2, "", -100}, {1, "", 65}}}, {"32", {{2, "7", 1}, {2, "8", -171}, {2, "9", 155}, {2, "", -100}, {1, "", 35}}}, {"31", {{2, "7", 2}, {2, "8", -118}, {2, "9", 111}, {2, "", -100}, {1, "", 25}}}, {"309", {{2, "7", 1}, {2, "8", 337}, {2, "9", -289}, {3, "", 200}, {2, "", -140}, {1, "", -27}}}, {"308", {{2, "7", 1}, {2, "8", 86}, {2, "9", -68}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"307", {{2, "7", 1}, {2, "8", 150}, {2, "9", -126}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"306", {{2, "7", 1}, {2, "8", 181}, {2, "9", -157}, {3, "", 200}, {2, "", -140}, {1, "", -3}}}, {"305", {{2, "7", 1}, {2, "8", 309}, {2, "9", -273}, {3, "", 200}, {2, "", -140}, {1, "", -15}}}, {"304", {{2, "7", 1}, {2, "8", 32}, {2, "9", -29}, {3, "", 200}, {2, "", -140}, {1, "", 18}}}, {"303", {{2, "7", 1}, {2, "8", 91}, {2, "9", -78}, {3, "", 100}, {2, "", -120}, {1, "", 7}}}, {"302", {{2, "7", 1}, {2, "8", 65}, {2, "9", -56}, {3, "", 100}, {2, "", -120}, {1, "", 11}}}, {"301", {{2, "7", 1}, {2, "8", 39}, {2, "9", -34}, {3, "", 100}, {2, "", -120}, {1, "", 15}}}, {"300", {{3, "8", 3}, {3, "9", 8}, {2, "7", 3}, {2, "8", -174}, {2, "9", 160}, {3, "", -100}, {2, "", -91}, {1, "", 30}}}, {"29", {{2, "7", -85}, {2, "8", 177}, {2, "", -100}, {1, "", -72}}}, {"28", {{2, "7", -72}, {2, "9", -69}, {2, "", -100}, {1, "", 161}}}, {"27", {{2, "8", 167}, {2, "9", -77}, {2, "", -100}, {1, "", -70}}}, {"26", {{2, "7", -67}, {2, "9", 30}, {2, "", -100}, {1, "", 57}}}, {"25", {{2, "7", -68}, {2, "8", 3}, {2, "9", 40}, {2, "", -100}, {1, "", 45}}}, {"24", {{2, "8", -268}, {2, "9", 223}, {2, "", -100}, {1, "", 65}}}, {"23", {{2, "8", -329}, {2, "9", 283}, {2, "", -100}, {1, "", 66}}}, {"22", {{2, "8", -168}, {2, "9", 153}, {2, "", -100}, {1, "", 35}}}, {"21", {{2, "7", 1}, {2, "8", -115}, {2, "9", 109}, {2, "", -100}, {1, "", 25}}}, {"209", {{2, "7", 1}, {2, "8", 338}, {2, "9", -290}, {3, "", 200}, {2, "", -140}, {1, "", -27}}}, {"208", {{2, "7", 1}, {2, "8", 87}, {2, "9", -69}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"207", {{2, "7", 1}, {2, "8", 151}, {2, "9", -127}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"206", {{2, "7", 1}, {2, "8", 182}, {2, "9", -158}, {3, "", 200}, {2, "", -140}, {1, "", -3}}}, {"205", {{2, "7", 1}, {2, "8", 310}, {2, "9", -274}, {3, "", 200}, {2, "", -140}, {1, "", -15}}}, {"204", {{2, "7", 1}, {2, "8", 33}, {2, "9", -30}, {3, "", 200}, {2, "", -140}, {1, "", 18}}}, {"203", {{2, "7", 1}, {2, "8", 92}, {2, "9", -79}, {3, "", 100}, {2, "", -120}, {1, "", 7}}}, {"202", {{2, "7", 1}, {2, "8", 66}, {2, "9", -57}, {3, "", 100}, {2, "", -120}, {1, "", 11}}}, {"201", {{2, "7", 1}, {2, "8", 40}, {2, "9", -35}, {3, "", 100}, {2, "", -120}, {1, "", 15}}}, {"200", {{3, "8", 2}, {3, "9", 9}, {2, "7", 2}, {2, "8", -170}, {2, "9", 157}, {3, "", -100}, {2, "", -91}, {1, "", 30}}}, {"19", {{2, "7", -85}, {2, "8", 178}, {2, "", -100}, {1, "", -73}}}, {"18", {{2, "7", -71}, {2, "9", -69}, {2, "", -100}, {1, "", 160}}}, {"17", {{2, "8", 170}, {2, "9", -79}, {2, "", -100}, {1, "", -71}}}, {"16", {{2, "7", -67}, {2, "8", 1}, {2, "9", 29}, {2, "", -100}, {1, "", 57}}}, {"15", {{2, "7", -69}, {2, "8", 2}, {2, "9", 41}, {2, "", -100}, {1, "", 46}}}, {"14", {{2, "8", -267}, {2, "9", 222}, {2, "", -100}, {1, "", 65}}}, {"13", {{2, "8", -334}, {2, "9", 287}, {2, "", -100}, {1, "", 67}}}, {"12", {{2, "7", 1}, {2, "8", -176}, {2, "9", 159}, {2, "", -100}, {1, "", 36}}}, {"11", {{2, "8", -112}, {2, "9", 107}, {2, "", -100}, {1, "", 25}}}, {"109", {{2, "7", 1}, {2, "8", 339}, {2, "9", -291}, {3, "", 200}, {2, "", -140}, {1, "", -27}}}, {"108", {{2, "7", 1}, {2, "8", 88}, {2, "9", -70}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"107", {{2, "7", 1}, {2, "8", 152}, {2, "9", -128}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"106", {{2, "7", 1}, {2, "8", 183}, {2, "9", -159}, {3, "", 200}, {2, "", -140}, {1, "", -3}}}, {"105", {{2, "7", 1}, {2, "8", 311}, {2, "9", -275}, {3, "", 200}, {2, "", -140}, {1, "", -15}}}, {"104", {{2, "7", 1}, {2, "8", 34}, {2, "9", -31}, {3, "", 200}, {2, "", -140}, {1, "", 18}}}, {"103", {{2, "7", 1}, {2, "8", 93}, {2, "9", -80}, {3, "", 100}, {2, "", -120}, {1, "", 7}}}, {"102", {{2, "7", 1}, {2, "8", 67}, {2, "9", -58}, {3, "", 100}, {2, "", -120}, {1, "", 11}}}, {"101", {{2, "7", 1}, {2, "8", 41}, {2, "9", -36}, {3, "", 100}, {2, "", -120}, {1, "", 15}}}, {"100", {{3, "8", 1}, {2, "7", 1}, {2, "8", -85}, {2, "9", 83}, {2, "", -101}, {1, "", 21}}}, {"09", {{2, "7", -85}, {2, "8", 179}, {2, "", -100}, {1, "", -74}}}, {"08", {{2, "7", -70}, {2, "9", -69}, {2, "", -100}, {1, "", 159}}}, {"07", {{2, "8", 173}, {2, "9", -81}, {2, "", -100}, {1, "", -72}}}, {"06", {{2, "7", -67}, {2, "8", 2}, {2, "9", 28}, {2, "", -100}, {1, "", 57}}}, {"05", {{2, "7", -70}, {2, "8", 1}, {2, "9", 42}, {2, "", -100}, {1, "", 47}}}, {"04", {{2, "8", -266}, {2, "9", 221}, {2, "", -100}, {1, "", 65}}}, {"03", {{2, "8", -339}, {2, "9", 291}, {2, "", -100}, {1, "", 68}}}, {"02", {{2, "8", -173}, {2, "9", 157}, {2, "", -100}, {1, "", 36}}}, {"01", {{2, "7", 2}, {2, "8", -123}, {2, "9", 115}, {2, "", -100}, {1, "", 26}}}, {"009", {{2, "7", 1}, {2, "8", 340}, {2, "9", -292}, {3, "", 200}, {2, "", -140}, {1, "", -27}}}, {"008", {{2, "7", 1}, {2, "8", 89}, {2, "9", -71}, {3, "", 100}, {2, "", -120}, {1, "", 2}}}, {"007", {{2, "7", 1}, {2, "8", 153}, {2, "9", -129}, {3, "", 100}, {2, "", -120}, {1, "", -4}}}, {"006", {{2, "7", 1}, {2, "8", 184}, {2, "9", -160}, {3, "", 200}, {2, "", -140}, {1, "", -3}}}, {"005", {{2, "7", 1}, {2, "8", 312}, {2, "9", -276}, {3, "", 200}, {2, "", -140}, {1, "", -15}}}, {"004", {{2, "7", 1}, {2, "8", 35}, {2, "9", -32}, {3, "", 200}, {2, "", -140}, {1, "", 18}}}, {"003", {{2, "7", 1}, {2, "8", 94}, {2, "9", -81}, {3, "", 100}, {2, "", -120}, {1, "", 7}}}, {"002", {{2, "7", 1}, {2, "8", 68}, {2, "9", -59}, {3, "", 100}, {2, "", -120}, {1, "", 11}}}, {"001", {{2, "7", 1}, {2, "8", 42}, {2, "9", -37}, {3, "", 100}, {2, "", -120}, {1, "", 15}}}, {"000", {{3, "9", 1}, {2, "8", -81}, {2, "9", 80}, {2, "", -101}, {1, "", 21}}} };
// --------------------------------------------------------------
// ここ以降は書き換える必要はない．
map<pair<int, string>, VTYPE> dp;
function<VTYPE(int, string)> rf = [&](int i, string s_add) {
//dump(i, s_add);
if (dp.count({ i, s_add })) return dp[{i, s_add}];
int L_add = sz(s_add);
string sR;
rep(j, L_add) {
sR += s_add[j];
if (rules.count(sR)) {
VTYPE res = 0;
for (auto [i2, s_add2, wgt] : rules[sR]) {
res += rf(i + L_add - i2, s_add2) * wgt; // ?
}
return dp[{i, s_add}] = res;
}
}
repir(j, i - 1, 0) {
sR += s[j];
if (rules.count(sR)) {
VTYPE res = 0;
for (auto [i2, s_add2, wgt] : rules[sR]) {
if (i2 >= L_add) {
res += rf(i + L_add - i2, s_add2) * wgt;
}
else {
res += rf(i, s_add2 + s_add.substr(L_add - i2)) * wgt;
}
}
return dp[{i, s_add}] = res;
}
}
assert(inis.count(sR));
return dp[{i, s_add}] = inis[sR];
};
return rf(sz(s), "");
}
//【めぐる式二分探索】O(log|ok - ng|)
/*
* 条件 okQ() を満たす要素 ok と満たさない要素 ng との境界を二分探索する．
* 境界に隣り合うような条件を満たす要素（ok 側）の位置を返す．
* debug_mode = true にして実行すると手元では単調かどうかチェックしながら全探索する．
*/
template <class T, class FUNC>
T meguru_search(T ok, T ng, const FUNC& okQ, bool debug_mode = false) {
// 参考 : https://twitter.com/meguru_comp/status/697008509376835584
// verify : https://atcoder.jp/contests/typical90/tasks/typical90_a
Assert(ok != ng);
#ifdef _MSC_VER
// 単調かどうか自信がないとき用
if (debug_mode) {
T step = ok < ng ? 1 : -1; T res = ok; bool is_ok = true;
for (T i = ok; i != ng + step; i += step) {
auto b = (i == ok ? true : i == ng ? false : okQ(i));
if (b) {
if (!is_ok) {
cout << "not monotony!" << endl;
for (T i = ok; i != ng + step; i += step) {
auto b = (i == ok ? true : i == ng ? false : okQ(i));
cout << i << " : " << b << endl;
}
exit(1);
}
}
else {
if (is_ok) res = i - step;
is_ok = false;
}
}
return res;
}
#endif
// 境界が決定するまで
while (abs(ok - ng) > 1) {
// 区間の中間
T mid = (ok + ng) / 2;
// 中間が OK かどうかに応じて区間を縮小する．
if (okQ(mid)) ok = mid;
else ng = mid;
}
return ok;
/* okQ の定義の雛形
auto okQ = [&](ll x) {
return true || false;
};
*/
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
ll K;
cin >> K;
auto okQ = [&](ll n) {
return solve<ull>(to_string(n)) - 1 <= K;
};
ll n = meguru_search(0LL, INFL, okQ);
dump("n:", n);
if (solve<ull>(to_string(n)) - 1 != K) EXIT(-1);
EXIT(n);
}