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.
Input
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.
Output
For each testcase write out the number 1 if the starting player can always win, or 0 in the opposite case.
Example
Input:
2
1
5
2
2 4
Output:
0
1
Scoring
For solving this problem you will score 10 points.
Added by: | Adam Dzedzej |
Date: | 2009-09-16 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp 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) |