--->
33 задач
<---
Источники
Дима и Катя продолжают играть в игру, описанную в задаче A (задача №1972) . В данный момент каждый из них уже сделал (k-1) ходов. При этом Катя, с ее феноменальной памятью, прекрасно помнит, какие карточки использовал Дима (и, конечно же, Катя знает какие карточки использовала она сама).
Определите оптимальный k-й ход для Кати (указание: используйте маскиминный критерий).
Cначала вводится число N (натуральное, не менее 2 не превосходит 20), затем вводится N строк по N чисел в каждой – таблица сумм выигрышей для Кати. Числа в таблице целые, по модулю не превосходят 1000. Затем вводится число k – номер текущего хода (натуральное, не менее двух, не превосходит N). После этого следуют две строки по (k-1) числу в каждой: первая строка – карточки, которые уже использовал Дима, вторая строка – карточки, которые использовала Катя. Гарантируется, что описания использованных карточек корректны (натуральные числа, не превосходят N, никакое число в строке не повторяется).
Выведите единственное число – оптимальный k-й ход для Кати. В случае, если оптимальных ходов несколько – выведите тот, где используется карточка с наибольшим номером.
2 -1 8 9 -6 2 1 1
2
Андрей играет в следующую экономическую игру: дана шахта, добывающая k единиц золота за 1 ход. В начале игры количество золота у Андрея равно нулю. В начале каждого хода можно принять решение о постройке одной (или более) новых шахт. Постройка каждой шахты занимает T ходов и требует S единиц золота (золото вычитается у игрока в момент принятия решения о постройке новой шахты). Игра заканчивается через N ходов. Определите максимальное количество единиц золота, с которым Андрей может завершить игру.
Вводятся числа k (натуральное, не превышает 100), T (натуральное, не превосходит 10), S (натуральное, не превосходит 10000) и N (натуральное, не превосходит 100).
Выведите единственное число – максимальное количество единиц золота, которое можно получить за N ходов. Гарантируется, что результат не превышает 1018.
Комментарий к примеру тестов
В начале игры количество золота равно нулю, следовательно начать строительство можно только со второго хода; строительство будет длиться 5 ходов (ходы со второго по шестой), поэтому к концу 6 хода новые шахты только будут построены, но еще не добудут нового золота. Исходя из этого решение строить новые шахты будет неоптимальным. Решение строить новые шахты меньше чем за 5 ходов до конца игры также будет неоптимальным.
100 5 50 6
600
Дима и Катя играют в следующую игру: на доске 5x5 клеток установлено несколько трусливых пешек. Трусливая пешка – это фигура, для взятия которой не обязательно перемещаться на ее клетку, а достаточно просто создать для нее угрозу.
Игроки ходят по очереди. Первый ход делает Катя, у которой есть единственная ладья. За один ход можно поставить ладью в любую незанятую клетку шахматной доски. При этом все трусливые пешки, для которых создана угроза (то есть находящиеся на той же горизонтали или вертикали, что и ладья) – снимаются с доски. Обратите внимание, что трусливая пешка не защищает другую от угрозы. Следующий ход делает Дима. Он может поставить на доску одну новую трусливую пешку в любую незанятую и не находящуюся в данный момент под угрозой клетку. Затем снова ходит Катя и т.д.
Игра продолжается до наступления одного из событий:
1. Катя сделала N ходов и при этом на доске осталась хотя бы одна пешка – в этом случае выиграл Дима;
2. После некоторого хода Кати на доске не осталось ни одной пешки – в этом случае выигрывает Катя.
3. Кто-то из игроков не может сделать следующий ход. В этом случае присуждается ничья.
Определите, кто из игроков выиграет при правильной игре.
Сначала вводится 5 строк по 5 чисел в каждой – начальное расположение трусливых пешек на доске. Наличие пешки в какой-то клетке обозначается числом 1, отсутствие пешки – числом 0. Затем вводится число N (натуральное, не превышает 15) – максимально допустимое количество ходов Кати. Гарантируется, что Катя сможет сделать первый ход (изначально на доске есть хотя бы одна незанятая клетка).
Выведите число 1 – если выигрывает Катя; число 2 – если выигрывает Дима или число 3 – если игра заканчивается вничью.
Комментарий к примеру тестов
1. У Кати есть единственный способ сделать первый ход, после которого Дима сделать ход не может, так как все свободные клетки будут находиться под угрозой.
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
3
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
3
Ограничение по времени: 4 секунды
Андрей и Антон играют в следующую игру: на прямоугольную доску размера MxN, некоторые клетки в которой заняты "нейтральными" фигурами, игроки по очереди выставляют белых и черных шахматных королей (ход можно делать только в свободные клетки). Двигать или убирать уже поставленного короля нельзя. Убирать или перемещать "нейтральные" фигуры нельзя. Также нельзя ставить короля в клетку, которая является соседней с королем противника по горизонтали, вертикали или диагонали. Проигрывает тот, кто не сможет сделать следующий ход.
Определите, кто выиграет при правильной игре.
Вводятся числа M и N (натуральные, не превышают 5). Затем вводится число k – количество "нейтральных" фигур на доске (целое, положительное, не превышает количества клеток доски). Затем следует k строк по 2 числа в каждой – номера строки и столбца, где находится данная "нейтральная" фигура. Гарантируется, что хотя бы первый игрок сможет сделать первый ход (не вся доска покрыта "нейтральными" фигурами).
Выведите число 1, если выигрывает игрок, ходящий первым; выведите число 2, если выигрывает игрок, ходящий вторым.
1 2 0
1
1 3 1 1 2
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