結果

問題 No.1004 サイコロの実装 (2)
ユーザー lam6er
提出日時 2025-03-20 20:46:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,150 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 82,684 KB
実行使用メモリ 82,880 KB
最終ジャッジ日時 2025-03-20 20:46:39
合計ジャッジ時間 5,085 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 18 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    a, b, x0, N = map(int, sys.stdin.readline().split())
    
    # Precompute mod6 LCG parameters
    a_mod6 = a % 6
    b_mod6 = b % 6
    x0_mod6 = x0 % 6
    initial_r_mod6 = (a_mod6 * x0_mod6 + b_mod6) % 6
    
    # Find cycle in mod6 LCG sequence
    seen = {}
    seq = []
    current_r = initial_r_mod6
    index = 1
    while current_r not in seen:
        seen[current_r] = index
        seq.append(current_r)
        next_r = (a_mod6 * current_r + b_mod6) % 6
        current_r = next_r
        index += 1
    
    # Determine cycle_start and cycle_length
    cycle_start = seen[current_r]
    cycle_length = len(seq) - cycle_start + 1  # since current_r is at position cycle_start-1 in seq (0-based)
    pre_cycle = seq[:cycle_start-1]  # elements before cycle starts
    cycle = seq[cycle_start-1:]      # elements in the cycle
    
    def get_r_mod6(k):
        if k <= len(pre_cycle):
            return pre_cycle[k-1]
        else:
            remaining = k - len(pre_cycle)
            pos = (remaining - 1) % cycle_length
            return cycle[pos]
    
    def process_player(total_steps, steps_k_func):
        white = 0
        black = 0
        state = 0
        sum_parity = 0  # sum mod2 of d_p's
        for step in range(1, total_steps + 1):
            k = steps_k_func(step)
            if k > N:
                break
            r_mod6 = get_r_mod6(k)
            r_parity = r_mod6 % 2
            d_p = 1 - r_parity  # die's parity (0 even, 1 odd)
            sum_parity = (sum_parity + d_p) % 2
            if sum_parity == 0:
                white += 1
            else:
                black += 1
        return white, black
    
    cnt_high = (N + 1) // 2
    cnt_low = N // 2
    
    # Process Takahashi (odd steps: 1,3,5,... -> k=1,3,5)
    white_t, black_t = process_player(cnt_high, lambda step: 2 * step - 1)
    # Process Aoki (even steps: 2,4,6,... -> k=2,4,6)
    white_a, black_a = process_player(cnt_low, lambda step: 2 * step)
    
    score_t = min(white_t, black_t)
    score_a = min(white_a, black_a)
    print(score_t, score_a)

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