Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
うさぎたちはキャンディを取り合うときも美しさにこだわります.
問題文
T 個のテストケースが与えられる.各テストケースで整数 N と整数 A_1, \ldots, A_N が与えられるので,以下の問に答えよ.
N 個の皿が並んでいて,i 番目の皿には最初キャンディが A_i 個置かれている.くろうさとしろうさがゲームをする.くろうさが先手で,交互に以下の行動をする.
行動.キャンディが 1 個以上置かれている皿を 1 個選び,その皿のキャンディの個数を x とする.その皿のキャンディの残り個数が x - 1 または \left\lfloor \frac{\sqrt{5} - 1}{2} x \right\rfloor になるようにキャンディを減らす (\lfloor y \rfloor は y を超えない最大の整数を表す).取ったキャンディは他の皿に足したりせずすべて食べる.
行動ができなくなった方が負けで,負けなかった方が勝ちである.くろうさとしろうさのどちらに必勝法があるか?
制約
- 1 \le T \le 100.
- 1 \le N \le 20.
- 1 \le A_i \le 10^{18} (1 \le i \le N).
入力
標準入力の 1 行目にテストケースの個数 T が与えられる.その後,T 個のテストケースがそれぞれ以下の形式で与えられる.
N A_1 \cdots A_N
出力
各テストケースについて,くろうさに必勝法がある場合は Black
,しろうさに必勝法がある場合は White
を 1 行に出力せよ.
入力例 1
2 2 5 9 4 20 15 10 5
出力例 1
Black White
1 番目のテストケースでは,くろうさの最初の行動としては以下のいずれかが可能である:
- 1 番目の皿のキャンディの残り個数を 5 - 1 = 4 にする (1 個食べる).
- 1 番目の皿のキャンディの残り個数を \left\lfloor \frac{\sqrt{5} - 1}{2} \cdot 5 \right\rfloor = 3 にする (2 個食べる).
- 2 番目の皿のキャンディの残り個数を 9 - 1 = 8 にする (1 個食べる).
- 2 番目の皿のキャンディの残り個数を \left\lfloor \frac{\sqrt{5} - 1}{2} \cdot 9 \right\rfloor = 5 にする (4 個食べる).
くろうさは,このうち例えば 2 番目の皿のキャンディの残り個数を 5 にする行動を選ぶと,その後しろうさの行動によらず必ず勝つ方法が存在する.