問題一覧 > 通常問題

No.1665 quotient replace

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 158
作問者 : shiroha_F14 / テスター : nok0
3 ProblemId : 6855 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-03 23:24:30

この問題ではPythonの代わりにPyPyを使用することを推奨します。
一応PyPyではないPythonでも想定解でTLEしないことを確認できましたが、限界に近いです。

問題文

白羽君と黒羽君がとあるゲームをします。ゲームの概要は以下の通りです。

[9/3 23:23 訂正] 最初に、乱数生成機で生成した正の整数を、N 個ホワイトボードに書きます。そして、以下の操作を白羽君から交互に1回ずつ行います。以下の操作を白羽君から交互に1回ずつ行うことを繰り返します。
「これらの内で 1 ではない整数を一つ選びます。ここではそれを a とします。次に 2 以上である a の約数をひとつ挙げます。これを b とします。最後に、a をホワイトボードから消して、新たに a/b を書きます。」
ここで、このゲームは最初に整数が選べなくなった人の負けです。

白羽君はゲームを始めるために A1,A2,AN の計 N 個の数字をホワイトボードに書きました。この状態から、白羽君も黒羽君も自分が勝つために最適な行動を行います。
どちらが勝つかを出力してください。

入力

N
A1 A2  An

  • 入力はすべて整数
  • 1N106
  • 1Ai106 (i は整数であり、1iN)

出力

白羽君が勝つならwhiteと出力、
黒羽君が勝つならblackと出力してください。
注意:すべて小文字で出力してください。

サンプル

サンプル1
入力
3
6 9 10
出力
white

例えば、
6/6=1
9/3=3
10/2=5
3/3=1
5/5=1
以上で全ての数字が 1 になったので、6 手目である黒羽君の負けです。

サンプル2
入力
3
7 9 27
出力
black

サンプル3
入力
1
16
出力
white

最初に白羽君が 16/16=1 としてしまえば良いです。

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