結果

問題 No.1004 サイコロの実装 (2)
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:51:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,260 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 81,848 KB
実行使用メモリ 69,916 KB
最終ジャッジ日時 2025-04-16 15:52:31
合計ジャッジ時間 5,386 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

a, b, x0, N = map(int, input().split())

a_mod6 = a % 6
b_mod6 = b % 6
s0 = x0 % 6

# Find the cycle of x_i mod6
visited = {}
history = [s0]  # history[0] = x0 mod6
current = s0
step = 0
while True:
    next_s = (a_mod6 * current + b_mod6) % 6
    if next_s in visited:
        break
    visited[next_s] = step + 1  # step+1 is the index in history where next_s is stored
    history.append(next_s)
    current = next_s
    step += 1

cycle_start = visited[next_s]
cycle = history[cycle_start:]
cycle_len = len(cycle)

M = 2 * N
t_black = 0
t_white = 0
a_black = 0
a_white = 0

t_parity = 0
a_parity = 0

for i in range(M):
    # Calculate x_{i+1} mod6
    if i + 1 < len(history):
        s_i_plus_1 = history[i + 1]
    else:
        pos_in_cycle = (i + 1 - cycle_start) % cycle_len
        s_i_plus_1 = cycle[pos_in_cycle]
    
    parity = 1 - (s_i_plus_1 % 2)
    
    if (i + 1) % 2 == 1:  # Takahashi's turn (1st, 3rd, 5th steps)
        t_parity ^= parity
        if t_parity:
            t_black += 1
        else:
            t_white += 1
    else:  # Aoki's turn (2nd, 4th, 6th steps)
        a_parity ^= parity
        if a_parity:
            a_black += 1
        else:
            a_white += 1

print(min(t_black, t_white), min(a_black, a_white))
0