Electronic Voice

Задача А. Electronic Voice

Имя входного файла:	a. in
Имя выходного файла:	a. out
Максимальное время работы на каждом тесте:	10 секунд

Выпущена новая версия редактора Electronic Voice, который понимает следующие голосовые команды: "повторить последнее слово" и "стереть последний символ". При исполнении команды "повторить последнее слово" редактор автоматически вставляет пробел, разделяющий слова.

С помощью этого редактора, как утверждает производитель программного продукта, можно набирать текст, нажимая клавиши на клавиатуре гораздо реже. Например, чтобы набрать фразу "this thin thing" , достаточно нажать на клавиши на клавиатуре всего 6 раз:

Действие	Нажатий	Содержимое документа
Набрать "this"	4	this
Сказать "повторить последнее слово"	0	this this
Сказать "стереть последний символ"	0	this thi
Набрать "n"	1	this thin
Сказать "повторить последнее слово"	0	this thin thin
Набрать "g"	1	this thin thing

Чтобы повысить популярность своего продукта, производитель решил провести конкурс, победителем которого станет тот, кто сможет набрать заданный набор слов в редакторе за наименьшее количество нажатий на клавиши. Причем первое слово зафиксировано, а остальные могут быть набраны в произвольном порядке. То есть, если надо набрать слова "apple", "plum" и "apricote", то первым надо набрать "apple", а слова "plum" и "apricote" можно поменять местами.

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

Формат входных данных

На первой строке входного файла находится число (1 ≤ N ≤ 100) – количество слов, которые предстоит набрать. Следующие строк содержат слова – последовательности маленьких латинских букв, не длиннее символов. Помните, что первое слово необходимо набрать первым!

Формат выходных данных

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

Примеры

a. in	a. out
3 this thin thing	6 this thin thing
4 popcorn apple apricote plum	21 popcorn plum apricote apple
2 hello hello	5 hello hello

Задача B. Лунные факториалы

Имя входного файла:	a. in
Имя выходного файла:	a. out
Максимальное время работы на каждом тесте:	10 секунд

В 4123 году исследовательская экспедиция обнаружила на Луне таинственные знаки. Смысл этих знаков был неизвестен ученым. Профессор Брэйн заметил, что всего в надписях, составленных из этих знаков, встречается ровно 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, разделенные пробелом. ( 1 ≤ N ≤ 109, 2 ≤ K ≤ 1000).

Формат выходных данных

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

Примеры

a. in	a. out
5 10	1
100 10	24
100 6	48
3 10	0

Задача C. Идентичные матрицы

Имя входного файла:	a. in
Имя выходного файла:	a. out
Максимальное время работы на каждом тесте:	10 секунд

Таблица состоит из N строк и M столбцов. Назовем таблицу целочисленной матрицей, если в каждой ячейке таблицы стоит целое число. Скажем, что матрица кратна чиcлу p, если все числа в ее ячейках кратны p.

Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел i-й строки за Hi , а сумму чисел j-го столбца за Vj . Упорядоченный набор чисел (H1, H2, …HN, V1, V2, …VM ) назовем профилем матрицы. Скажем, что матрица почти кратна p, если все числа, входящие в ее профиль, кратны p.

Почти кратная 5 матрица и ее профиль изображены на рисунке 1.

6	7	2	15
2	2	31	35
7	1	7	15
15	10	40

Рисунок 1

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

1.  отличается от не более чем на

2. 

Профили и совпадают.

На рисунке 2 изображены две похожие относительно числа 5 матрицы, первая из них почти кратна 5, а вторая кратна 5. Третья матрица на рисунке 2 тоже кратна 5, но не похожа на первую (хотя похожа на вторую).

Дано число p и почти кратная p матрица A. Ваша задача – найти такую матрицу B, чтобы она была кратна p и похожа на A относительно p.

Формат входных данных

На первой строке входного файла находятся целые числа p (1 ≤ p ≤ 10), и (1 ≤ N, M ≤ 30). Следующие строк содержат по M целых неотрицательных чисел, не превышающих 1000, которые являются элементами исходной матрицы A.

Формат выходных данных

Выведите в выходной файл матрицу B по строкам – сначала M элементов первой строки, затем M элементов второй и т. д. Разделяйте числа пробелами и/или переводами строк. Заботиться о «красивом» форматировании таблицы не надо. Если искомой матрицы не существует, выведите единственное число –

"- 1". Если решений несколько, выведите любое из них.

Пример

a. in	a. out
5 3 3 6 7 2 2 2 31 7 1 7	5 5 5 0 5 30 10 0 5

Задача D. Подсчет суммы

Имя входного файла:	a. in
Имя выходного файла:	a. out
Ограничение по времени:	2 секунды
Ограничение по памяти:	256 мегабайт

Даны три числа А, В и С. Для того чтобы установить между ними какую-либо простую закономерность, надо выяснить, можно ли этим числам приписать в конец несколько нулей так, чтобы сумма первых двух чисел стала равна третьему. Например, если даны числа 9, 34 и 43, то к ним невозможно приписать нули — сумма 9 и 34 и так равна 43. Если же даны числа 23, 7 и 93, то можно приписать нуль к 7 и получить 70. После чего 23 + 70 = 93.

Вам дано три натуральных числа А, В и С. Требуется найти неотрицательные целые числа n, m и k такие, что А × 10n + В × 10m = С × 10k.

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

На первой строке входного файла записано число А, на второй — В, на третьей — С. Все числа не меньше единицы и не больше .

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

Если числа n, m и k, удовлетворяющие условию, существуют — выведите на первой строке «YES», а на второй строке сами числа. Числа должны быть неотрицательными и не превосходить 106. Если решений несколько — выведите любое. Если же таких чисел не существует — выведите «NO».

Примеры

a. in	a. out
9 34 43	YES 0 0 0
23 7 93	YES 0 1 0
1 2 4	NO

Задача Е. Украшения из драгоценных камней

Имя входного файла:	a. in
Имя выходного файла:	a. out
Ограничение по времени:	2 секунды
Ограничение по памяти:	256 мегабайт

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

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

Шах обычно оценивает украшения следующим образом: он заранее определил несколько упорядоченных пар видов украшений: (a1, b1), (a2, b2), … , (ak, bk). Эти пары он называет красивыми, их множество обозначим как Р. Теперь представим ряд украшений, которые продают купцы, в виде строки S длины n из строчных букв латинского алфавита. Шах считает число таких пар (i, j), что 1 ≤ i < j ≤ n, а украшения Si и Sj образуют красивую пару, то есть существует такое число 1 ≤ q ≤ k , что Si = аq и Sj = bq.

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

Напишите программу, которая находит ответ на эту задачу.

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

Первая строка входного файла содержит целые числа n и k (1 ≤ n ≤ 1 ≤ k ≤ 676) — число украшений, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку S, описывающую виды украшений, которые привезли купцы.

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

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

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

Примеры

a. in	a. out
7 1 аbасаbа аа	6
7 3 аbасаbа аb ас bb	7