TEAMNIM - Team Nim

no tags 

Elayne and Nynaeve have teamed up against Aviendha and Birgitte to play a game of Nim. There are 3 piles of coins with X, Y and Z coins initially. In each turn the current player selects any non-empty pile, and removes any non-zero number of coins from that heap. Then play passes to the next player. The team whose player cannot make any valid move, loses, and the other team wins the game. Assume that all the players play optimally. Find out which team wins the game.

Input:
The first line contains T, the number of test cases. T test cases follow.
The first line of each test case contains 3 integers X,Y,Z.
This is followed by 4 lines containing the names "Elayne", "Nynaeve", "Aviendha", "Birgitte" (without quotes) in some order. This denotes the order of play. The player listed first gets the first turn, the next listed player gets the next turn and so on. After the player listed fourth, turn comes back to the player listed first and play continues.


Output:
Output T lines, each containing the winner's description for the corresponding test case.
Output "Elayne/Nynaeve" (without quotes) if Elayne and Nynaeve's team wins.
Output "Aviendha/Birgitte" (without quotes) if Aviendha and Birgitte's team wins.


Constraints:
T <= 50000
1 <= X,Y,Z <= 1000000000

Sample Input:
3
1 1 1
Elayne
Nynaeve
Aviendha
Birgitte
2 2 1
Aviendha
Elayne
Birgitte
Nynaeve
3 1 3
Elayne
Nynaeve
Birgitte
Aviendha

Sample Output:

Elayne/Nynaeve
Aviendha/Birgitte
Elayne/Nynaeve


Explanation:
In the first test case, the players do not really have any choice. Elayne, Nynaeve and Aviendha empty one pile each on their turn, and Birgitte cannot make any valid move after that.
In the second test case, Aviendha should empty the third pile of 1 coin. Now if Elayne takes 2 coins from a pile, Birgitte takes 2 coins from the other pile, leaving Nynaeve with no move. Or if Elayne takes 1 coin from a pile, Birgitte takes 1 coin from the other pile, and play will continue to leave Elayne with no move on her next turn.
In the third test case, Elayne and Nynaeve should each take 3 coins and empty a pile. Birgitte is forced to take the last coin leaving Aviendha with no move.


hide comments
Alex Anderson: 2012-04-01 01:20:51

I really liked this problem.


Added by:Rudradev Basak
Date:2012-03-30
Time limit:0.826s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem, used for ACM Indo-Pak Contest