結果

問題 No.1004 サイコロの実装 (2)
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:49:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,511 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 81,924 KB
実行使用メモリ 54,536 KB
最終ジャッジ日時 2025-04-16 15:51:32
合計ジャッジ時間 2,697 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    a, b, x0, N = map(int, sys.stdin.readline().split())
    
    if N == 0:
        print(0, 0)
        return
    
    a_mod6 = a % 6
    b_mod6 = b % 6
    x0_mod6 = x0 % 6
    current_mod6 = (a_mod6 * x0_mod6 + b_mod6) % 6
    
    state_map = {}
    steps = []
    found_cycle = False
    cycle_start = 0
    cycle_length = 0
    
    t_black = 0
    t_white = 0
    a_black = 0
    a_white = 0
    t_parity = 0  # 0: even, 1: odd (initial position 0 is even)
    a_parity = 0
    
    for i in range(1, N + 1):
        current_parity = i % 2  # 1 for odd, 0 for even
        state = (current_mod6, current_parity)
        if state in state_map:
            cycle_start = state_map[state]
            cycle_length = i - cycle_start
            found_cycle = True
            break
        else:
            state_map[state] = i
        
        d = current_mod6 + 1
        d_mod2 = d % 2
        
        if i % 2 == 1:  # Takahashi's turn
            new_parity = (t_parity + d_mod2) % 2
            if new_parity == 1:
                t_black += 1
            else:
                t_white += 1
            t_parity = new_parity
        else:  # Aoki's turn
            new_parity = (a_parity + d_mod2) % 2
            if new_parity == 1:
                a_black += 1
            else:
                a_white += 1
            a_parity = new_parity
        
        current_mod6 = (a_mod6 * current_mod6 + b_mod6) % 6
        steps.append((d_mod2, i % 2))
    
    if not found_cycle:
        t_score = min(t_black, t_white)
        a_score = min(a_black, a_white)
        print(t_score, a_score)
        return
    
    remaining = N - (cycle_start - 1)
    Q = remaining // cycle_length
    R = remaining % cycle_length
    
    prev_t_black = t_black
    prev_t_white = t_white
    prev_a_black = a_black
    prev_a_white = a_white
    prev_t_parity = t_parity
    prev_a_parity = a_parity
    prev_current_mod6 = current_mod6
    
    cycle_t_black = 0
    cycle_t_white = 0
    cycle_a_black = 0
    cycle_a_white = 0
    cycle_t_parity = prev_t_parity
    cycle_a_parity = prev_a_parity
    cycle_current_mod6 = prev_current_mod6
    
    for k in range(cycle_length):
        i_in_cycle = cycle_start + k
        turn = (i_in_cycle % 2) == 1
        d = cycle_current_mod6 + 1
        d_mod2 = d % 2
        
        if turn:
            new_parity = (cycle_t_parity + d_mod2) % 2
            if new_parity == 1:
                cycle_t_black += 1
            else:
                cycle_t_white += 1
            cycle_t_parity = new_parity
        else:
            new_parity = (cycle_a_parity + d_mod2) % 2
            if new_parity == 1:
                cycle_a_black += 1
            else:
                cycle_a_white += 1
            cycle_a_parity = new_parity
        
        cycle_current_mod6 = (a_mod6 * cycle_current_mod6 + b_mod6) % 6
    
    total_cycle_t_black = cycle_t_black * Q
    total_cycle_t_white = cycle_t_white * Q
    total_cycle_a_black = cycle_a_black * Q
    total_cycle_a_white = cycle_a_white * Q
    
    remainder_t_black = 0
    remainder_t_white = 0
    remainder_a_black = 0
    remainder_a_white = 0
    remainder_t_parity = cycle_t_parity
    remainder_a_parity = cycle_a_parity
    remainder_current_mod6 = cycle_current_mod6
    
    for k in range(R):
        i_in_cycle = cycle_start + (cycle_length * Q) + k
        turn = (i_in_cycle % 2) == 1
        d = remainder_current_mod6 + 1
        d_mod2 = d % 2
        
        if turn:
            new_parity = (remainder_t_parity + d_mod2) % 2
            if new_parity == 1:
                remainder_t_black += 1
            else:
                remainder_t_white += 1
            remainder_t_parity = new_parity
        else:
            new_parity = (remainder_a_parity + d_mod2) % 2
            if new_parity == 1:
                remainder_a_black += 1
            else:
                remainder_a_white += 1
            remainder_a_parity = new_parity
        
        remainder_current_mod6 = (a_mod6 * remainder_current_mod6 + b_mod6) % 6
    
    t_black = prev_t_black + total_cycle_t_black + remainder_t_black
    t_white = prev_t_white + total_cycle_t_white + remainder_t_white
    a_black = prev_a_black + total_cycle_a_black + remainder_a_black
    a_white = prev_a_white + total_cycle_a_white + remainder_a_white
    
    t_score = min(t_black, t_white)
    a_score = min(a_black, a_white)
    print(t_score, a_score)

if __name__ == "__main__":
    main()
0