結果
問題 | No.189 SUPER HAPPY DAY |
ユーザー | e-mon |
提出日時 | 2015-04-23 20:47:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 401 ms / 5,000 ms |
コード長 | 1,333 bytes |
コンパイル時間 | 378 ms |
コンパイル使用メモリ | 87,112 KB |
実行使用メモリ | 144,500 KB |
最終ジャッジ日時 | 2023-09-18 08:43:35 |
合計ジャッジ時間 | 8,874 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 236 ms
104,136 KB |
testcase_01 | AC | 240 ms
104,160 KB |
testcase_02 | AC | 234 ms
104,060 KB |
testcase_03 | AC | 243 ms
104,420 KB |
testcase_04 | AC | 244 ms
104,308 KB |
testcase_05 | AC | 240 ms
104,180 KB |
testcase_06 | AC | 240 ms
104,152 KB |
testcase_07 | AC | 244 ms
104,176 KB |
testcase_08 | AC | 242 ms
103,860 KB |
testcase_09 | AC | 242 ms
104,320 KB |
testcase_10 | AC | 241 ms
104,164 KB |
testcase_11 | AC | 245 ms
104,280 KB |
testcase_12 | AC | 241 ms
104,272 KB |
testcase_13 | AC | 330 ms
117,588 KB |
testcase_14 | AC | 369 ms
125,856 KB |
testcase_15 | AC | 361 ms
132,768 KB |
testcase_16 | AC | 359 ms
131,316 KB |
testcase_17 | AC | 391 ms
144,500 KB |
testcase_18 | AC | 339 ms
120,236 KB |
testcase_19 | AC | 401 ms
139,712 KB |
testcase_20 | AC | 291 ms
109,160 KB |
testcase_21 | AC | 303 ms
108,764 KB |
testcase_22 | AC | 249 ms
104,384 KB |
testcase_23 | AC | 245 ms
104,500 KB |
testcase_24 | AC | 242 ms
104,164 KB |
testcase_25 | AC | 249 ms
104,416 KB |
ソースコード
#!/usr/bin/env python # -*- coding: utf-8 -*- import sys sys.setrecursionlimit(10**6) M,D = map(int,input().split()) length = 201 dp = [[False for i in range(1800+2)] for j in range(length)] dp[0][0] = 1 for i in range(1,10): dp[0][i] = 1 for n in range(1,length): dp[n] = dp[n-1]+[] for i in range(1,10): for d in range(1800+2)[::-1]: if d+i < 1800+2 and dp[n-1][d] is not False: dp[n][d+i] += dp[n-1][d] #ある桁数のその数字までの値を求める def hoge(digit,n): n = int(n) xs = [0 for i in range(1800+2)] upper = 0 for i in range(int(n)): for d in range(1800+2)[::-1]: if d+i < 1800+2: xs[d+i] += dp[digit-1][d] return xs def solve(num,digit): #numまでは足して,numになったらnum以降の数字で出来たものにnumを足したものを返す if digit == 0: a = [1 if i <= int(num) else 0 for i in range(0,1800+2)] return a n = int(num[0]) a = hoge(digit,n) b = solve(num[1:],digit-1) for i in range(1800+2): if i+n < 1800+2: a[i+n] += b[i] return a M_count = solve(str(M),len(str(M))-1) D_count = solve(str(D),len(str(D))-1) ans = 0 for i in range(1,1800+2): ans += M_count[i] * D_count[i] %(10**9+9) print(ans%(10**9+9))