QWERTY04 - TRIVIADOR

no tags 

TRIVIADOR

Triviador is a war between two Kings. A king can attack an enemy region at each step. When a king attacks a region, he conquers all the enemy regions connected to it. Every region is connected to the region immediately next to it and previous to it. The kings get alternate chances to attack. King1 gets the chance to attack first. Assume both kings are intelligent and find who will conquer the whole territory at the end of the war. It can be proved that one of the Kings can win for sure if he is intelligent!

 

Input Specification:

The first line is an integer t, denotes the number of test cases. In each test case the first line consists one integers denoting the number of regions in the territory. Then the description of each cell follows. Every region contains a character ‘X’ if it is owned by king1 or ‘O’ otherwise.


Output Specification:
For each test case output the result in a single line ‘X’ if king1 wins or ‘O’ if king2 wins.

 

Input Constraints:

T<=100

1<=regions<=100

 

Sample input:

 

3

 

8

XXXXOOOO

 

8

OXOXXXXO

 

8

XOXOXOXO



Sample Output:

X

O

X

 

 

Try the 2D version of this problem : http://spoj.com/problems/TWOKINGS/


hide comments
Mitch Schwartz: 2014-04-17 09:28:20

In the first example, for any move king1 can make, king2 can counter in a way that returns the board to its original state. Thus king2 can prevent king1 from winning indefinitely. This clearly contradicts "It can be proved that one of the Kings can win for sure if he is intelligent!".


Added by:cegprakash
Date:2012-01-09
Time limit:0.100s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All