結果
問題 | No.657 テトラナッチ数列 Easy |
ユーザー |
![]() |
提出日時 | 2025-03-20 18:58:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 1,053 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 82,728 KB |
実行使用メモリ | 77,000 KB |
最終ジャッジ日時 | 2025-03-20 18:59:16 |
合計ジャッジ時間 | 2,288 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
def precompute(): mod = 17 sequence = [0, 0, 0, 1] # T1 to T4 state_map = {} current_state = (0, 0, 0, 1) state_map[current_state] = 4 # next index to be added is 4 (T5) cycle_length = None cycle_start = None n = 4 # current index is 3 (T4), next to compute is T5 (index 4) while True: next_val = sum(current_state) % mod sequence.append(next_val) n += 1 # now n is the next index + 1 after appending new_state = (current_state[1], current_state[2], current_state[3], next_val) if new_state in state_map: cycle_start = state_map[new_state] cycle_length = n - cycle_start break else: state_map[new_state] = n current_state = new_state return sequence, cycle_length sequence, cycle_length = precompute() Q = int(input()) for _ in range(Q): n = int(input()) if n <= 4: print(sequence[n-1]) else: offset = (n - 5) % cycle_length print(sequence[4 + offset])