Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование в играх
---> 9 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке находится сначала число стопок N, за ним идут N чисел, задающих количество монет в стопках слева направо, а затем число K. Все числа в строке разделены пробелами.

Ограничения: 1 <= N <= 180, 1 <= K <= 80, количество монет в стопке - не менее 1 и не более 20 000.

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

Вывести одно число - максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.


Примеры
Ввод 1          Ввод 2            Ввод 3
3  4 9 1  3     4  1 2 2 7  3     5  3 4 8 1 7  2
Вывод 1         Вывод 2           Вывод 3
14              5                 18

Поле для игры с шашками – длинная горизонтальная полоска, размеченная на клетки. Клетки пронумерованы от 1 до N (2 < N 10000). На поле стоят две шашки. Позиция каждой из шашек определяется номером клетки, в которой она стоит.

Играют двое. Каждый игрок при своем ходе должен переместить любую шашку на одну, две или три клетки в сторону клетки 1 (сделать 1, 2 или 3 шага). Перепрыгивать через стоящую впереди шашку нельзя, но можно сдваивать шашки. На сдваивание шашек   тратится два шага из трех доступных игроку (то есть сдваивать можно либо шашки, стоящие  вплотную друг к другу, либо шашки, между которыми есть только одна пустая клетка). Если произошло сдваивание – ход передается другому игроку, который делает ход  одной шашкой , оставив другую на месте.

Выигрывает тот, кто сдвоит шашку на клетке с номером 1.

Требуется написать программу, реализующую алгоритм, обеспечивающий победу игроку, начинающему игру.

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

В первой строке содержится число K (0 < K 10) – количество начальных позиций. В последующих K строках содержится по два целых числа от 3 до 10000, разделенных пробелом – номера начальных позиций шашек на игровом поле.

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

Выводится K строчек – ответ на каждую начальную позицию.

Если при заданной начальной позиции шашек в игре не достигается выигрыш (при правильной игре противника) выводится слово NO.

Если выигрыш достижим, то выводится первый ход начинающего игру, который приводит к его выигрышу независимо от того, как играет соперник. Ход описывается парой чисел  i, j через пробел, означающих, что выигрышный ход игрока – это перемещение шашки из клетки с номером i в клетку с номером  j. Например, «4 3» означает, что игрок двигает шашку, стоящую в клетке 4, на одну клетку в сторону клетки 1.

Примечание
Ответ на тест из примера:
NO
11 10
12 11
NO
15 12
12 10
Примеры
Входные данные
6
3 10
3 11
4 12
5 8
9 15
3 12
Выходные данные
YES
NO
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Сегодня на уроке математики Петя и Вася изучали понятие арифметической прогрессии. Арифметической прогрессией с разностью d называется последовательность чисел a1, a2, …, ak, в которой разность между любыми двумя последовательными числами равна d. Например, последовательность 2, 5, 8, 11 является арифметической прогрессией с разностью 3.

После урока Петя и Вася придумали новую игру с числами. Игра проходит следующим образом.

В корзине находятся n фишек, на которых написаны различные целые числа a1, a2, …, an. По ходу игры игроки выкладывают фишки из корзины на стол. Петя и Вася делают ходы по очереди, первым ходит Петя. Ход состоит в том, что игрок берет одну фишку из корзины и выкладывает ее на стол. Игрок может сам решить, какую фишку взять. После этого он должен назвать целое число d ≥ 2 такое, что все числа на выбранных к данному моменту фишках являются членами некоторой арифметической прогрессии с разностью d, не обязательно последовательными. Например, если на столе выложены фишки с числами 2, 8 и 11, то можно назвать число 3, поскольку эти числа являются членами приведенной в начале условия арифметической прогрессии с разностью 3.

Игрок проигрывает, если он не может сделать ход из-за отсутствия фишек в корзине или из-за того, что добавление любой фишки из корзины на стол приводит к тому, что он не сможет подобрать соответствующее число d.

Например, если в корзине имеются числа 2, 3, 5 и 7, то Петя может выиграть. Для этого ему необходимо первым ходом выложить на стол число 3. После первого хода у него много вариантов назвать число d, например он может назвать d = 3. Теперь у Васи два варианта хода.

  1. Вася может вторым ходом выложить фишку с числом 5 и назвать d = 2. Тогда Петя выкладывает фишку с числом 7, называя d = 2. На столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2. Вася не может ее выложить, поскольку после этого он не сможет назвать корректное число d. В этом случае Вася проигрывает.
  2. Вася может вторым ходом выложить фишку с числом 7 и также назвать, например, d = 2. Тогда Петя выкладывает фишку с числом 5, называя также d = 2. Вася снова попадает в ситуацию, когда на столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2, и он также проигрывает.

Заметим, что любой другой первый ход Пети приводит к его проигрышу. Если он выкладывает число 2, то Вася отвечает числом 7, и Петя не может выложить ни одной фишки. Если Петя выкладывает фишку с числом 5 или 7, то Вася выкладывает фишку с числом 2, и у Пети также нет допустимого хода.

Требуется написать программу, которая по заданному количеству фишек n и числам на фишках a1, a2, …, an определяет, сможет ли Петя выиграть вне зависимости от действий Васи, и находит все возможные первые ходы Пети, ведущие к выигрышу.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200).

Вторая строка содержит n различных целых чисел a1, a2, …, an (для всех i от 1 до n выполняется неравенство 1  ai  105). Соседние числа разделены ровно одним пробелом.

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

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

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

Примечание

Первый пример рассматривается в тексте условия этой задачи.

Во втором примере, какую бы фишку не выложил Петя первым ходом, Вася в ответ выкладывает другую фишку, и Петя не может сделать ход из-за отсутствия фишек в корзине.

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

Аркадий и Алексей придумали новую игру. Листок клетчатой бумаги размером 2 N ×2 M клеток заполняется цифрами (по одной цифре в каждую клетку). Затем начинается собственно игра: тот, чья очередь ходить, разрезает листок пополам вдоль короткой стороны (или любой стороны, если листок квадратный), выбирает любую из половин и выбрасывает ее; оставшаяся половина передается другому игроку. При этом игрок получает очки за каждую пару клеток, бывших соседними до разрезания:

• если в соседних клетках были одинаковые цифры, то игрок получает 3 очка;

• если в соседних клетках были цифры одинаковой четности, то игрок получает 1 очко;

• если в соседних клетках были цифры разной четности, то игрок получает 0 очков.

Резать листок можно только по линиям, разделяющим клетки. Игра завершается, когда от листка остается одна клетка — ее разрезать нельзя. Побеждает тот, кто наберет больше очков. Аркадий ходит первым и его интересует, какую максимальную разницу между его очками и очками Алексея он может получить, если оба они будут играть оптимально. Аркадию и Алексею доступны только такие листки, у которых N и M отличаются не более чем на 1.

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

В первой строке записаны два целых числа N и M ( 0 ≤ N , M ≤ 10 , | N M | ≤ 1 ). Данный листок имеет размеры 2 N ×2 M клеток. В следующих 2 N строках записано содержимое листка. В каждой строке записано 2 M десятичных цифр без пробелов. Каждая цифра соответствует одной клетке исходного листка.

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

Выведите единственное число — максимально возможную разницу между количествами очков Аркадия и Алексея.

Примечание

В первом примере Аркадий может разрезать квадрат по горизонтали, получив 2 очка (за пары 1, 3 и 2, 4). Оставив Алексею половинку с цифрами 1, 2, Аркадий не даст ему шанса заработать ни одного очка. Если же Аркадий разрежет исходный квадрат по вертикали, то он не получит ни одного очка, зато при разрезании любой из оставшихся половин ( или Во втором примере Алексей наберет больше очков, как бы не играл Аркадий. Первым ходом Аркадий может только разрезать листок по вертикали, не получив очков. Если отдать Алексею левую половину, то это позволит ему получить 6 очков, разрезав ее по вертикали (за пары 2, 2 и 1, 1). При этом Аркадию достанется листок , разрезание которого не принесет очков. Если же отдать Алексею правую половину исходного листка, то он сможет получить 1 очко, разрезав листок любым способом. Но для максимизации своего выигрыша Алексей разрежет листок по вертикали и отдаст Аркадию половинку , разрезание которой не принесет последнему очков. Итоговый счет 0:1 в пользу Алексея.

Примеры
Входные данные
1 1
12
34
Выходные данные
2

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