結果
問題 | No.1595 The Final Digit |
ユーザー |
![]() |
提出日時 | 2021-07-10 11:13:36 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 916 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-07-02 01:50:37 |
合計ジャッジ時間 | 1,532 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
# 周期、サイクルfrom collections import defaultdictp, q, r, K = map(int, input().split())A = [-1] * 10 ** 5A[0] = p % 10A[1] = q % 10A[2] = r % 10# 3点が一致すれば循環するvisited = defaultdict(tuple)steps = [(-1, -1, A[0]), (-1, -1, A[1]), (-1, -1, A[2])]pos = (A[0], A[1], A[2])cnt = 2while pos not in visited:visited[pos] = 1steps.append(pos)cnt += 1A[cnt] = A[cnt - 1] + A[cnt - 2] + A[cnt - 3]A[cnt] %= 10pos = (A[cnt - 2], A[cnt - 1], A[cnt])if cnt == K - 1:print(A[K - 1])exit()# print(steps)loop_start = steps.index(pos) # ループの開始点loop_cycle = len(steps) - loop_start # ループの周期# print(loop_start, loop_cycle)freq, pos = divmod(K - loop_start - 1, loop_cycle) # freq:周回数、pos:到着位置# ans = steps[loop_start + pos] + 1ans = steps[loop_start + pos]print(sum(ans) % 10)