結果
問題 |
No.1953 8
|
ユーザー |
![]() |
提出日時 | 2022-05-20 23:22:14 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 761 bytes |
コンパイル時間 | 265 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-09-20 09:45:21 |
合計ジャッジ時間 | 4,886 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
from functools import lru_cache maru = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1] accmaru = maru[:] for i in range(1, 10): accmaru[i] += accmaru[i-1] def parse(x): res = 0 while x: x, m = divmod(x, 10) res += maru[m] return res @lru_cache(maxsize=None) def dfs(x): if x < 10: return accmaru[x] d, m = divmod(x, 10) res = 0 for i in range(10 * d, x + 1): res += parse(i) res += d * accmaru[9] res += 10 * (dfs(d - 1) - 1) return res def main(): K = int(input()) l = 0 r = 10 ** 18 while r - l > 1: m = (r + l) // 2 if dfs(m) - 1 > K: r = m else: l = m if dfs(l) - 1 != K: return -1 return l print(main())