結果
問題 | No.1106 🦉 何事もバランスが大事 |
ユーザー |
![]() |
提出日時 | 2020-07-03 22:35:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,500 bytes |
コンパイル時間 | 1,014 ms |
コンパイル使用メモリ | 81,900 KB |
実行使用メモリ | 72,360 KB |
最終ジャッジ日時 | 2024-09-17 04:17:09 |
合計ジャッジ時間 | 7,412 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 77 |
ソースコード
mod = 1000000007 eps = 10**-9 def main(): import sys input = sys.stdin.readline N = int(input()) F = [] while N: n, m = divmod(N, 5) if m < 3: F.append(m) N = n else: F.append(m-5) N = n+1 F.reverse() L = len(F) dp0 = [[0] * (4*L+1) for _ in range(L+1)] dp1 = [[0] * (4*L+1) for _ in range(L+1)] dp0[0][0] = 1 for i in range(L): f = F[i] for j in range(-2*L, 2*L+1): for b in range(-2, 3): if b < f: dp1[i+1][j+b] += dp0[i][j] + dp1[i][j] elif b > f: dp1[i+1][j+b] += dp1[i][j] else: dp0[i+1][j+b] += dp0[i][j] dp1[i+1][j+b] += dp1[i][j] ans = dp0[-1][0] + dp1[-1][0] dp0 = [[0] * (4 * L + 1) for _ in range(L + 1)] dp1 = [[0] * (4 * L + 1) for _ in range(L + 1)] dp0[0][0] = 1 F = [0] * L for i in range(L): f = F[i] for j in range(-2 * L, 2 * L + 1): for b in range(-2, 3): if b < f: dp1[i + 1][j + b] += dp0[i][j] + dp1[i][j] elif b > f: dp1[i + 1][j + b] += dp1[i][j] else: dp0[i + 1][j + b] += dp0[i][j] dp1[i + 1][j + b] += dp1[i][j] ans_neg = dp0[-1][0] + dp1[-1][0] print(ans - ans_neg) if __name__ == '__main__': main()