All submissions for this problem are available.
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The goal of the game is to avoid being the player who ends up having no objects to remove.
Alice and Bob were playing nim during summer holidays. They both got bored after some time as the player who starts had higher probability of winning the game. So, they decided to change the rules of the game a bit. Luckily, they had a random number generator which generates a number k randomly(ofcourse). Now, the first k heaps are considered to be special heaps. For each non-empty special heap, either player can remove 0 object from that heap and count it as their move. But, the heap loses its speciality status once the zero move is performed(i.e., zero move is allowed only once per special heap).
Alice and Bob play g games. Given the random number k, number of heaps and number of objects in each heap, find who will win the game. It is also given that Alice starts every game and both the player play optimally.
The first line contains an integer g, denoting the number of games. Each game is described over two lines:
1. The first line contains two space separated integers n and k, denoting the number of heaps and the number generated by the random number generator.
2. The second line contains n space separated integers ai denoting number of objects in each heap.
For each game, print Alice or Bob depending on who wins.
- 1 ≤ g ≤ 30
- 1 ≤ n ≤ 10000
- 0 ≤ k ≤ n
- 1 ≤ ai ≤ 109
Input: 1 2 1 2 2 Output: Alice
Example case 1. Alice and Bob play g=1 games, First game:
There are n=2 heaps and first k=1 heap is a special heap. Alice will make zero move to the first heap. Now, that heap will become normal one. Now, Bob can either take one object or two object.
If Bob takes one object from any one of the heaps, Alice will take one object from the other heap so as to make one objects in both the heap. Now, Bob is forced to take one object from any heap. Then Alice can take the other object to leave Bob with no other possible moves.
If, Bob takes two objects from any one of the heaps, Alice can take the remaining two objects from the other heap leaving Bob with no further moves.
So, whatever way Bob chooses, Alice will win the match.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions