結果

問題 No.1004 サイコロの実装 (2)
ユーザー lam6er
提出日時 2025-04-15 22:25:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,698 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 81,868 KB
実行使用メモリ 54,436 KB
最終ジャッジ日時 2025-04-15 22:27:41
合計ジャッジ時間 2,878 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 25
権限があれば一括ダウンロードができます

ソースコード

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

    # Find the cycle in mod6
    current = x0_mod6
    visited = {}
    sequence = []
    while current not in visited:
        visited[current] = len(sequence)
        sequence.append(current)
        current = (a_mod6 * current + b_mod6) % 6
    start_idx = visited[current]
    cycle = sequence[start_idx:]
    T = len(cycle)
    if T == 0:
        T = len(sequence)
        cycle = sequence

    # Generate B (parity bits for the cycle)
    B = []
    for x in cycle:
        parity = 1 if (x % 2 == 0) else 0
        B.append(parity)

    # Generate Th_bitlist and Ta_bitlist
    Th = T // 2 if T % 2 == 0 else T
    Th_bitlist = []
    for i in range(Th):
        pos = (2 * i) % T
        Th_bitlist.append(B[pos])

    Ta = T // 2 if T % 2 == 0 else T
    Ta_bitlist = []
    for i in range(Ta):
        pos = (2 * i + 1) % T
        Ta_bitlist.append(B[pos])

    # Function to compute black stones using the cycle efficiently
    def compute_black(bitlist, n):
        if n == 0:
            return 0
        len_bitlist = len(bitlist)
        sum_mod = 0
        black = 0
        remaining = n
        seen = {}
        while remaining > 0:
            if sum_mod in seen:
                prev_remaining, prev_black, prev_sum = seen[sum_mod]
                cycle_remaining = prev_remaining - remaining
                cycle_black = black - prev_black
                if cycle_remaining <= 0:
                    break
                num_cycles = remaining // cycle_remaining
                black += cycle_black * num_cycles
                remaining -= num_cycles * cycle_remaining
                seen = {}
            else:
                seen[sum_mod] = (remaining, black, sum_mod)
                process = min(remaining, len_bitlist)
                for i in range(process):
                    bit = bitlist[i]
                    sum_mod = (sum_mod + bit) % 2
                    if sum_mod == 1:
                        black += 1
                remaining -= process
                if process == len_bitlist:
                    sum_mod = sum_mod % 2
                else:
                    break
        return black

    takahashi_black = compute_black(Th_bitlist, N)
    aoki_black = compute_black(Ta_bitlist, N)

    takahashi_white = N - takahashi_black
    aoki_white = N - aoki_black

    takahashi_score = min(takahashi_black, takahashi_white)
    aoki_score = min(aoki_black, aoki_white)

    print(takahashi_score, aoki_score)

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