|Submit||All submissions||Best solutions||Back to list|
HS09NLG - Nim-like game
Consider the following game similar to Nim. Two players use N stacks of stones. A move consists of taking away a positive number of stones from a chosen stack. For each stack, the first move which involves taking stones from this stack, should leave at least one stone on the stack. In any subsequent move using this stack, a player can take at most twice as many stones as in the previous move on this stack.
Players take turns to move. The one who cannot make a move loses. Write a program which determines if for a given set of starting sizes of stacks the player who moves first can force a win.
In the first line of input there is one integer C (1 ≤C ≤ 1 000), meaning the number of test cases. Each test case is described in two lines. The first line of the two contains a number N (1 ≤N ≤ 1 000) and the second contains N numbers describing the sizes of stacks. No stack contains more than 300 stones.
For each testcase write out the number 1 if the starting player can always win, or 0 in the opposite case.
For solving this problem you will score 10 points.
|Added by:||Adam Dzedzej|
|Cluster:||Cube (Intel G860)|
|Languages:||ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TCL TEXT WHITESPACE|
|Resource:||High School Programming League (thanks to Talent Association)|