結果

問題 No.220 世界のなんとか2
ユーザー roaris
提出日時 2019-10-29 07:03:39
言語 PyPy3
(7.0.0)
結果
AC  
実行時間 142 ms
コード長 445 Byte
コンパイル時間 250 ms
使用メモリ 69,080 KB
最終ジャッジ日時 2019-10-29 07:03:42

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
test01.txt AC 110 ms
68,480 KB
test02.txt AC 115 ms
67,604 KB
test03.txt AC 115 ms
67,368 KB
test04.txt AC 109 ms
67,448 KB
test05.txt AC 115 ms
67,316 KB
test06.txt AC 132 ms
67,300 KB
test07.txt AC 107 ms
68,080 KB
test08.txt AC 107 ms
67,464 KB
test09.txt AC 106 ms
67,308 KB
test10.txt AC 110 ms
67,424 KB
test11.txt AC 110 ms
67,348 KB
test12.txt AC 113 ms
68,144 KB
test13.txt AC 110 ms
67,560 KB
test14.txt AC 111 ms
67,312 KB
test15.txt AC 108 ms
67,432 KB
test16.txt AC 119 ms
68,528 KB
test17.txt AC 142 ms
69,080 KB
test18.txt AC 117 ms
68,012 KB
test19.txt AC 118 ms
68,044 KB
テストケース一括ダウンロード

ソースコード

diff #
P = int(input())
S = str(10**P)
L = len(S)
dp = [[[[0] * 2 for _ in range(3)] for _ in range(2)] for _ in range(L+1)]
dp[0][0][0][0] = 1

for i in range(L):
    for j in range(2):
        for d in range(10 if j else int(S[i])):
            for k in range(3):
                for l in range(2):
                    dp[i+1][j|(d<int(S[i]))][(k+d)%3][l|(d==3)] += dp[i][j][k][l]

print(dp[L][1][0][0]+dp[L][1][0][1]+dp[L][1][1][1]+dp[L][1][2][1]-1)
0