問題一覧 > 通常問題

No.1665 quotient replace

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 : shiroha_F14shiroha_F14 / テスター : nok0nok0
0 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$ を書きます。」
ここで、このゲームは最初に整数が選べなくなった人の負けです。

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

入力

$N$
$A_1$ $A_2$ $\dots$ $A_n$

  • 入力はすべて整数
  • $1 \leq N \leq 10^6$
  • $1 \leq A_i \leq 10^6$ ($i$ は整数であり、$1 \leq i \leq N$)

出力

白羽君が勝つなら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もしくは右上の雲マークをクリックしてアカウントを作成してください。