Игры и выигрышные стратегии

Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из N столбцов и N строк, в каждой клетке которого находится какая-нибудь картинка, появляется на экране телевизора. Пусть все картинки пронумерованы следующим образом:

1	2	…	N
N+1	N+2	…	2*N
:	:	…	:
N*(N–1)+1	N*(N–1)+2	…	N*N

Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).

Дэвиду приходится довольно часто повторять этот трюк, и, чтобы не ошибиться, он попросил написать программу, которая будет ему сообщать, сколько ходов должны делать телезрители, и какие картинки нужно убирать. Напишите такую программу.

Входные данные
Во входном файле записано одно число N — размер квадрата (2<=N<=100).

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

K₁ X_1,1 X_1,2 … X_1,m1

K₂ X_2,1 X_2,2 … X_2,m2

…

K_e X_e,1 X_e,.2 … X_e,me

где K_i — это число ходов, которые должны сделать телезрители, а X_i,1 … X_i,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все K_i должны удовлетворять условию 2N<=K_i<=10000 и все K_i должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать K_i ходов, Дэвид должен убирать хотя бы одну картинку. Каждое K_i должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.

В игру крестики-крестики играют на поле размером 1 × N. Два игрока ходят по очереди. На каждом ходу игрок выбирает одну свободную ячейку и ставит там крестик. Если после его хода оказывается три крестика подряд, то он побеждает.

По известному N вам необходимо определить какой игрок победит при оптимальной игре обоих игроков.

Входные данные
Входной файл содержит одно число N (3 ≤ N ≤ 2000).

Выходные данные
Выведите 1, если побеждает первый игрок и 2, если побеждает второй игрок.

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

Кто из богатырей (начинающий или второй) может получить в жены принцессу независимо от действий другого?

Входные данные
Во входном файле записано два числа N и M — количество двух- и трехголовых драконов соответственно (оба числа целые из диапазона от 0 до 100).

Выходные данные
В выходной файл выведите сначала число 1 или 2 определяющее, кто из богатырей имеет все шансы получить в жены принцессу (1 — тот, кто начинает, 2 — второй). В случае 1 выведите также все варианты его первого хода, которые к этому приводят: сначала выведите количество различных выигрышных ходов (при этом отрубание одинакового количества голов у разных двухголовых драконов считается одним и тем же ходом, так же и для трехголовых), а затем сами ходы. Каждый ход задается парой чисел: первое число определяет у сколькиголового дракона нужно отрубать головы, а второе — сколько голов нужно отрубать.

После того, как к удивлению тётушки Полли, её забор был покрашен, она поручила Тому Сойеру обновить краску на плитках, которыми был вымощен их квадратный двор. Двор был покрыт NxN одинаковыми квадратными плитками, каждая из которых когда-то давно была покрашена в один из K цветов (K<N). Краска на плитках потускнела и Тому Сойеру поручили их покрасить, на этот раз в один любой цвет (из тех же К цветов). Покрасить нужно все плитки, в том числе и те, которые уже были покрашены в этот цвет раньше.

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

Входные данные
В первой строке записаны через пробел два числа: N — количество плиток в одном ряду (1<N≤200) и K (1≤K<N). В каждой из следующих N строк записаны N натуральных чисел, обозначающих номера цветов красок, в которые когда-то были выкрашены соответствующие плитки данного горизонтального ряда. Номера цветов — натуральные числа в диапазоне от 1 до K.

Выходные данные
Выведите два числа: L — какое минимальное число раз придется окунать кисть в ведро с краской, и номер краски С, в которую в результате окажутся перекрашены все плитки двора. Если таких красок может быть несколько, то выведите номер любой из них.

Если перекрасить все плитки, следуя придуманным Томом правилам, нельзя, выведите два раза число 0.

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачёркивают ровно K пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.

Входные данные
Ограничения: 1 <= K <= N <= 40.

В первой строке содержатся числа N и K, во второй строке N символов: латинская заглавная O - пустая клетка, латинская заглавная X - зачёркнутая клетка.

Выходные данные
Вывести одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя.

Слава и Оля играют в игру умножения - умножают целое число P на одно из чисел от 2 до 9. Слава всегда начинает с P = 1, делает умножение, затем число умножает Оля, затем Слава и т.д. Перед началом игры им задают случайное число N, и победителем считается тот, кто первым получит P >= N. Определить, кто выиграет при заданном N, если оба играют наилучшим образом.

Входные данные
В первой строке находится единственное число N. 2 <= N <= 4 294 967 295.

Выходные данные
Выводится одна строка - "Stan wins.", если победит Слава, или "Ollie wins.", если победит Оля.

Вы можете предполагать, что суммарное время работы библиотеки в процессе тестирования не будет превышать 4 сек.

Загрузить библиотеку для тестирования

Рассмотрим игру для двух игроков. Игрокам дан прямоугольник размером x × y (где x и y — положительные целые числа). Игроки ходят по очереди. Ход состоит в разделении прямоугольника на два прямоугольника одним горизонтальным или вертикальным разрезом. Полученные прямоугольники должны иметь положительные целочисленные размеры.


                  Возможные разрезы прямоугольника размером 4 × 3.

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

Ваша задача — написать программу, которая бы играла в игру с прямоугольниками и выигрывала. Для того чтобы играть, программа должна использовать специальную библиотеку. В библиотеке есть функции dimension_x() и dimension_y(), возвращающие размеры прямоугольника. Начальные размеры прямоугольника — целые числа от 1 до 100 000 000. Как минимум один из размеров больше 1. К тому же, в 50% тестов размеры прямоугольника не будут превышать 25.

В библиотеке есть также процедура cut(dir, position), которая должна вызываться вашей программой, чтобы сделать ход. Параметры dir и position описывают направление и позицию разреза соответственно. Параметр dir может принимать одно из двух значений: vertical и horizontal. Если dir = vertical, то проводится вертикальный разрез, а параметр position указывает x - координату разреза, как показано на рисунке выше. При этом вы должны гарантировать выполнение неравенства 1 ≤ position  ≤ dimension_x()− 1. Если dir = horizontal, то проводится горизонтальный разрез, а параметр position указывает y ? координату разреза. При этом, вы должны гарантировать выполнение неравенства 1 ≤ position  ≤ dimension_y()− 1.

После запуска вашей программы она будет играть за одного из игроков. Ваша программа ходит первой, она должна разрезать исходный прямоугольник. Когда ваша программа вызывает процедуру cut, ваш ход записывается и управление передается программе соперника. После хода соперника управление возвращается вашей программе. Значения, которые возвращаются функциями dimension_x() и dimension_y(), будут отражать результат вашего хода и хода соперника. Как только ваша программа выигрывает, проигрывает или делает неправильный ход, ее исполнение будет прервано. Прерывание вашей программы — это автоматический процесс, так что ваша программа должна продолжать делать столько ходов, сколько возможно до автоматического прерывания ее исполнения. Вы можете предполагать, что для предложенных входных данных всегда существует выигрышная стратегия для вашей программы.

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

Экспериментирование

Для того, чтобы дать вам возможность поэкспериментировать с библиотекой, в ваше распоряжение предоставлены примеры библиотек: их исходные тексты находятся в файлах preclib.pas, creclib.c и creclib.h . Эти библиотеки вы можете взять по адресу: http :// contest / . Они реализуют очень простую стратегию. Когда вы запустите вашу программу, она будет играть против этих простых соперников. Вы можете изменять их, чтобы протестировать вашу программу с лучшими соперниками. Следует учесть, что во время тестирования после окончания тура, ваша программа будет играть против другого соперника.

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

Если вы модифицируете часть implementation библиотеки preclib.pas, пожалуйста, перекомпилируйте её, используя команду ppc386 -O2 preclib.pas. Эта команда создаст файлы preclib.o и preclib.ppu. Эти файлы необходимы для компиляции вашей программы и должны быть в помещены в каталог, где находится ваша программа. Пожалуйста, не модифицируйте часть interface библиотеки preclib.pas.

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

В ваше распоряжение также предоставляются две простые программы, которые иллюстрируют использование библиотек crec.c и prec.pas. Пожалуйста, помните, что эти программы не являются правильными решениями. Вы можете откомпилировать их, используя такие команды:

gcc -O2 -static crec.c creclib.c -lm
g++ -O2 -static crec.c creclib.c -lm
ppc386 -O2 -XS prec.pas

Библиотеки

В ваше распоряжение предоставлены библиотеки, которые обеспечивают следующую функциональность:

Библиотека для FreePascal (preclib.ppu, preclib.o)
type direction = (vertical, horizontal);
function dimension_x(): longint;
function dimension_y(): longint;
procedure cut(dir: direction; position: longint);

 
Включите следующий оператор в ваш исходный файл rec.pas:
uses preclib;
Чтобы откомпилировать вашу программу, скопируйте файлы preclib.o и reclib.ppu в каталог, где находится ваш исходный файл, и выполните следующую команду:
ppc386 -O2 -XS rec.pas
Файл prec.pas является примером использования библиотеки preclib.

Библиотека для GNU C/C++ (creclib.h, creclib.c)

typedef enum __direction {vertical, horizontal} direction;
int dimension_x();
int dimension_y();
void cut(direction dir, int position);



Включите следующий оператор в ваш исходный файл (rec.c или rec.cpp):
#include ”creclib.h”
Чтобы откомпилировать вашу программу, скопируйте файлы creclib.c и creclib.h в каталог, где находится ваш исходный файл, и выполните следующую команду:
gcc -O2 -static rec.c creclib.c –lm
или:
g++ -O2 -static rec.cpp creclib.c –lm
Файл crec.c является примером использования библиотеки в C.
Пример взаимодействия

Ниже приведен пример взаимодействия вашей программы с библиотекой. Он показывает, как может проходить игра. Игра начинается с прямоугольника размером 4 × 3. Существует выигрышная стратегия для этого случая.
 

Ваша программа вызывает	Что происходит
dimension_x()	возвращает 4
dimension_y()	возвращает 3
cut(vertical, 1)	ваш разрез записывается, и прямоугольник размером 3 × 3 передается вашему сопернику, который разрезает его и получается прямоугольник размером 3 × 2; после этого управление передается вашей программе
dimension_x()	возвращает 3
dimension_y()	возвращает 2
cut(horizontal, 1)	ваш разрез записывается, и прямоугольник размером 3 × 1 передается вашему сопернику, который разрезает его и получается прямоугольник размером 2 × 1; после этого управление передается вашей программе
dimension_x()	возвращает 2
dimension_y()	возвращает 1
cut(vertical, 1)	в результате вашего разреза получается прямоугольник размером 1 × 1, так что вы выиграли; после этого работа вашей программы автоматически прекращается.

Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?

Входные данные
Вводится одно натуральное число — N ( 1≤ N ≤ 10000) начальное количество спичек в кучке.

Выходные данные
Выведите 1, если выигрывает первый игрок (тот, кто ходит первым), или 2, если выигрывает второй игрок.

Два участника олимпиады играют в следующую игру. Участники по очереди бросают монетки (одну или больше) в хитрый ящик. Если в ящике находится в точности X₁, или X₂, ..., или X_n монеток, то они, кроме одной, отдаются участнику, сделавшему последний ход. Оставшаяся монетка "исчезает" из игры. Игра заканчивается, если у одного из участников игры не осталось монеток. При этом монетки из ящика (все до одной) отдаются другому участнику(он является победителем игры). Определить наибольшее количество монеток, которое может выиграть первый участник при наилучшей игре второго. Если первый участник не может выиграть, то результатом является число 0.

Входные данные
В первой строке входного файла два числа 0 < S,T <= 50 (число монеток у первого и второго игроков). Во второй строке N (0 <= N <= 50) - число хитрых состояний ящика. В третьей строке целые числа X₁, X₂,..., X_n, 0 < X₁ <= X₂ <= ... <= X_n <= 100.

Выходные данные
Вывести число монеток у первого участника или 0.

То же, что и Дровосек - 1, только граф произвольный, после хода выживают те компоненты связности, которые содержат корни (изначально в каждой компоненте связности есть хотя бы один корень).

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

В первой строке задаются 3 числа - количество вершин 1 < N <= 10000, число ребер 0 <= M <= 100000 и количество корней 1 <= R <= N. В следующей строке идут различные числа 1 <= R_i <= N - номера вершин, являющихся корнями. В следующих M строках идут пары чисел - описания ребер.

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

Выведите одно число -  номер игрока-победителя.

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

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

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

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

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

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

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

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

Формат входных данных
В первой строке входных данных задается число N (1 ≤ N ≤ 50) — количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк содержат по две пары целых чисел — координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.

Координаты всех точек неотрицательны и не превосходят 50.

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

Примечание

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

Алиса и капитан Буран играют в покер с одной картой. Однокарточный покер - это игра для двух игроков с игральными картами. Каждая карта в этой игре показывает целое число от 1 до 13 включительно. Сила карты определяется числом, написанным на ней, следующим образом:
Слабая 2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1 Сильная
В покер с одной картой играют следующим образом:
- Каждый игрок берет одну карту из колоды.
- Выбранная карта становится рукой игрока.
- Игроки раскрывают друг другу руки.
- Игрок с более сильной картой побеждает в игре.
- Если их карты одинаково сильны, игра заканчивается вничью.
Вы смотрите, как Алиса и капитан Буран играют в игру, и можете видеть их руки. Число, написанное на карточке Алисы, - A, а число, написанное на карточке капитана Бурана, - B.

Напишите программу для определения исхода игры.
 

Вася и Петя играют в следующую игру. Они берут колоду из 36 карточек. На каждой карточке написано число от 1 до 9 и каждая карточка покрашена в один из 4 цветов так, что есть ровно по 9 карточек каждого цвета и они пронумерованы числами от 1 до 9. Карты перемешиваются, и игрокам раздается по 18 карт.

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

Выигрывает тот, кто первым выложит все свои карточки на стол.

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

Входные данные
Во входном файле записаны 18 пар чисел, описывающих карточки, которые достались первому игроку. Каждая карточка описывается двумя числами — номером цвета (от 1 до 4) и цифрой, которая написана на карточке (от 1 до 9). Второму игроку, соответственно, достались все остальные карточки.

Выходные данные
В выходной файл выведите одно число (1 или 2) — номер игрока, который выиграет при оптимальной игре обоих игроков.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9	1

Маша и Даша играют в игру с N (\(1<=N<=10^5\)) кучками камушков, где i-ая кучка содержит ai камешков (\(1<=i<=N\), \(1<=a_i<=10^6\)). Они ходят по очереди, первой ходит Маша.

• Сначала Маша выбирает некоторое положительное число s1 и удаляет s1 камешков из некоторой кучки, в которой есть не менее s1 камешков.
• Затем Даша выбирает некоторое положительное число s2 такое, что s2 делится на s1 и удаляет s2 камешков из некоторой кучки, содержащей не менее s2 камешков.
• Затем Маша выбирает некоторое положительное число s3, которое делится на s2 и удаляет s3 камешков из некоторой кучки, в которой есть не менее s3 камешков.
• В общем случае si, количество камешков, которое убирается на ходу i, должно быть делителем si+1.

Проигрывает тот, кто не может сделать ход.

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

Входные данные
Первая строка содержит N.
Вторая строка содержит N разделённых одиночными пробелами целых чисел a1,…,aN.


Выходные данные
Выведите количество способов, которыми Маша может удалить камушки на первом ходу, чтобы гарантировать себе выигрыш.
Для вычислений используйте 64-ное целое например, "long long" в C/C++.
 
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	1 7	4	Маша выбирает 4, 5, 6, 7 камушков из одной кучи и игра закончится сразу.
2	6 3 2 3 2 3 1	8	Маша выиграет, если удалит 2 или 3 камушка из любой кучи. Затем игроки будут по очереди брать одно и то же количество камушков, но Маша сделает последний ход.