結果

問題 No.1004 サイコロの実装 (2)
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:50:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,097 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 81,820 KB
実行使用メモリ 54,548 KB
最終ジャッジ日時 2025-04-16 00:52:37
合計ジャッジ時間 2,877 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    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
    s0 = x0 % 6

    # Find the cycle of x_i mod6
    s_list = [s0]
    index_map = {s0: 0}
    while True:
        next_s = (a_mod6 * s_list[-1] + b_mod6) % 6
        if next_s in index_map:
            start = index_map[next_s]
            pre_cycle = s_list[:start]
            cycle = s_list[start:]
            break
        else:
            index_map[next_s] = len(s_list)
            s_list.append(next_s)

    # Generate p for pre_cycle and cycle
    pre_p = [1 - (s % 2) for s in pre_cycle]
    cycle_p = [1 - (s % 2) for s in cycle]

    # Function to get player's sequence
    def get_player_sequence(pre_p, cycle_p, player):
        pre_seq = []
        for i in range(len(pre_p)):
            if i % 2 == player:
                pre_seq.append(pre_p[i])
        cycle_seq = []
        for i in range(len(cycle_p)):
            if i % 2 == player:
                cycle_seq.append(cycle_p[i])
        # Find minimal cycle for cycle_seq
        if not cycle_seq:
            return pre_seq, cycle_seq
        min_period = len(cycle_seq)
        for period in range(1, len(cycle_seq) + 1):
            valid = True
            for i in range(len(cycle_seq)):
                if cycle_seq[i] != cycle_seq[i % period]:
                    valid = False
                    break
            if valid:
                min_period = period
                break
        return pre_seq, cycle_seq[:min_period]

    pre_high, cycle_high = get_player_sequence(pre_p, cycle_p, 0)
    pre_low, cycle_low = get_player_sequence(pre_p, cycle_p, 1)

    # Calculate for Takahashi (high)
    total_high = N
    current_xor_high = 0
    black_high = 0
    white_high = 0

    # Process pre_high
    len_pre_high = len(pre_high)
    if len_pre_high > 0:
        take = min(total_high, len_pre_high)
        for p in pre_high[:take]:
            current_xor_high ^= p
            if current_xor_high:
                black_high += 1
            else:
                white_high += 1
        total_high -= take
        if total_high == 0:
            pass
        else:
            pass

    if total_high > 0:
        len_cycle_high = len(cycle_high)
        if len_cycle_high == 0:
            pass
        else:
            full_cycles = total_high // len_cycle_high
            remainder = total_high % len_cycle_high

            cycle_xor = 0
            cycle_black = 0
            cycle_white = 0
            temp_xor = current_xor_high
            for p in cycle_high:
                temp_xor ^= p
                if temp_xor:
                    cycle_black += 1
                else:
                    cycle_white += 1
            cycle_xor = temp_xor ^ current_xor_high

            black_high += cycle_black * full_cycles
            white_high += cycle_white * full_cycles

            current_xor_after_cycles = current_xor_high
            if full_cycles % 2 == 1:
                current_xor_after_cycles ^= cycle_xor

            temp_xor = current_xor_after_cycles
            for p in cycle_high[:remainder]:
                temp_xor ^= p
                if temp_xor:
                    black_high += 1
                else:
                    white_high += 1

    # Calculate for Aoki (low)
    total_low = N
    current_xor_low = 0
    black_low = 0
    white_low = 0

    # Process pre_low
    len_pre_low = len(pre_low)
    if len_pre_low > 0:
        take = min(total_low, len_pre_low)
        for p in pre_low[:take]:
            current_xor_low ^= p
            if current_xor_low:
                black_low += 1
            else:
                white_low += 1
        total_low -= take
        if total_low == 0:
            pass
        else:
            pass

    if total_low > 0:
        len_cycle_low = len(cycle_low)
        if len_cycle_low == 0:
            pass
        else:
            full_cycles = total_low // len_cycle_low
            remainder = total_low % len_cycle_low

            cycle_xor = 0
            cycle_black = 0
            cycle_white = 0
            temp_xor = current_xor_low
            for p in cycle_low:
                temp_xor ^= p
                if temp_xor:
                    cycle_black += 1
                else:
                    cycle_white += 1
            cycle_xor = temp_xor ^ current_xor_low

            black_low += cycle_black * full_cycles
            white_low += cycle_white * full_cycles

            current_xor_after_cycles = current_xor_low
            if full_cycles % 2 == 1:
                current_xor_after_cycles ^= cycle_xor

            temp_xor = current_xor_after_cycles
            for p in cycle_low[:remainder]:
                temp_xor ^= p
                if temp_xor:
                    black_low += 1
                else:
                    white_low += 1

    score_high = min(black_high, white_high)
    score_low = min(black_low, white_low)
    print(score_high, score_low)

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