Задача A. Длинное взятие

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек. Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.) Вертикали обозначены буквами a, b, c, … слева направо. Клетка, таким образом, задается комбинацией из буквы и числа, например d12. Ход шашки задается перечислением всех клеток, которые она посетила за этот ход, включая начальную и конечную. Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.

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

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

Формат входного файла

В первой строке входного файла содержится число N. В следующих N строках — описание позиции, состоящее из символов '.' (точка), 'O' (заглавная латинская О),'X' (заглавная латинская X). Они определяют пустую клетку, белую шашку и черную шашку соответственно.

Формат выходного файла

В выходном файле должна содержаться единственная строка вида L1 N1 − L2 N2 − … − LK NK, где K ≥ 1, или Impossible если взятие невозможно.

Ограничения

1 ≤ N ≤ 12

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
.....
.O.O.
....X
.O.O.
X....  
e3-c1-a3-c5-e3  
2
4
X...
....
....
...O  
Impossible

Задача B. Судьба математика

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

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

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

Формат входного файла

В каждой строке входного файла содержится одно отношение, состоящее из двух различных номеров цифр от 1 до 6, между которыми стоит один из знаков >, <, =, <=, >=, <>. Внутри строки пробелов нет.

Формат выходного файла

В выходном файле должно содержаться единственное число — количество номеров.

Ограничения

Количество отношений находится в диапазоне от 1 до 30.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1&lt;2
3=1
3&gt;4
12000

Задача C. Ответы к тесту

Автор:А. Жуплев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

Поскольку Гена не подготовился к тесту, он решил схитрить. Для этого он подговорил P шушанчиков, чтобы они прошли тест до него. Каждый шушанчик запомнил, как он отвечал на каждый из вопросов, и сколько баллов получил.

По этим данным Гена должен определить правильные ответы.

Формат входного файла

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

Формат выходного файла

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

Исходные данные таковы, что существует хотя бы один вариант решения.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 2
+-
0
-+
2
3 4
--++
3
----
1
---+
2
+-++

Задача D. Марсианские факториалы

Автор:I Всероссийская командная школьников по программированию, 2000 год   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце — это конечно же нули — ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули начиная с 5! = 1 × 2 × 3 × 4 × 5 = 120. А у числа 100 в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 — так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N! = 1 × 2 × 3 × … × (N − 1) × N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

Формат входного файла

На первой строке входного файла находятся числа N и K, разделенные пробелом.

Формат выходного файла

Выведите в выходной файл число X - количество нулей в конце записи числа N! в системе счисления с основанием K.

Ограничения

1 ≤ N ≤ 109, 2 ≤ K ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 10
1
2
100 10
24
3
100 6
48
4
3 10
0

0.249s 0.011s 19