C - Candies Candidates Editorial /

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 \rfloory を超えない最大の整数を表す).取ったキャンディは他の皿に足したりせずすべて食べる.

行動ができなくなった方が負けで,負けなかった方が勝ちである.くろうさとしろうさのどちらに必勝法があるか?

制約

  • 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,しろうさに必勝法がある場合は White1 行に出力せよ.


入力例 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 にする行動を選ぶと,その後しろうさの行動によらず必ず勝つ方法が存在する.