結果
問題 | No.220 世界のなんとか2 |
ユーザー |
![]() |
提出日時 | 2022-11-04 21:50:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 56 ms / 1,000 ms |
コード長 | 1,456 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 56,576 KB |
最終ジャッジ日時 | 2024-07-18 19:35:33 |
合計ジャッジ時間 | 1,934 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
import sysimport itertoolsimport heapqimport bisectfrom collections import deque, defaultdictfrom functools import lru_cache, cmp_to_keyinput = sys.stdin.readline# for AtCoder Easy testif __file__ != 'prog.py':sys.setrecursionlimit(10 ** 6)def readints(): return map(int, input().split())def readlist(): return list(readints())def readstr(): return input().rstrip()P = int(input())S = str(10 ** P)dp = [[[0, 0] for _ in range(2)] for _ in range(3)]dp[0][0][0] = 1for i in range(len(S)):ndp = [[[0, 0] for _ in range(2)] for _ in range(3)]for j in range(3):for k in range(10):n = (j + k) % 3if k == 3:ndp[n][1][1] += dp[j][1][1] + dp[j][0][1]else:ndp[n][1][1] += dp[j][1][1]ndp[n][0][1] += dp[j][0][1]if k < int(S[i]):if k == 3:ndp[n][1][1] += dp[j][1][0] + dp[j][0][0]else:ndp[n][1][1] += dp[j][1][0]ndp[n][0][1] += dp[j][0][0]elif k == int(S[i]):if k == 3:ndp[n][1][0] += dp[j][1][0] + dp[j][0][0]else:ndp[n][1][0] += dp[j][1][0]ndp[n][0][0] += dp[j][0][0]dp = ndpans = 0for i in range(3):for j in range(2):if i == 0 or j == 1:ans += sum(dp[i][j])print(ans - 1)