printАнтагонистические игры

printДерево игры

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 — победа первого игрока, `-1` — победа второго игрока, 0 — ничья. Ваша задача — определить, кто выиграет, если оба противника следуют правильной стратегии.
Ввод
Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое `N\ (2\ ≤\ N\ ≤\ 1000)` – число узлов в дереве игры. Следующая `N-1` строка описывает узлы — одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья – третьего узла и т.д. Если узел является листом, первый символ строки — L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 — победа первого игрока, `-1` — победа второго, 0 — ничья). Если узел внутренний, то строка содержит N – первый символ, затем пробел и номер родительского узла.
Вывод
Выводится +1, если выигрывает первый игрок, `-1`, если второй, и 0 — в случае ничейного исхода.

Пример ввода 1

7     
N 1   
N 1   
L 2 -1
L 2 +1
L 3 +1
L 3 +1

Пример вывода 1

+1

Пример ввода 2

7     
N 1   
N 1   
L 2 -1
L 2 +1
L 3 +1
L 3 0 

Пример вывода 2

0

Пример ввода 3 (см. рис)

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

Пример вывода 3

+1
Источник: Central quarterfinal, NEERC, 2003
loading