--->
20 задач
<---
Источники
Петя получил золотую медаль на IOI, за что от правительства ему положена благодарность в виде шоколадки. На данный момент имеется N видов шоколадок, которые производит государственная шоколадная фабрика. У каждой шоколадки есть стоимость. Кроме того, у каждого вида, кроме шоколадки "Юлька", есть вид-прародитель. Известно, что прародителем может быть только шоколадка, которая была выпушена хронологически раньше. Исторически самый первый вид - "Юлька". Чиновник и Петя выбирают шоколадку ему в подарок. При этом цель первого - сэкономить, второго - получить настолько дорогую шоколадку, насколько это возможно. Начинается выбор с "Юльки". Петя за ход либо берет текущую шоколадку, либо меняет свой выбор на шоколадку-потомка (если это возможно). Чиновнику же кажется, что позже выпущенные виды хуже и дешевле, поэтому он меняет выбор на шоколадку-потомка (если это возможно), либо покупает Пете шоколадку (если потомков нет). Они ходят по очереди, Петя - первый. Определите, на шоколадку какой стоимости может претендовать Петя.
Сначала вводится число 0 < N <= 200000 - количество видов. "Юлька" имеет номер 1. Далее идут N строк с парами чисел 0 <= Pi <= N - номер сорта-предка (для шоколадки "Юлька" указан 0, у остальных Pi > 0) и 0 < Ci <= 1000000000 - стоимость i-го сорта.
Выведите стоимость шоколадки, которую Петя может себе гарантировать при правильных действиях.
8 0 4 5 3 1 2 5 1 1 5 4 8 3 6 3 7 | 6 |
Двое играют в следующую игру: имеется дерево с отмеченной вершиной (корнем). За ход игрок рузрубает ветку (стирает ребро), причем из двух получившихся компонент связности остается только та, которая содержит корень - остальная отваливается вместе с корнем. Проигрывает тот, кто не может сделать ход. Определите, может ли выиграть первый игрок, и если да, то любой из его выигрышных ходов.
В первой строке вводится 2 числа - количество вершин 1 < N <= 100000 и номер корня 1 <= R <= N. В следующих N-1 строках идут пары чисел - описания ребер.
Выведите 1 или 2 - номер победителя при правильной игре. Если побеждает первый игрок, то выведите порядковый номер ребра во входных данных, которое ему достаточно разрубить первым ходом (число от 1 до N-1).
То же, что и Дровосек - 1, только граф произвольный, после хода выживают те компоненты связности, которые содержат корни (изначально в каждой компоненте связности есть хотя бы один корень).
В первой строке задаются 3 числа - количество вершин 1 < N <= 10000, число ребер 0 <= M <= 100000 и количество корней 1 <= R <= N. В следующей строке идут различные числа 1 <= Ri <= N - номера вершин, являющихся корнями. В следующих M строках идут пары чисел - описания ребер.
Выведите одно число - номер игрока-победителя.
Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?
Вводится одно натуральное число — \(N\) ( 1≤ \(N\) ≤ 10000) начальное количество спичек в кучке.
Выведите 1, если выигрывает первый игрок (тот, кто ходит первым), или 2, если выигрывает второй игрок.
2
1
3
2
Слава и Оля играют в игру умножения - умножают целое число \(P\) на одно из чисел от 2 до 9. Слава всегда начинает с \(P\) = 1, делает умножение, затем число умножает Оля, затем Слава и т.д. Перед началом игры им задают случайное число \(N\), и победителем считается тот, кто первым получит \(P\) >= \(N\). Определить, кто выиграет при заданном \(N\), если оба играют наилучшим образом.
В первой строке находится единственное число \(N\). 2 <= \(N\) <= 4 294 967 295.
Выводится одна строка - "Stan wins.", если победит Слава, или "Ollie wins.", если победит Оля.
10
Ollie wins.
19
Stan wins.