結果
問題 | No.319 happy b1rthday 2 me |
ユーザー |
|
提出日時 | 2019-12-09 17:03:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 2,113 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 82,944 KB |
実行使用メモリ | 65,084 KB |
最終ジャッジ日時 | 2024-06-22 23:54:37 |
合計ジャッジ時間 | 2,796 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
def calc1(N):N = str(N)L = len(N)dp = [[[[0]*10 for _ in range(2)] for _ in range(2)] for _ in range(L+1)]dp[0][0][0][0] = 1for i in range(L):Ni = int(N[i])for j in range(2):for k in range(10):for d in range(10 if j else Ni+1):if d!=1:if d!=2:dp[i+1][j|(d<Ni)][0][k] += dp[i][j][0][k]+dp[i][j][1][k]if d==2:dp[i+1][j|(d<Ni)][0][k] += dp[i][j][0][k]if k+1<10:dp[i+1][j|(d<Ni)][0][k+1] += dp[i][j][1][k]else:dp[i+1][j|(d<Ni)][1][k] += dp[i][j][0][k]+dp[i][j][1][k]res = 0for i in range(2):for j in range(2):for k in range(10):res += k*dp[L][i][j][k]return resdef calc2(N):N = str(N)L = len(N)dp = [[[0]*2 for _ in range(2)] for _ in range(L+1)]dp[0][0][0] = 1for i in range(L):Ni = int(N[i])if i==L-1:for j in range(2):for k in range(2):if 2<=Ni or j==1:dp[i+1][j|(2<Ni)][1] += dp[i][j][k]continuefor j in range(2):for k in range(2):if k==0:dp[i+1][j|(0<Ni)][0] += dp[i][j][k]if 2<=Ni or j==1:dp[i+1][j|(2<Ni)][1] += dp[i][j][k]else:for d in range(10 if j else Ni+1):dp[i+1][j|(d<Ni)][1] += dp[i][j][k]res = 0for i in range(2):for j in range(2):res += dp[L][i][j]return resA, B = map(int, input().split())ans = calc1(B)-calc1(A-1)+calc2(B)-calc2(A-1)strA = str(A)if strA[0]=='2' and strA[-1]=='2':ans -= 1print(ans)