ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Quarterfinal, Rybinsk, October 16 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Game Tree

Time limit: 1.0 second
Memory limit: 64 MB
A game for two players is determined by its tree. The competitors make moves in turn. The first competitor starts the game. The game ends up with either a draw, or a victory of one of the players. The leaf nodes of the tree of this game may have values equal to one of three numbers: “+1” – victory of the first competitor, “–1” – victory of the second competitor, “0” – draw.
Problem illustration
You have to find out who will win if both competitors follow the right strategy.

Input

The nodes of the tree are numbered with successive integer numbers. The root of the tree always has number 1.
The first line contains an integer N (1 < N ≤ 1000) – the number of the nodes in the game tree. Next N-1 lines describe the nodes – one line for each node (with exception for the first node). The second line will contain the description of the second node of the tree, the third line – the description of the third node, and so on.
If the node is a leaf of the tree, the first symbol of the line is “L”, followed by a space, then the number of the ancestor of this node goes, another space, and the result of the game (+1: victory of the first player, –1: victory of the second one, 0: draw).
If the node is an inner one then the line contains the first symbol “N”, a space character and the number of the ancestor of this node.

Output

contains “–1” if the second competitor wins, “+1” if so does the first and “0” if the result is a draw.

Samples

inputoutput
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 +1
+1
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 0
0
18
N 1
N 1
N 2
L 2 +1
N 3
L 3 +1
L 3 +1
L 4 -1
L 4 +1
N 4
N 6
L 6 -1
L 6 -1
L 11 -1
L 11 +1
L 12 +1
L 12 -1
+1
Problem Author: © Sergey G. Volchenkov, 2003(volchenkov@yandex.ru); Vladimir N. Pinaev, 2003(vpinaev@mail.ru; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (mkopachev@krista.ru).
Problem Source: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003
To submit the solution for this problem go to the Problem set: 1282. Game Tree