AtCoder Beginner Contest 027

C - 倍々ゲーム


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君と青木君が以下のような二人ゲームで勝負する。

まず、正の整数 N が与えられる。 また、変数 x1 に初期化する。高橋君から始め、高橋君と青木君が交互に次の操作を行う。

  • x の値を 2x または 2x+1 に置き換える。

xN よりも大きくなったとき、最後に操作を行った人が負けである。

二人が最善を尽くすとき、どちらが勝つか求めよ。


入力

入力は以下の形式で標準入力から与えられる。

N
  • 1 行目には、正の整数 N (1≦N≦10^{18}) が与えられる。

出力

高橋君が勝つならば Takahashi を、青木君が勝つならば Aoki1 行に出力せよ。 出力の末尾には改行を入れること。


入力例1

1

出力例1

Aoki

高橋君がどのように操作を行っても x>1 となってしまう。


入力例2

5

出力例2

Takahashi

高橋君が x=3 とすると、青木君がどのように操作を行っても x>5 となってしまう。


入力例3

7

出力例3

Aoki

入力例4

10

出力例4

Takahashi

入力例5

123456789123456789

出力例5

Aoki

N32 bit 整数型に収まらない。


Submit提出する