結果

問題 No.1579 New Type of Nim
ユーザー qwewe
提出日時 2025-05-14 13:01:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,381 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 70,412 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:02:45
合計ジャッジ時間 1,883 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm> // Required for std::min and std::max

/*
Problem Description:
Two players, P and Q, play a game with two piles of stones, initially containing A and B stones.
P starts first. Players take turns performing the following operation as long as at least one pile has stones:
1. Choose a pile with a positive number of stones.
2. Remove at least one stone from the chosen pile.

Turn change rule:
- After a move, if the number of stones in the two piles are DIFFERENT (A' != B'), the turn passes to the other player.
- After a move, if the number of stones in the two piles are the SAME (A' == B' > 0), the player who just moved gets to play again.

Winning condition:
The game ends when both piles are empty (0, 0). The player who made the last move (i.e., moved to (0, 0)) wins.
Both players play optimally. Determine if P wins or Q wins.

Constraints:
1 <= A, B <= 10^9
Input are integers.

Output:
Print 'P' if P wins, 'Q' if Q wins.


Game Analysis:
This is an impartial game with a modified turn structure. The standard approach for impartial games is using Sprague-Grundy theorem, but the non-standard turn rule complicates this. We analyze the game by identifying Winning (W) and Losing (L) states. A state is L if every move leads to a W state for the opponent, or leads to an L state for the current player (if they get an extra turn). A state is W if there exists at least one move leading to an L state for the opponent, or a move leading to a W state for the current player (if they get an extra turn).

Let's analyze small states (A, B), assuming A <= B without loss of generality due to symmetry.
(1, 1): Moves: (0, 1), (1, 0). Both result in unequal piles, turn passes. Opponent gets state (0, 1) or (1, 0). From (0, 1) or (1, 0), the only move is to (0, 0), winning. So opponent starts at a winning state. Thus, (1, 1) is an L state.
(1, 2): Moves:
  - (0, 2): Unequal (0 != 2). Turn passes. Opponent at (0, 2). Opponent moves to (0, 0) and wins.
  - (1, 1): Equal (1 == 1). Same player (P) plays again from (1, 1). Since (1, 1) is L, P loses.
  - (1, 0): Unequal (1 != 0). Turn passes. Opponent at (1, 0). Opponent moves to (0, 0) and wins.
All moves lead to P losing. Thus, (1, 2) is an L state.
(2, 2): Moves:
  - (0, 2) or (2, 0): Unequal. Turn passes. Opponent at (0, 2) or (2, 0). Opponent moves to (0, 0) wins.
  - (1, 2) or (2, 1): Unequal. Turn passes. Opponent at (1, 2) or (2, 1). We found (1, 2) is L. So opponent starts at L state and loses. P wins!
Since P has a winning move, (2, 2) is a W state.

Pattern Identification:
Through further analysis of states like (3, 3), (3, 4), (4, 4), etc., a pattern emerges for the Losing states (L-states).
A state (A, B) is an L-state if and only if, after sorting A and B such that $m = \min(A, B)$ and $M = \max(A, B)$:
- $m$ is odd, AND
- $M = m$ or $M = m+1$.

All other states are W-states (Winning states).

Explicitly, the L-states are of the form:
- $(2k-1, 2k-1)$ for $k \ge 1$. (Example: (1, 1), (3, 3), (5, 5), ...)
- $(2k-1, 2k)$ or $(2k, 2k-1)$ for $k \ge 1$. (Example: (1, 2), (2, 1), (3, 4), (4, 3), ...)

If the initial state (A, B) is an L-state, the first player P cannot force a win if the second player Q plays optimally. Q wins.
If the initial state (A, B) is a W-state, the first player P can force a win by always moving to an L-state for Q. P wins.


Algorithm based on the pattern:
1. Read A and B.
2. Find $m = \min(A, B)$ and $M = \max(A, B)$.
3. Check if $m$ is odd.
4. If $m$ is odd:
   Check if $M = m$ or $M = m+1$.
   If yes, the state is L. Output 'Q'.
   If no ($M > m+1$), the state is W. Output 'P'.
5. If $m$ is even:
   The state is always W. Output 'P'.

Example Checks:
Input: 1 2. m=1 (odd), M=2. M = m+1. State is L. Output Q. Correct.
Input: 4 3. m=3 (odd), M=4. M = m+1. State is L. Output Q. Correct.
Input: 12398742 83717408. m=12398742 (even). State is W. Output P. Correct.

The constraints $A, B \leq 10^9$ fit within `long long` in C++. The logic is computationally simple.
*/

int main() {
    // Improve input/output speed for competitive programming
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    long long A, B;
    // Read input values A and B
    std::cin >> A >> B;
    
    // Determine the minimum (m) and maximum (M) of A and B
    long long m = std::min(A, B);
    long long M = std::max(A, B);
    
    // Check the parity of the minimum value m based on the identified pattern for L/W states
    if (m % 2 != 0) { // If m is odd
        // If m is odd, check if the state (m, M) matches the pattern for Losing (L) states:
        // L states occur when the maximum value M is equal to m or m+1.
        if (M == m || M == m + 1) {
            // If it matches an L state pattern, the first player (P) loses, so the second player (Q) wins.
            std::cout << "Q" << std::endl;
        } else {
            // If m is odd but M > m+1, it doesn't match an L state pattern. It's a Winning (W) state.
            // The first player (P) wins.
            std::cout << "P" << std::endl;
        }
    } else { // If m is even
        // If the minimum value m is even, the state never matches the L state patterns according to our analysis.
        // Thus, it's always a Winning (W) state. The first player (P) wins.
        std::cout << "P" << std::endl;
    }
    
    return 0;
}
0