--->
6 задач
<---
Источники
Двое играют в такую игру: перед ними лежит шоколадка размера NxM. За ход можно разломить имеющийся кусок шоколадки вдоль одной из сторон на 2 "непустых".
Однако, нельзя разламывать куски размером не больше, чем \(1 \times k\) (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части). Таким образом, нельзя разламывать куски размером \(1 \times 1\), \(1 \times 2\), \(\ldots\), \(1 \times k\), а остальные куски разламывать можно.
Проигрывает тот, кто не может сделать ход. Определите, кто же станет победителем в игре, если известны начальные размеры шоколадки.
Вводятся целые числа 0 < N, M, K <= 100.
Вывести 1 или 2 - номер игрока, который выиграет при правильной игре.
1 1 1
2
2 2 1
1
В игру крестики-крестики играют на поле размером 1 × N. Два игрока ходят по очереди. На каждом ходу игрок выбирает одну свободную ячейку и ставит там крестик. Если после его хода оказывается три крестика подряд, то он побеждает.
По известному N вам необходимо определить какой игрок победит при оптимальной игре обоих игроков.
Входной файл содержит одно число N (3 ≤ N ≤ 2000).
Выведите 1, если побеждает первый игрок и 2, если побеждает второй игрок.
3
1
6
2
Пусть G=(V, E) – произвольный ориентированный граф. Для каждой вершины x этого графа введем множество Next(x) как множество всех вершин, в которые ведут дуги, выходящие из вершины x.
Пусть F – функция, принимающая целые неотрицательные значения, определенная на вершинах графа G. Функция F называется функцией Гранди, если для каждой вершины x графа G выполняется условие F(x)=min{n≥0|n≠F(y) ни для какой вершины y из Next(x)}.
Рассмотрим класс ориентированных графов, у которых в каждую вершину входит ровно одна дуга. Напишите программу, которая получает на вход некоторый граф из описанного выше класса и находит функцию Гранди для этого графа, если она существует.
Входной файл содержит описание ориентированного графа. В первой строке файла находится целое число N (2 ≤ N ≤ 100000), равное количеству вершин графа. В i-й из следующих N строк находится одно целое число Pi (1 ≤ Pi ≤ N; Pi ≠ i), равное номеру вершины, из которой выходит та дуга, которая ведет в вершину с номером i.
Eсли для графа, описанного во входном файле, не существует функции Гранди, то выходной файл должен содержать одну строку со словом "NO". В противном случае, файл должен состоять из N строк, в i-й из которых должно быть записано одно целое число Fi – значение найденной функции Гранди для вершины с номером i. Если существует несколько функций Гранди для графа, описанного во входном файле, то выведите любую из них.
4 2 4 4 1
YES
3 3 1 2
NO
4 4 3 2 1
YES
Двое играют в следующую игру: имеется дерево с отмеченной вершиной (корнем). За ход игрок разрубает ветку (стирает ребро), причем из двух получившихся компонент связности остается только та, которая содержит корень, другая удаляется. Проигрывает тот, кто не может сделать ход. Определите, может ли выиграть первый игрок, и если да, то укажите любой из его выигрышных ходов.
В первой строке вводится 2 числа — количество вершин 1 < N ≤ 100000 и номер корня 1 ≤ R ≤ N. В следующих N – 1 строках идут пары чисел — описания ребер.
В первой строке выведите число 1 или 2 – номер победителя при правильной игре.
Если побеждает первый игрок, то во второй строке выведите порядковый номер ребра во входных данных, которое ему достаточно разрубить первым ходом (число от 1 до N – 1).
2 1 1 2
1 1
5 2 1 3 3 4 2 3 2 5
2
Петя с Андреем играют в интересную игру. Для этой игры им необходимо k шоколадок, каждая из которых имеет форму прямоугольника i-ая из них имеет размер wi на hi долек.
Петя с Андреем ходят по очереди, за один ход игрок должен взять со стола одну шоколадку, разломать ее на две неравных непустых части, и их обе положить обратно на стол. При этом обе получающиеся части должны иметь форму прямоугольника, длины сторон которого выражаются целым числом долек.
Первый ход в этой игре делает Петя. Проигрывает игрок, который не может сделать ход. Победитель после этого получает весь шоколад, лежащий на столе.
Ваша задача — определить, кто из игроков выиграет при оптимальной игре обоих.
Входной файл содержит несколько наборов входных данных. Первая строка входного файла содержит количество T наборов входных данных (1 ≤ T ≤ 1000).
Каждый набор входных данных описывается следующим образом. Первая строка описания содержит число k (1 ≤ k ≤ 100) — количество шоколадок, лежащих на столе в начале игры. Последующие k строк описывают шоколадки: i-ая из этих строк содержит два числа: wi и hi — размеры соответствующей шоколадки (1 ≤ wi, hi ≤ 100).
Для каждого набора входных данных выведите ответ. Следуйте формату, приведенному в примерах.
3 1 1 1 1 3 1 2 1 1 3 1
Game 1: Andrew wins. Game 2: Petr wins. Game 3: Petr wins.