(RankList for this Question)
6.2 Alice, Bob and Sticks
Alice and Bob are in a park and are bored as they have no one else to play with. They found a few sticks under a tree and then decided to play a game. They arranged the sticks in the increasing order of their heights. A player is allowed to choose a stick from the arrangement. On choosing the stick, all the sticks smaller than the selected stick, and the first occurrence of the stick in the arrangement, would be removed from the arrangement. An example: Suppose the arrangement is \([4, 5, 5, 5, 6, 6, 7, 7]\). If a player chooses \(5\), then the arrangement will look like \( [5, 5, 6, 6, 7, 7]\). The game goes on until there are no sticks left to be removed from the arrangement. The player who fails to remove a stick loses. Alice plays first. Both Alice and Bob play optimally. Given the input, you have to find whether Alice wins the game or Bob.
\(1 \leq t \leq 10\)
\(1 \leq n \leq 1000\)
\(1 \leq a[i] \leq 10000\)
You will be given \(t\) test cases, each having two lines:
The first line will have an integer \(n\), the number of sticks that Alice and Bob have found and have arranged in increasing order
The second line will contain \(n\) integers, arranged in increasing order. Each integer will represent the height of the stick. There can be more than one sticks having the same height.
For each test case, you have to output a string
If Alice wins, then you have to print “Alice”, without quotes
Else print “Bob”, without quotes.
3 3 17 17 23 23 39
The arrangement originally looks like [3, 3, 17, 17, 23, 23, 39]
Alice will choose the stick having height 39. So all the sticks having a height less than 39 will be removed from the arrangement, and also the first stick in the arrangement having height 39 will be removed. So there will be no sticks left in the arrangement. And therefore Bob loses the game.
3 3 17 17 23 23 39 39
Alice will choose the stick with height 39. Again all sticks having a height less than 39 will be removed. Also, the first stick in the sequence having height 39 will be removed. The resulting arrangement will be like:
Now, since there is only one stick left, Bob has no choice but to remove the stick only stick in the arrangement. This will leave Alice with no stick to remove, and so Alice loses the game.
Log In to solve the Question