結果

問題 No.1208 anti primenumber game
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:55:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,042 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 106,636 KB
最終ジャッジ日時 2025-05-14 12:57:34
合計ジャッジ時間 5,202 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

def solve():
    # Read N and M from the first line of input.
    # N is the number of piles, M is the penalty for taking the last stone.
    line1 = sys.stdin.readline().split()
    N = int(line1[0])
    M = int(line1[1])
    
    # Read the initial number of stones in each pile A_i from the second line.
    A = list(map(int, sys.stdin.readline().split()))

    # Initialize the total score difference. This variable will store the final score
    # of the First player minus the score of the Second player.
    total_score_diff = 0

    # The game proceeds pile by pile from left to right.
    # We can analyze the game as a sum of independent subgames, one for each pile.
    # Let V(A) be the score difference achieved by the player whose turn it is to play
    # on a single pile of size A, assuming optimal play from both sides.
    # The total score difference for the entire game is the alternating sum of V(A_i),
    # because the first player starts on pile 1, second player on pile 2, first on pile 3, etc.
    # Total score difference = V(A_1) - V(A_2) + V(A_3) - V(A_4) + ...

    # We analyze the function V(A) based on the value of M.

    # Case 1: M = 0
    # If there is no penalty for taking the last stone (M=0), we derived that
    # the optimal strategy leads to V(A) = A for any pile size A >= 1.
    # The player whose turn it is when facing pile A will ensure they get a score difference of A.
    if M == 0:
        for i in range(N):
            # The value associated with pile A_i is simply A_i.
            val_Ai = A[i] 
            
            # If i is even (0-indexed), it's the (i+1)-th pile. Example: i=0 is 1st pile.
            # First player starts the subgame on this pile. Add val_Ai to total score difference.
            if (i % 2) == 0: 
                total_score_diff += val_Ai
            # If i is odd, it's the (i+1)-th pile. Example: i=1 is 2nd pile.
            # Second player starts the subgame on this pile. They achieve score difference val_Ai from their perspective.
            # From First player's perspective, this contributes -val_Ai to the total score difference.
            else: 
                total_score_diff -= val_Ai
    
    # Case 2: M >= 1
    # If there is a penalty M >= 1 for taking the last stone, we derived a different structure for V(A).
    # Specifically:
    # V(1) = 1 - M (The only move is to take the last stone, getting 1 point and M penalty).
    # V(A) = A - 2 + M for A >= 2 (The optimal move is typically to leave 1 stone for the opponent,
    # taking A-1 stones, resulting in this value).
    else: 
        for i in range(N):
            # Calculate V(A_i) based on A_i value
            val_Ai = 0
            if A[i] == 1:
                # If the pile has only 1 stone, apply the formula for V(1)
                val_Ai = 1 - M
            else: # A[i] >= 2
                # If the pile has 2 or more stones, apply the formula for V(A) with A >= 2.
                # Note that A_i and M can be large (up to 10^12), potentially resulting in large values.
                # Python's arbitrary precision integers handle this automatically.
                val_Ai = A[i] - 2 + M
            
            # Add or subtract V(A_i) based on whose turn it is to start on this pile.
            if (i % 2) == 0: # First player's turn for piles 1, 3, 5, ...
                total_score_diff += val_Ai
            else: # Second player's turn for piles 2, 4, 6, ...
                total_score_diff -= val_Ai

    # Determine the winner based on the final total score difference.
    # The problem states: Higher score wins. If scores are equal, Second player wins.
    # total_score_diff represents S_first - S_second.
    # First player wins if S_first > S_second, which means total_score_diff > 0.
    if total_score_diff > 0:
        print("First")
    # Otherwise (if S_first <= S_second, which means total_score_diff <= 0), Second player wins.
    else:
        print("Second")

# Execute the solve function to run the logic
solve()
0