QWERTY04 - TRIVIADOR

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/


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

hide comments
2017-10-06 08:14:05 Sandeep N Menon
My code takes up 986 bytes
But while submitting it shows "Your solution is too long for this problem, the limit is 1000 bytes! "
2017-09-29 19:02:28
what does it mean by 406 in spoj ? my submission for this problem is getting verdict 406 and the color is green . may I assume that my solution has been accepted ?
2016-12-01 20:06:55 Ananda kumar P
8
OXOXXXXO

sol1:
step1:king1: OXOXXXXX
step2:king2: OOOXXXXX
step3:king1: XXXXXXXX
SOL1:KING1 WINS

sol2:
step1:king1: OXOXXXXX
step2:king2: OXOOOOOO
step3:king1: XXOOOOOO
step4:king2: OOOOOOOO
SOL2:KING2 WINS

if there is possibility for both the kings to win, which one should we consider.?
yes, the sample test case says O,but i am generally asking if there is a chance for both kings to win, what should be the output.

reply : It can be proved that one of the Kings can win for sure if he is intelligent!

Last edit: 2016-12-03 08:17:23
2015-03-24 03:45:19 Yaduvir Singh
during submission it giving 437. what is the meaning of this????
2014-10-15 20:51:04 cegprakash
Vukasin : A king's attack spreads like the poison in the blood.
2014-04-17 09:28:20 Mitch Schwartz
@Vukasin: The only thing I think is unclear in the problem statement is that the sentence "Every region is connected to the region immediately next or previous to it" seems to define "connected" as something different from what the author intended. This is cleared up by reading the below comments between the author and me. Other than that, if you think the problem is not written clearly enough, please ask a specific question about that.

Last edit: 2014-04-03 17:46:42
2014-04-17 09:28:20 Vukasin
Can someone please explain this game better than the explanation above? thanks in advance!
2014-10-15 20:44:11 cegprakash
7,7 case is actually a one move victory!
XXXXOOOO -> XXXXXXXX

You've considered the problem statement as conquering the neighbouring regions. It's specified as connected regions!

Last edit: 2012-09-14 05:32:16
2014-04-17 09:28:20 Mitch Schwartz
@cegprakash: I don't think so, or maybe there is some misunderstanding about the rules. King1 has four possible moves, easily inspected.

XXXXOOOO

Say the regions are labelled 1-8 starting from the left. Given as (King1's move, King2's counter), the counters are exhaustively: (5,6), (6,6), (7,7), (8,7 or 8). In each case the board returns to its original position.

For example the (7,7) case looks like

XXXXOOOO -> XXXXOXXX -> XXXXOOOO

Last edit: 2012-09-13 23:27:43
2014-04-17 09:28:20 cegprakash
@Mitch: King2 can't counter if King1 is intelligent

Last edit: 2012-09-13 21:37:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.