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

Автор:А. Жуплев, А. Кленин   Ограничение времени: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
+-++

Задача 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   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Однажды школьник Вася пришел в недавно построенное новое здание университета на мастер-класс по информатике. Здание имеет форму куба, составленного из одинаковых аудиторий также кубической формы. Каждой аудитории присвоены три номера x, y, z — порядковые номера по ширине, длине и высоте соответственно. Самая первая аудитория имеет номера 1, 1, 1. Из каждой аудитории можно перейти в любую соседних, имеющих с ней общую стену.

Вася находится в аудитории (xB, yB, zB). Мастер-класс пройдет в аудитории (xM, yM, zM). Вася решил посчитать, сколькими способами можно попасть из текущей аудитории в ту, где проходит мастер-класс, за наименьшее число переходов между аудиториями.

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

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

Входной файл содержит 6 целых чисел xM yM zM xB yB zB.

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

Выходной файл должен содержать единственное целое число — количество способов. Так как ответ на вопрос Васи может быть слишком большим, выведите в его остаток от деления на 109 + 7.

Ограничения

1 ≤ xM, yM, zM, xB, yB, zB ≤ 1000.

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

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

Задача D. Спичечные блоки

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

Условие

Пусть имеется n спичек равной длины. Из указанных спичек необходимо собрать набор прямоугольных блоков, каждый из которых представляет собой двумерную матрицу квадратных ячеек (см. рисунок). При этом каждое ребро в таком блоке соответствует ровно одной спичке. Таким образом, полученный блок однозначно определяется своей конфигурацией [A × B], где A и B — размеры его сторон. Блоки, совпадающие с точностью до поворота, считаются одинаковыми, т.е. [A × B] = [B × A].

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

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

Входной файл "input.txt" содержит исходное число спичек n.

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

Выходной файл "output.txt" должен содержать все найденные комбинации, представленные в следующем формате: вначале указывается число блоков в текущей комбинации k; далее следует ровно k пар натуральных чисел, определяющих конфигурации имеющихся блоков.

В случае, если подходящие комбинации не были найдены, в выходной файл записывается единственный символ пробела (ASCII 32).

Ограничения

0 < n ≤ 128

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

Входной файл (input.txt) Выходной файл (output.txt)
1
23
5 1 1 1 1 1 1 1 1 1 2
3 1 1 1 2 2 2
2 1 1 1 6
2 1 2 1 5
2 1 3 1 4
2
3
 

Задача E. Hot-keys

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

Условие

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

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

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

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

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

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

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

Выходной файл должен содержать N строк с одинаковыми заголовками, как и во входном файле. В каждом заголовке, которому была назначена какая-то комбинации, перед самым левым вхождением символа из горячей клавиши необходимо добавить символ '&' (ASCII 38).

Ограничения

1 ≤ N ≤ 10, все заголовки имеют длину от 1 до 10 символов и состоят из строчных латинских букв.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&amp;abc
&amp;bca
a&amp;cb
aaaa

0.342s 0.018s 23