結果
問題 | No.2455 Numbers Dictionary |
ユーザー |
![]() |
提出日時 | 2023-08-25 20:36:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 860 bytes |
コンパイル時間 | 1,916 ms |
コンパイル使用メモリ | 192,256 KB |
最終ジャッジ日時 | 2025-02-16 13:34:54 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = unsigned long long;//Kを接頭辞としてもつ数字のうち、N以下であるものの数ll f(ll K, ll N){if (K > N) return 0;ll res = 1, Z=K;while(Z<=N && K*10<=N){Z = Z*10+9;K *= 10;assert (min(Z, N)-K+1>=0);res += min(Z, N)-K+1;}return res;}//辞書順でK以下、数字でN以下であるものの数string K;ll N;ll g(ll idx=0, ll num=0){num *= 10;ll c = K[idx]-'0', res = 0;if (idx != 0 && c != 0) res += f(num, N);if (num+c <= N) res++;for (int i=1; i<c; i++) res += f(num+i, N);if (idx < K.size()-1) res += g(idx+1, num+c);return res;}int main(){int T;cin >> T;while(T){T--;cin >> N >> K;cout << g() << endl;}return 0;}