No.1579 New Type of Nim
magsta
startcppProblem Statement
P and Q play a stone-taking game. Initially there are 2 piles: the first pile contains $A$ stones and the second pile contains $B$ stones.
As long as there is a pile with stones remaining, P and Q repeat the following operation. Initially, the player to operate is P. After an operation, if the numbers of stones in the 2 piles are not equal, the player to operate switches.
- Choose 1 pile with stones remaining, and remove any number (at least 1) of stones from that pile.
When neither of the 2 piles has any stones left, the player who took the last stone wins. Determine which player wins when both play optimally.
Print P if P wins, and Q if Q wins.
Input
$A\ \ B$
- $1 \leq A, B \leq 10^9$
- All inputs are integers
Output
Print P or Q, followed by a newline.
Sample
Sample 1
Input
1 2
Output
Q
If P chooses the first pile, 1 pile with 2 stones remains, and Q can win by taking the 2 stones.
If P chooses the second pile and takes 2 stones, 1 pile with 1 stone remains, and Q can win by taking the 1 stone.
If P chooses the second pile and takes 1 stone, 2 piles with 1 stone each remain, so the player to operate does not switch and remains P.
Whatever operation P performs from here, 1 pile with 1 stone remains, and Q can win by taking the 1 stone.
Therefore, Q can win no matter how P operates from the start.
Sample 2
Input
4 3
Output
Q
Sample 3
Input
12398742 83717408
Output
P
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。