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

Дима и Катя продолжают играть в игру, описанную в задаче 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
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Дима и Катя играют в следующую игру: на доске 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
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Ограничение по времени: 4 секунды

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

Определите, кто выиграет при правильной игре.

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

Вводятся числа M и N (натуральные, не превышают 5). Затем вводится число k – количество "нейтральных" фигур на доске (целое, положительное, не превышает количества клеток доски). Затем следует k строк по 2 числа в каждой – номера строки и столбца, где находится данная "нейтральная" фигура. Гарантируется, что хотя бы первый игрок сможет сделать первый ход (не вся доска покрыта "нейтральными" фигурами).

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

Выведите число 1, если выигрывает игрок, ходящий первым; выведите число 2, если выигрывает игрок, ходящий вторым.

Примеры
Входные данные
1 2
0
Выходные данные
1
Входные данные
1 3
1
1 2
Выходные данные
2
Функция Гранди на специфическом графе с одним циклом с подвешенными к нему поддеревьями. Если в цикле все вершины имеют одинаковое значение Гранди относительно поддеревьев для цикла нечетной длины ответ NO, а для четной - a, a+1, a, a+1... В противном случае ищем минимальное значение сосед которого, входящий в него, не минимален. Расставляем значения начиная с этого минимума.

Пусть 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

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