結果

問題 No.1004 サイコロの実装 (2)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:10:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,629 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 54,620 KB
最終ジャッジ日時 2025-06-12 14:11:03
合計ジャッジ時間 2,997 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

def find_cycle(a_mod, b_mod, initial, m=6):
    seen = {}
    current = initial
    cycle = []
    while True:
        if current in seen:
            start_idx = seen[current]
            return cycle[:start_idx], cycle[start_idx:]
        seen[current] = len(cycle)
        next_val = (a_mod * current + b_mod) % m
        cycle.append(next_val)
        current = next_val
        if len(cycle) > 2 * m:
            return [], cycle

def compute_stones(a_mod, b_mod, initial, M):
    prefix, cycle = find_cycle(a_mod, b_mod, initial)
    if not cycle:
        return 0
    K = len(cycle)
    s = [0] * (K + 1)
    for i in range(K):
        s[i+1] = (s[i] + cycle[i]) % 2
    cycle_ones = sum(s[1:K+1])
    full_cycles = M // K
    rem = M % K
    rem_ones = sum(s[1:rem+1])
    total_ones = full_cycles * cycle_ones + rem_ones
    black = total_ones
    white = M - black
    return min(black, white)

def main():
    import sys
    a, b, x0, N = map(int, sys.stdin.readline().split())
    a_mod6 = a % 6
    b_mod6 = b % 6
    x0_mod6 = x0 % 6

    # Compute x1_mod6 and x2_mod6
    x1_mod6 = (a_mod6 * x0_mod6 + b_mod6) % 6
    x2_mod6 = (a_mod6 * x1_mod6 + b_mod6) % 6

    # Takahashi's parameters
    a_t = (a_mod6 * a_mod6) % 6
    b_t = (a_mod6 * b_mod6 + b_mod6) % 6
    initial_t = x1_mod6
    takahashi_score = compute_stones(a_t, b_t, initial_t, M=N)

    # Aoki's parameters
    a_a = (a_mod6 * a_mod6) % 6
    b_a = (a_mod6 * b_mod6 + b_mod6) % 6
    initial_a = x2_mod6
    aoki_score = compute_stones(a_a, b_a, initial_a, M=N)

    print(f"{takahashi_score} {aoki_score}")

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