Задача A. Автомобильные номера

Автор:VI Всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:numbers.in   Ограничение памяти:64 Мб
Выходной файл:numbers.out  

Условие

При расследовании дорожно-транспортных происшествий часто возникают проблемы с розыском автомобилей, водители которых покинули место происшествия.

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

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

Входной файл содержит одну строку, которая представляет собой корректный автомобильный номер.

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

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

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

Входной файл (numbers.in) Выходной файл (numbers.out)
1
X772KX
9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача B. Два компьютера

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

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров Ti секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

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

Входной файл содержит число N, за которым следуют числа T1TN. Все числа — целые, разделены пробелами.

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

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

Ограничения

1 ≤ N ≤ 20, 1 ≤ Ti ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7 10 3 5 6
16

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

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

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

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

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

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

Задача F. Разнообразный куб

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

Условие

Даны восемь символов из диапазона от "A" до "Z". Некоторые из них могут совпадать. Требуется определить, можно ли расположить эти символы в вершинах куба таким образом, чтобы на соседних (т. е. соединенных ребром) вершинах оказались разные символы.

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

Во входном файле находится строка из восьми заглавных латинских букв.

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

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

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

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

Задача G. Домино

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

Условие

Костяшка домино описывается парой цифр от 0 до 6, например 06 или 33. Цепочка - это последовательность костяшек, скложенных таким образом, чтобы соседние цифры на них совпадали. При этом костяшки можно переворачивать. Например, 15-54-44-46-60 — цепочка.

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

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

Входной файл содержит строку, задающую костяшки.

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

В выходном файле должна содержаться единственная строка вида d1-d2-...-dN, где d1, d2, …, dN — костяшки из исходного набора, или NO, если сложить цепочку невозможно.

Ограничения

2 ≤ N ≤ 21

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1234
NO
2
453335
45-53-33

Задача H. Слово из кубиков

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

Условие

Имеется N кубиков, на гранях которых написаны буквы. Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов, и если да, то вывести номера использованных кубиков. При этом каждый кубик можно использовать только один раз. Если решений несколько, выдать любое из них.

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

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

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

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

Ограничения

1 ≤ N, K ≤ 12.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
2 5 3 4

Problem I. Hot-keys

Author:A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

When designing dialog forms for interactive programs, it is important to assign hot-keys (known also as accelerator keys) to each dialog element, so as to facilitate keyboard input.

For better mnemonics, hot-keys are assigned based on the letters of dialog elements' captions, usually favoring letters near the beginning of caption. Manual hot-keys distribution can be tedious and error-prone, as one must be careful not to assign same letter to different elements.

Your program will be given a list of captions. It must assign unique hot-keys to as many captions of possible. Each assigned hot-key must be a letter from the corresponding caption.

For each hot-key, position is the leftmost occurrence of the hot-key letter in the corresponding caption. From all solutions with the same numbers of hot-keys, your program must choose the one with minimal sum of hot-key positions. If there is still more than one optimal solution, output any of them.

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&amp;abc
&amp;bca
a&amp;cb
aaaa

Задача J. Максимальный перепад

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

Условие

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

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

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

Входной файл содержит число N, за которым следуют N2 целых чисел — описание карты региона.

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

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

Ограничения

1 ≤ N ≤ 100. Все высоты — целые числа от 0 до 231−1

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

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

0.664s 0.019s 33