Дима и Катя играют в следующую игру: на доске 5x5 клеток установлено несколько трусливых пешек. Трусливая пешка – это фигура, для взятия которой не обязательно перемещаться на ее клетку, а достаточно просто создать для нее угрозу.

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

Игра продолжается до наступления одного из событий:
1. Катя сделала N ходов и при этом на доске осталась хотя бы одна пешка – в этом случае выиграл Дима;
2. После некоторого хода Кати на доске не осталось ни одной пешки – в этом случае выигрывает Катя.
3. Кто-то из игроков не может сделать следующий ход. В этом случае присуждается ничья.

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

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

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

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

Из описания некоего растения: «… его время жизни составляет 20 лет. В первый год плод растения попадает в землю. Первые побеги растения появляются лишь на второй год. Плодоносить растение начинает с четвертого года и ежегодно дает по 1 плоду, которые сразу попадают в землю, и из них вырастают такие же растения. На двадцатый год своей жизни растение плодоносит в последний раз, а на двадцать первый год – погибает».

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

Замечания

Из описания следует, что плод, который появился в 4-м году, сразу попадает в землю, и этот год считается 1-м годом жизни нового растения (при этом при подсчете числа живых растений в этом году данное растение еще не будет учтено). Это растение даст первые побеги в 5-м году, начнет плодоносить — в 7-м, а последний раз будет плодоносить в 23-м году и перестанет быть живым – в 24-м.

При подсчете числа живых растений в 20-м году исходное растение еще считается живым, а в 21-м — уже не считается.

Рассмотрим расписание движения электричек на некоторой железнодорожной линии. Нас будут интересовать только электрички, идущие в одном направлении.

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

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

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

По данному расписанию движения электричек определите порядок, в котором электрички должны идти в книжке—расписании.