3 Ball Story
All submissions for this problem are available.
You probably know the game where two players in turns take 1 to 3 balls from a pile. Looses the one who takes the last ball. We'll generalize this well known game. Assume that both of the players can take not 1, 2 or 3 balls, but k1, k2, …, km ones. Again we'll be interested in one question: who wins in the perfect game. It is guaranteed that it is possible to make next move irrespective to already made moves.
The first line contains number of test cases t <=200. For each test case input is of two lines. First line contains n and m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 50) — they are an initial amount of balls in the pile and an amount of numbers k1, …, km. The second line consists of the numbers k1, …, km, separated with a space (1 ≤ ki ≤ n).
Output 1, if the first player (the first to take balls) wins in a perfect game. Otherwise, output 2.
Input: 2 15 3 3 5 7 17 3 1 4 3 Output: 2 2
|Time Limit:||0.588235 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.