ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1282. Game Tree

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
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.

Исходные данные

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.

Результат

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

Примеры

исходные данныерезультат
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
Автор задачи: © 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).
Источник задачи: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003