HS09GAME - Strategy game

no tags 

Julia and Robert are playing a game, in which they pick up sticks from heaps. The game starts with n heaps, the i-th heap contains a[i] sticks. In each turn the players choose a heap and take away 2, 3 or 5 sticks from it (removed sticks do not return to the game). Julia starts the game making the first move. The one, who cannot make a move, loses the game, and the other player wins. Can you decide who will win the game, assuming that both players follow a perfect strategy ? If Julia is the winner, point out her winning move! If there are several possibilities for such a move, then choose the one in which the largest number of sticks is taken away. If there are still several such moves, choose the one, in which sticks are taken from the heap of the smallest number.

Input

An integer T, denoting the number of testcases (T <= 1000). Each testcase contains one integer n, the number of heaps, followed by n non-negative integers: a[1], a[2], ..., a[n], where a[i] is the number of sticks of the i-th heap.

Constraints:
1 <= n <= 1000,
0 <= a[i] <= 1000000000.

Output

Please consult the example below for a specification of the required output format. Print a blank line after each testcase.

Example

Input:
5
1
5
1
7
4
1 2 3 4
10
1 2 3 4 5 6 7 8 9 10
2
1000000 1000001

Output:
Julia wins.
Take 5 sticks from heap number 1.

Robert wins.

Julia wins.
Take 3 sticks from heap number 4.

Julia wins.
Take 5 sticks from heap number 6.

Julia wins.
Take 5 sticks from heap number 1.

hide comments
Mitch Schwartz: 2015-02-07 03:07:51

No, taking 3 sticks from heap number 3 is a losing move. Think about the term "perfect strategy"; you will need to understand that concept in order to understand the problem.

Sahil Sharma: 2015-02-07 02:33:31

@Mitch Schwartz
In that case, for the test case
4
1 2 3 4
Shouldn't the answer be
"Julia wins.
Take 3 sticks from heap number 3." ?
This is because according to problem specifications "If there are still several such moves, choose the one, in which sticks are taken from the heap of the smallest number." Hence since Julia could have won by taking 3 sticks from heap 4, should could as well have won by taking 3 from heap 3, and that move would seem to be the answer, according to the question. Am I interpreting any part wrongly?

Thanks

Krishna Mohan: 2015-02-06 13:46:41

Got two WA's for forgetting the '.' at the end xD

Mitch Schwartz: 2015-02-05 05:17:39

@Sahil Sharma: The first move. It is winning in the sense that it will lead to a win.

Sahil Sharma: 2015-02-05 05:06:23

Hi,

Can someone please explain what winning move means? Is it the first move or the last move? If it is the last move, then how can we determine what the last move would be? Since the 2nd player can chose whatever he wants to.
In the example
"1 2 3 4"
the answer IMO should be
"Julia wins.
Take 3 sticks from heap number 3."

This is because there exists a game wherein Julia can take 3 sticks from heap 3 as the last move. This happens when Julia takes 3 sticks from heap 4 as first move, Robert takes 2 sticks from heap 2 and finally Julia takes 3 sticks from heap 3. Please clarify.

Thanks

Robert Gerbicz: 2012-12-09 14:19:43

You need to solve all input sets to get accepted.

Aditya Pande: 2012-12-09 14:17:01

AC :)

Last edit: 2014-10-27 14:38:37

Added by:Robert Gerbicz
Date:2009-09-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:High School Programming League