Задача 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. Беговые дорожки 2

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

Условие

Между n спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется стадион лишь с n − 1 беговой дорожкой, поэтому одновременно могут состязаться только n − 1 из n участников. По этой причине соревнования разбиваются на несколько забегов.

Правила соревнований требуют, чтобы каждый из бегунов:

Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на соседние дорожки в забеге. При этом у каждого из участников есть не более одного «неприятного» ему конкурента, и чувство антипатии является взаимным.

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

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

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

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

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

Ограничения

2 ≤ n ≤ 100.

1 ≤ r ≤ 1000.

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

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

Задача C. Код Грея

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

Условие

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

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

Во входном файле содержится строка из символов 0 и 1

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

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

Ограничения

1 ≤ N ≤ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
0
2
110
110
111
101
100
000
001
011
010

Задача D. k-почтимонотонность

Автор:Жюри летних сборов 2009   Ограничение времени:15 сек
Входной файл:kinc.in   Ограничение памяти:256 Мб
Выходной файл:kinc.out  

Условие

Рассмотрим последовательность a1, , an. Назовём её k-почтимонотонной, если среди неравенств a1 ≤ a2, a2≤ a3, , an − 1≤ an ровно k неверных.

Даны числа 0 ≤ b1, b2, …, bm ≤ n, где b1 + b2 + …  + bm = n. Найдите количество k-почтимонотонных последовательностей, в которой число 1 встречается b1 раз, 2 встречается b2 раз, , m — bm раз.

Ответ требуется вывести по модулю 109 + 9.

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

В первой строке заданы два натуральных числа k и m. В следующей строке задано m натуральных чисел bi.

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

Выведите единственное число — ответ на поставленную задачу.

Ограничения

1 ≤ k ≤ 100;

1 ≤ m ≤ 26;

1 ≤ bi ≤ 100;

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

Входной файл (kinc.in) Выходной файл (kinc.out)
1
2 2
2 2
1

0.303s 0.015s 19