問題一覧 > 通常問題

No.153 石の山

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 115
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
3 ProblemId : 13 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:46:46

問題文

$N$個の石が積まれた山が1つある。
A君とB君が交互に石を分けるゲームを行う。
分けるときに石を$2$つの山か$3$つの山に分ける。

$x$を正の整数とするとき、

$2x$個の石を$x$個と$x$個に分ける。
$2x+1$個の石を$x$個と$x+1$個に分ける。
$3x$個の石を$x$個と$x$個と$x$個に分ける、
$3x+1$個の石を$x$個と$x$個と$x+1$個に分ける。
$3x+2$個の石を$x$個と$x+1$個と$x+1$個に分ける。

以上の操作を選んでできるものとする。

例えば、最初に$5$個の石が積まれた山が$1$つあるとき、

ケース1:
まずA君が$2$個と$2$個と$1$個に分けるとする。
B君は$2$個を分けて$2$個と$1$個と$1$個と$1$個になる。
A君も$2$個を分けて$1$個と$1$個と$1$個と$1$個と$1$個にする。
B君は$1$個の石をこれ以上分けられない。

ケース2:
まずA君が$3$個と$2$個に分けたとする。
B君は$3$個の石を$2$個と$1$個に分け$2$個と$2$個と$1$個にできる。
A君が$2$個の石を分けて$2$個と$1$個と$1$個と$1$個になる。
B君も$2$個を分けて$1$個と$1$個と$1$個と$1$個と$1$個にする。
A君は$1$個の石をこれ以上分けられない。

ゲームは石を最後に分けられなくなったほうが負けである。
よって、この最初の石が$5$個のゲームの場合には、
ケース1のように先手のA君がまず石を3つに分ければA君が必ず勝てる。
A君が先手でA君もB君も勝つために最善を尽くすとき、
最初のNによってA君が勝つかB君が勝つかを判定せよ。

入力

N

石の数\( N(1 \le N \le 100) \)が与えられます。

出力

勝者の名前\( A \)または\( B \)を出力してください。
末尾に改行をしてください。

サンプル

サンプル1
入力
2
出力
A

A君が先に2つの石を1つずつに分けます。
すると、B君はこれ以上分けられないのでA君の勝ちです。

サンプル2
入力
1
出力
B

最初からA君は石を分けることができません。
よって、B君の勝ちです。

サンプル3
入力
5
出力
A

問題文と同じケースです。

サンプル4
入力
20
出力
A

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。