No.1579 New Type of Nim
タグ : / 解いたユーザー数 133
作問者 :
magsta
/ テスター :
startcpp
問題文
P 君と Q 君で石取りゲームをします。最初は山が 2 つあり、1 つ目の山には $A$ 個の石が、2 つ目の山には $B$ 個の石があります。
P 君と Q 君は、石が残っている山が存在する限り以下の操作を繰り返します。最初、操作する人は P 君です。操作した後、2 つの山にある石の数が同じでなければ、操作する人を交代します。
- 石が残っている山を 1 つを選び、好きな数だけ (1 個以上) その山にある石を取り除く。
2 つの山どちらにも石が存在しなくなったとき、最後に石を取った人が勝ちです。両者最善を尽くしたとき、どちらの人が勝つか判定してください。
P 君が勝つなら P を、Q 君が勝つなら Q を出力してください。
入力
$A\ \ B$
- $1 \leq A, B \leq 10^9$
- 入力はすべて整数である
出力
P か Q を出力し、最後に改行せよ。
サンプル
サンプル1
入力
1 2
出力
Q
P 君が 1 つ目の山を選んだ場合、石が 2 つある山が 1 つ残ることになり、Q 君は 2 つの石を取れば勝つことができます。
P 君が 2 つ目の山を選んで石を 2 つ取った場合、石が 1 つある山が 1 つ残ることになり、Q 君は 1 つの石を取れば勝つことができます。
P 君が 2 つ目の山を選んで石を 1 つ取った場合、石が 1 つある山が 2 つ残ることになり、操作する人は交代せず操作する人は P 君のままです。
これから P 君がいかなる操作をしても、石が 1 つある山が 1 つ残ることになり、Q 君は 1 つの石を取れば勝つことができます。
よって、P 君が最初からどのように操作しても Q 君は勝つことができます。
サンプル2
入力
4 3
出力
Q
サンプル3
入力
12398742 83717408
出力
P
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。