結果

問題 No.1506 Unbalanced Pocky Game
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:00:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,025 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 102,096 KB
最終ジャッジ日時 2025-05-14 13:02:43
合計ジャッジ時間 6,358 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to compute the winner based on the Staircase Nim analogy
def solve():
    # Read N, the length of the sequence
    N = int(sys.stdin.readline())
    
    # Read the sequence A as a list of integers
    # The input provides space-separated integers on a single line.
    A = list(map(int, sys.stdin.readline().split()))

    # Calculate the Nim sum (Grundy value) of the game state.
    # The problem describes an impartial game. Based on analysis and comparison
    # with known games, this game appears equivalent to Staircase Nim.
    # In Staircase Nim, the game's state is equivalent to a Nim game
    # played on a subset of piles. Specifically, the piles correspond
    # to elements A_k where the index k has the same parity as N.
    # These are the indices k such that N-k is even.
    # We calculate the XOR sum of these elements A_k.
    
    nim_sum = 0
    
    # Iterate through the relevant indices k using 1-based indexing.
    # The indices are N, N-2, N-4, ..., down to 1 if N is odd, or 2 if N is even.
    # Start from k = N and decrement by 2 in each step as long as k is positive.
    current_idx_1based = N
    while current_idx_1based >= 1:
        # Access the element A_k. Since the list A is 0-indexed,
        # A_k corresponds to the element A[k-1].
        nim_sum ^= A[current_idx_1based - 1]
        
        # Move to the next relevant index by decrementing by 2
        current_idx_1based -= 2

    # Determine the winner based on the calculated Nim sum.
    # The Sprague-Grundy theorem states that for an impartial game under normal play convention:
    # - If the Nim sum (Grundy value) of the initial state is non-zero, the first player has a winning strategy.
    # - If the Nim sum is zero, the second player has a winning strategy.
    # In this game, Alice is the first player and Bob is the second player.
    if nim_sum > 0:
        print("Alice")
    else:
        print("Bob")

# Execute the solve function to process the input and print the result
solve()
0