Темы --> Информатика --> Алгоритмы --> Игры и выигрышные стратегии
    Простые игры(20 задач)
    Функция Гранди(6 задач)
---> 33 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Ответ считается как функции Гранди поддеревьев ($X_i + 1$)

Двое играют в следующую игру: имеется дерево с отмеченной вершиной (корнем). За ход игрок разрубает ветку (стирает ребро), причем из двух получившихся компонент связности остается только та, которая содержит корень, другая удаляется. Проигрывает тот, кто не может сделать ход. Определите, может ли выиграть первый игрок, и если да, то укажите любой из его выигрышных ходов.

Входные данные

В первой строке вводится 2 числа — количество вершин 1 < N ≤ 100000 и номер корня 1 ≤ RN. В следующих N – 1 строках идут пары чисел — описания ребер.

Выходные данные

В первой строке выведите число 1 или 2 – номер победителя при правильной игре.

Если побеждает первый игрок, то во второй строке выведите порядковый номер ребра во входных данных, которое ему достаточно разрубить первым ходом (число от 1 до N – 1).

Примеры
Входные данные
2 1
1 2
Выходные данные
1
1
Входные данные
5 2
1 3
3 4
2 3
2 5
Выходные данные
2
#2976
  
Источники: [ Командные олимпиады, ВКОШП, 2010, Задача D ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На планете Шелезяка катастрофа — запасы смазки подходят в концу. В связи с этим правительство решило организовать всепланетное соревнование, главный приз в котором — вагон смазочных материалов.

Соревнование проводится в несколько этапов, каждый из которых поделен на множество раундов. В каждом раунде принимают участие два игрока. Жюри предоставляет им большое целое число $n$. Затем игроки делают ходы по очереди. Первый ход первого игрока заключается в том, что игрок выписывает на специальном поле цифру, причем первым ходом запрещается выписывать ноль. В дальнейшем ход игрока заключается в том, что он приписывает справа к уже написанному числу произвольную цифру. Выигрывает тот, после чьего хода выписанное число больше или равно $n$.

Знаменитый ученый-робот «ЩК-33» считает, что результат игры легко предсказуем. Для доказательства он решил предоставить программу, которая определяет, кто выигрывает, если оба игрока действуют по оптимальной стратегии. К сожалению, из-за недостатка смазки, его манипуляторы вышли из строя, поэтому он просит вас о помощи.

Входные данные

Первая строка входного файла содержит целое число $n$ ($1 \le n \le 10^{100\,000}$). Это число не содержит ведущих нулей.

Выходные данные

Выведите «First», если при оптимальной игре выигрывает первый игрок, и «Second» в противном случае.

Примеры
Входные данные
22
Выходные данные
First
Входные данные
1
Выходные данные
First
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На листке записано в одну строку $N$ ($2 \leq N \leq 100$) целых положительных чисел. Каждое число не превышает 200. Играют двое. За каждый ход можно зачеркивать крайнее число либо слева, либо справа. Зачеркнутое число добавляется к очкам игрока. $N$ – четное. Игру начинает первый игрок. Необходимо вывести максимально возможную сумму очков для первого игрока при условии, что противник играет наилучшим образом..

Входные данные

В первой строке входного файла содержится одно целое число $N$ ($2 \leq N \leq 100$). В следующих $N$ строках записан исходный ряд чисел, по одному числу в строке.

Выходные данные

Выходной файл должен содержать единственное число – максимально возможную сумму очков для первого игрока при наилучшей игре второго игрока.

Примеры
Входные данные
6
4
7
2
9
5
2

Выходные данные
18
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Ретроанализ. Игра на циклическом графе.

Полицейский гонится за преступником по музею. В начале погони каждый из них находится в одной из $n$ комнат здания, некоторые комнаты соединены дверями.

Непосредственно перед началом погони в здании сработала сигнализация, и все двери закрылись. Музей использует сверхсовременную систему охраны - каждая дверь принадлежит одному из $k$ контуров безопасности. Полицейский может с помощью специального пульта управления блокировать и разблокировать все двери некоторого контура. При этом с целью обеспечения безопасности операции он может одновременно разблокировать не более одного контура. Полицейский впервые попал на такое ответственное задание, поэтому очень волнуется. Чтобы случайно не провалить операцию, каждый раз, перейдя из одной комнаты в другую, он блокирует все двери. При этом он очень инициативен и каждую минуту переходит из комнаты в комнату.

Благодаря системе камер, установленной в музее, полицейский в любой момент знает, где находится преступник. Однако поскольку система видеонаблюдения находится в состоянии тестовой эксплуатации, данная информация доступна также во всех комнатах, поэтому преступник тоже знает, где находится полицейский. Преступник наблюдает за всеми перемещениями полицейского. Каждый раз, после того как полицейский переходит из одной комнаты в другую, перед тем, как полицейский заблокирует двери, преступник тоже может перебежать в одну из соседних комнат. Разумеется, он может пробегать только через двери контура, который в настоящее время разблокирован.

Преступник хочет добраться до выхода (который находится в комнате с номером 1), а полицейский - поймать преступника. Если полицейский врывается в комнату, где находится преступник, то преступник не успевает убежать в другую комнату, и полицейский арестовывает его. Если преступник оказывается в комнате с выходом, то он немедленно покидает здание и скрывается в близлежащих районах.

Полицейский хочет как можно быстрее поймать преступника или, если это невозможно, то как можно дольше задержать его внутри здания, чтобы дождаться помощи. Преступник же хочет либо как можно быстрее сбежать, либо как можно дольше бегать от полицейского (если первое невозможно).

Определите, сможет ли полицейский поймать преступника, и если да, то какое минимальное количество перемещений из комнаты в комнату ему для этого потребуется. Если полицейский не сможет поймать преступника, то определите, сможет ли тот убежать, и если да, то сколько переходов из комнаты в комнату ему для этого потребуется.

Входные данные

Первая строка входного файла содержит три числа: $n$, $m$ и $k$ - количество комнат, дверей и контуров соответственно ($4 \le n \le 300$, $4 \le m \le 10\,000$, $1 \le k \le 10$). Следующие $m$ строк содержат по три целых числа --- для каждой двери указаны номера комнат, которые она соединяет, и номер контура безопасности, к которому она принадлежит.

Последняя строка входного файла содержит два различных целых числа - номера комнат, в которых в начале погони находятся полицейский и преступник, соответственно.

Выходные данные

На первой строке выходного файла выведите "Caught", если полицейскому удастся поймать преступника, "Escaped", если преступнику удастся убежать, и "Endless", если ни один из этих случаев не имеет место.

Если полицейскому удастся поймать преступника, или преступнику удастся сбежать, то на второй строке выходного файла выведите число переходов полицейского из комнаты в комнату при оптимальных действиях обеих сторон.

Примеры
Входные данные
4 3 2
1 2 2
3 2 1
4 3 1
4 2
Выходные данные
Caught
2
Входные данные
5 5 5
1 2 3
2 3 2
2 4 2
4 5 2
3 5 2
5 2
Выходные данные
Endless
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя с Андреем играют в интересную игру. Для этой игры им необходимо 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.

Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест