All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Nim is a well-known combinatorial game, based on removing stones from piles. In this problem, we'll deal with a similar game, which we'll call Dual Nim. The rules of this game are as follows:
- Initially, there are N piles of stones, numbered 1 through N. The i-th pile contains ai stones.
- The players take alternate turns. If the bitwise XOR of all piles equals 0 before a player's turn, then that player wins the game.
- In his/her turn, a player must choose one of the remaining piles and remove it. (Note that if there are no piles, that player already won.)
Decide which player wins, given that both play optimally.
- The first line of the input contains an integer T - the number of test cases.
- The first line of each test case contains N - the number of piles.
- The following line contains N space-separated integers a1,..,aN - the sizes of piles.
For each test case, output one string on a separate line - "First" (without quotes) if the first player wins, "Second" (without quotes) if the second player wins.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 500
- 1 ≤ ai ≤ 500
Input: 3 4 1 2 4 8 3 2 3 3 5 3 3 3 3 3 Output: First Second Second
|Tags||cook68, easy, game-theory, nim, parity-obsv, xellos0|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.