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

## Четвертьфинал, Рыбинск, 16 октября 2003

Соревнование завершено

## I. 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.
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
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1282. Game Tree