No.1665 quotient replace
タグ : / 解いたユーザー数 160
作問者 :
shiroha_F14
/ テスター :
nok0
For this problem, we recommend using PyPy instead of Python.
We have confirmed that the intended solution does not get TLE even in non-PyPy Python, but it is close to the limit.
Problem Statement
Shiroha and Kuroha play a certain game. The outline of the game is as follows.
[Correction 9/3 23:23]
First, $N$ positive integers generated by a random number generator are written on a whiteboard. Then, the following operation is performed once each, alternately, starting with Shiroha. the players repeatedly take turns performing the following operation once each, starting with Shiroha.
"Choose one of these integers that is not $1$. Call it $a$. Next, name one divisor of $a$ that is at least $2$. Call it $b$. Finally, erase $a$ from the whiteboard and write $a/b$ in its place."
Here, the first player who cannot choose an integer loses this game.
To start the game, Shiroha wrote a total of $N$ numbers $A_1, A_2, … A_N$ on the whiteboard. From this state, both Shiroha and Kuroha act optimally in order to win.
Output which player wins.
Input
$N$ $A_1$ $A_2$ $\dots$ $A_n$
- All inputs are integers
- $1 \leq N \leq 10^6$
- $1 \leq A_i \leq 10^6$ ($i$ is an integer with $1 \leq i \leq N$)
Output
Output white if Shiroha wins,
and output black if Kuroha wins.
Note: Output everything in lowercase.
Sample
Sample 1
Input
3 6 9 10
Output
white
For example,
$6 / 6 = 1$
$9 / 3 = 3$
$10 / 2 = 5$
$3 / 3 = 1$
$5 / 5 = 1$
Now all the numbers have become $1$, so Kuroha, who has the $6$th move, loses.
Sample 2
Input
3 7 9 27
Output
black
Sample 3
Input
1 16
Output
white
Shiroha can simply make $16 / 16 = 1$ on the first move.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。