結果
問題 |
No.1953 8
|
ユーザー |
![]() |
提出日時 | 2022-05-20 23:43:02 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 914 bytes |
コンパイル時間 | 14,720 ms |
コンパイル使用メモリ | 296,348 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 10:10:44 |
合計ジャッジ時間 | 15,331 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
C = [1i64, 0i64, 0i64, 0i64, 1i64, 0i64, 1i64, 0i64, 2i64, 1i64] CS = [0i64] C.size.times do |i| CS << CS[i] + C[i] end CNT = [0i64, CS[-1]] 1.upto(16) do |i| CNT << CNT[i] + (CS[-1] - 1) * (10i64 ** i) + CS[-1] * 9 * (10i64 ** (i - 1)) * i end k = read_line.to_i64 + 1 lo = 0i64 hi = 100000000000000000i64 while hi - lo > 1 mid = (lo + hi) // 2 # puts [mid, cnt(mid, mid.to_s.size - 1, 1)] if cnt(mid, mid.to_s.size - 1, 1) > k hi = mid else lo = mid end end puts cnt(lo, lo.to_s.size - 1, 1) == k ? lo : -1 def cnt(v, len, first) if len == 0 return CS[v + 1] end hi = v // (10i64 ** len) rest = v - hi * (10i64 ** len) ret = 0i64 if first == 1 ret += CNT[len] end ret += (CS[hi] - first) * (10i64 ** len) ret += (hi - first) * CS[-1] * (10i64 ** (len - 1)) * len ret += C[hi] * (rest + 1) ret += cnt(rest, len - 1, 0) # puts [v, len, ret] return ret end