結果

問題 No.2103 ±1s Game
ユーザー qwewe
提出日時 2025-05-14 12:57:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 1,000 ms
コード長 4,832 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 52,352 KB
最終ジャッジ日時 2025-05-14 12:58:54
合計ジャッジ時間 2,898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to compute (-1)^k efficiently
# (-1)^k is 1 if k is even, -1 if k is odd.
# This depends only on the parity of k.
def neg_one_pow_k(k):
  """Computes (-1)^k."""
  if k % 2 == 0:
    return 1
  else:
    return -1

def solve():
    # Read input values X, Y, K, P
    # X: number of +1 cards
    # Y: number of -1 cards
    # K: number of cards remaining at the end
    # P: target product for Alice (1 or -1)
    x, y, k, p = map(int, sys.stdin.readline().split())

    # Calculate total number of cards initially
    n = x + y
    # Calculate total number of turns (cards removed)
    t = n - k 

    # Based on problem constraints 1 <= K <= X+Y-1, we have T = X+Y-K >= 1.
    # The game always has at least one turn.

    # Calculate the term (-1)^K which appears in win conditions
    k_parity_term = neg_one_pow_k(k)

    # Determine the winner based on the number of turns T (parity determines who moves last)
    
    if t % 2 == 1: # T is odd, Alice makes the last move (turn T)
        # Alice moves last. She generally wins if she has control over the last move.
        # Bob wins only if he can force Alice into a specific state where her only move leads to Bob winning.
        # This forcing happens if Bob can empty one of the piles (either +1 or -1 cards) before Alice's last turn.
        
        # Bob makes TB = floor(T/2) moves.
        TB = t // 2

        # Bob wins if he can force x=0 (all +1 cards removed) AND this results in Bob winning.
        # Bob can force x=0 if the number of +1 cards X is less than or equal to the number of moves Bob makes (TB).
        # If x=0 is forced, the final state has K cards, all -1. So y' = K.
        # The product is (-1)^K. Bob wins if this product is not P.
        bob_wins_force_x0 = (x <= TB) and (k_parity_term != p)

        # Bob wins if he can force y=0 (all -1 cards removed) AND this results in Bob winning.
        # Bob can force y=0 if the number of -1 cards Y is less than or equal to TB.
        # If y=0 is forced, the final state has K cards, all +1. So y' = 0.
        # The product is (-1)^0 = 1. Bob wins if 1 != P, which means P must be -1.
        bob_wins_force_y0 = (y <= TB) and (p == -1)

        # If either condition allows Bob to force a win, Bob wins.
        if bob_wins_force_x0 or bob_wins_force_y0:
            print("Bob")
        else:
            # Otherwise, Alice can ensure she has a choice on her last turn, or any forced state leads to her win. Alice wins.
            print("Alice")

    else: # T is even, Bob makes the last move (turn T)
        # Bob moves last. He generally wins if he has control over the last move.
        # Alice wins only if she can force Bob into a specific state where his only move leads to Alice winning.
        # This forcing happens if Alice can empty one of the piles before Bob's last turn.

        # Alice makes TA = ceil(T/2) = T/2 moves (since T is even).
        TA = t // 2 

        # Check if Alice can force a win state.
        
        # Alice wins if she can force x=0 AND this results in Alice winning.
        # Alice can force x=0 if X <= TA.
        # Resulting state has y'=K. Alice wins if (-1)^K == P.
        alice_wins_force_x0 = (x <= TA) and (k_parity_term == p)
        
        # Alice wins if she can force y=0 AND this results in Alice winning.
        # Alice can force y=0 if Y <= TA.
        # Resulting state has y'=0. Alice wins if (-1)^0 == P, which means 1 == P.
        alice_wins_force_y0 = (y <= TA) and (p == 1)

        # Now determine the overall winner based on possibilities
        
        if x > TA and y > TA:
            # Alice cannot force x=0 nor y=0. Bob will have control on his last move. Bob wins.
            print("Bob")
        elif x <= TA and y <= TA:
            # Alice can choose whether to force x=0 or y=0.
            # She wins if *at least one* of these forced states leads to her win.
            if alice_wins_force_x0 or alice_wins_force_y0:
                print("Alice")
            else:
                # If both forced states lead to Bob winning, Alice cannot win. Bob wins.
                print("Bob")
        elif x <= TA: # This implies y > TA due to the first condition 'if x > TA and y > TA' failing
            # Alice can only force x=0. She wins if this forced state leads to her win.
            if alice_wins_force_x0:
                 print("Alice")
            else: # Forced x=0 leads to Bob winning. Bob wins.
                 print("Bob")
        else: # This implies y <= TA and x > TA
             # Alice can only force y=0. She wins if this forced state leads to her win.
            if alice_wins_force_y0:
                 print("Alice")
            else: # Forced y=0 leads to Bob winning. Bob wins.
                 print("Bob")

# Execute the solve function
solve()
0