Задача A. Неправильный кабель

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

Условие

Принтер соединен с компьютером кабелем, содержащим N линий данных, пронумерованных от 1 до N. Принтер имеет N контактов, также пронумерованных от 1 до N. При правильном подключении номер линии данных совпадает с номером контакта принтера (см. рис. 1).

По каждой линии данных i может передаваться сигнал si — "0" либо "1". При передаче в принтер кода символа по линиям 1, 2, ..., N одновременно передаются сигналы s1, s2, ..., sN. Например, при N = 8 символу "A" может соответствовать код 01000001 — это значит, что по линиям с номерами 2 и 8 должен быть передан сигнал "1", а по остальным — сигнал "0" (см. рис. 1).

В результате неправильного монтажа кабеля линии могли быть соединены не с теми контактами принтера. Известно, что линии не соединены между собой и не оборваны. На рис. 2 изображен пример неправильного монтажа кабеля при N = 8.

Схему монтажа кабеля можно обозначить перестановкой π1π2, … , πN чисел от 1 до N, где πi - номер линии, подсоединенной к i-му контакту принтера. Например, правильному монтажу, изображенному на рис. 1, соответствует перестановка 12345678, а неправильному монтажу, изображенному на рис. 2, — перестановка 12534687.

При передаче кода s1, s2, … , sN по кабелю принтер получит код , который может отличаться от исходного из-за ошибок монтажа. Например, при передаче кода 01001101 по кабелю на рис. 2 принтер получит код 01100110. Заметим, что код 11000100 здесь будет передан правильно.

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

Даны M пар кодов. Код состоит из N символов, каждый из которых либо "0", либо "1". Первым в паре стоит код, переданный с компьютера, вторым — код, полученный принтером. Программа должна однозначно определить схему монтажа кабеля (перестановку чисел от 1 до N), либо сообщить, что это невозможно.

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

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

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ M ≤ 10000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8 3
11110000 11110000
11001100 11001010
10101010 10101001
1 2 3 4 5 8 6 7

Задача B. Свинья-копилка

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

Условие

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

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

Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N). Требуется определить минимальную сумму, которая может содержаться в копилке.

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

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — Ci Wi. Все числа во входном файле — целые.

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

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

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 110 2
1 1
30 50
60
2
10 110 2
1 1
50 30
100
3
1 6 2
10 3
20 4
-1

Задача C. Связка брусков

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

Условие

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

По длинам сторон сечения каждого бруска a1 b1 и a2 b2 определить минимальную длину веревки.

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

Во входном файле содержатся вещественные положительные числа a1 b1 a2 b2.

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1 1 1
8.83

Задача D. Последняя цифра

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

Условие

Дано N целых чисел a1, a2, … , aN. Требуется найти две последние цифры числа, определяющего количество натуральных делителей произведения a1 × a2 × … × aN. Если число делителей меньше 10, то вывести это число без лидирующего нуля.

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

В первой строке входного файла содержится число N. В следующей строке содержатся числа a1, a2, … , aN.

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

Выходной файл должен содержать одну или две искомые цифры, в соответствии с условием задачи.

Ограничения

1 ≤ N ≤ 20; 1 ≤ ai ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
3 5 7 720
20
2
4
64 1024 9 5
02
3
3
2 3 5
8

0.323s 0.009s 27