Лексикографические пути

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

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

Входные данные

В первой строке записаны числа N и K (1<=N<=26, 1<=К<=5000).
Последующие N строк содержат описание вершин графа в следующем виде:
<описание i-ой вершины>::= <символ, записанный в i-й вершине> <число di дуг, исходящих из i-й вершины> <номер вершины, в которую ведёт первая дуга>...<номер вершины, в которую ведёт di-ая дуга>.
Все данные в строке отделены друг от друга пробелом.
Разные вершины могут иметь одинаковый записаный на них символ.

Выходные данные

В первой и единственной строке должно содержаться найденное слово.

Пример

Ввод

2 7
a 2 1 2
b 1 1

Вывод

Aaaaaaa

Service Pack

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Известная своими нетрадиционными разработками фирма Macrohard решила выпустить пакет обновления (service pack), чудесным образом превращающий программный пакет Beds v1.0 в Beds v1.01. Этот пакет обновления состоит из последовательности команд следующих двух типов:
· Old P L - означает, что нужно взять L байт пакета Beds v1.0, начиная с позиции P;
· New seq - означает, что нужно взять и переписать непосредственно последовательность байтов seq.
Команды исполняются по порядку. Длиной пакета обновления называется сумма длин отдельных его команд, причем длина команды Old равна L1 байт, а длина команды New равна (L2 + длина последовательности seq) байт.
Ваша задача: по содержимому пакетов Beds v1.0 и Beds v1.01 составить пакет обновления наименьшей длины.

Входные данные

Первая строка содержит числа L1 и L2, разделенные пробелом (1<=L1,L2<=100). Вторая строка содержит пакет Beds v1.0, а третья - версии 1.01. Пакеты представляют собой непустые последовательности строчных букв латинского алфавита длины не более 1000 символов.

Выходные данные

В первой строке файла должна быть указана найденная наименьшая длина пакета обновления, во второй стороке - число команд K в этом пакете. Последующие K строк должны содержать сам пакет обновления (по одной команде пакета в строке). Синтаксис этих команд таков:
<команда Old>::= Old <начальная позиция P> <длина L>
<команда New>::= New <последоваетельность seq строчных букв латинского алфавита>.
Названия команд и их аргументы должны отделяться друг от друга пробелами.

Пример

Ввод

1 1
thisisanoldversion
thisisanewversion

Вывод

5
3
Old 1 8
New ew
Old 12 7

155. Скобки II или "The brackets strikes back"

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Рассмотрим все правильные скобочные последовательности длины 2N. Упорядочим их в лексикографическом порядке (считается, что открывающая скобочка меньше закрывающей) и пронумеруем их начиная с 1. Возникает задача: найти K-ую последовательность в этом упорядочении.

Входные данные

В первой строке входного файла INPUT.TXT записано число N (1<=N<=50), а во второй строке - натуральное число K (1<=K<=10^1000+255), задающее номер интересующей нас последовательности. В записи числа K возможны лидирующие нули.

Выходные данные

Выходной файл OUTPUT.TXT должен содержать ровно одну строку, в которой должна быть записана K-ая правильная скобочная последовательность длины 2N. В этом случае выходной файл не должен содержать пробелов. Если последовательностей длины 2N меньше K, то вывести сообщение "No solution for this testcase."

Пример

Ввод

2
1

Вывод

(())

Рамки

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Для данного N постройте N вложенных друг в друга квадратных рамок. Самая внешняя рамка должна состоять из цифр 0, следующая из цифр 1 и т.д. Самая внутренняя рамка должна иметь размер 2х2 и состоять из цифр (N-1).

Входные данные

Во входном файле содержится число N (1 <= N <= 10).

Выходные данные

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

Пример

Ввод

3

Вывод

000000
011110
012210
012210
011110
000000

Перепись

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

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

Входные данные

В первой строке содержится натуральное число N (1 <= N <= 1000) - количество домов на улице Вязов. Во второй строке содержится последовательность латинских букв 'К' и 'T' длины N. Буква 'K' обозначает семью Крюгеров, 'T' - Томпсонов. Порядок букв в последовательности совпадает с тем, в каком порядке они живут.

Выходные данные

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

Пример

Ввод

5
KKTKT

Вывод

1
3 4

На доске

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

На доске записано N чисел A1, A2,:, AN. Далее, пока на доске записано хотя бы одно число, повторяют следующую последовательность действий:
1) находят такое число B, которое наиболее часто встречается на доске (если таких чисел несколько, берут наименьшее);
2) выписывают B на листок бумаги;
3) если B = 1, то стирают с доски все числа, равные 1, иначе заменяют все числа В на числа (B - 1).
В конце концов, на доске не останется ни одного числа, а на листке бумаги окажутся выписанными одно или несколько чисел. Ваша задача выдать все числа на листке в порядке их записи.

Входные данные

В первой строке входного файла записано число N (1 <= N <= 3000). Далее, во второй строке записана последовательность N натуральных чисел A1, A2,..., AN через пробел (1 <= Ai <= 300, для 1 <= i <= N).

Выходные данные

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

Пример

Ввод

5
1 2 2 3 3

Вывод

5
2 1 3 2 1

Мафия

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

22 марта 20** г. крестный отец чикагской мафии соберет всю семью. Разговор пойдет не на шутку. Дон Карлионе озабочен падением доходов. Все ответственные построятся в шеренгу в порядке, соответствующем номеру района Чикаго. Всего ответственных N человек, и каждый из них назовет сумму дохода Ai в миллионах долларов со своего района (Ai может быть меньше нуля, то есть район принес убыток). Дон пойдет по порядку вдоль шеренги и будет складывать соответствующие доходы. Если в какой-то момент сумма окажется не положительной, то Дон достанет автомат Томпсона и расстреляет всех ответственных. Ответственные обеспокоены возможным исходом и поэтому хотят встать в таком порядке, чтобы все прошло без жертв. К несчастью, Дон Карлионе обладает великолепной памятью и поэтому помнит для каждого ответственного его левого и правого соседа, поэтому для выполнения задуманного они могут делать только циклические перестановки. Ваша задача указать одну из возможных циклических перестановок.

Входные данные

Во входном файле в первой строке записано количество ответственных N (1 <= N <= 150000) и во второй - последовательность целых чисел A1, A2,..., AN через пробел (-1000 <= Ai <= 1000 для 1 <= i <= N).

Выходные данные

В первой строке выведите слово "YES" если решение существует или "NO" в противном случае. Если решение существует, то во второй строке выведите номер первого человека в шеренге. Если решений несколько выведите любое из них.

Пример

Ввод

3
5 -7 4

Вывод

YES
3

Испорченный реферат

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Петя долго набирал реферат, используя только латинские буквы и пробелы. Он пользовался пиратской копией редактора "PingWord" и при финальном сохранении редактор записал сначала все согласные буквы в порядке их следования, затем все гласные, а пробелы не записал. Петя знает, что он использовал только латинские буквы. В служебных файлах редактора Петя нашел словарь слов, используемых в реферате и одну из строк реферата, преобразованную редактором. Теперь он хочет восстановить текст этой строки. Помогите ему. Считайте, что гласные буквы это 'e', 'y', 'u', 'i', 'o' и 'a'.

Входные данные

В первой строке входного файла записаны согласные буквы, во второй - гласные буквы преобразованной строки. В третьей строке записано число N (0 <= N <= 100) - количество слов в словаре. Далее идет N строк со словами из словаря. Слова в словаре могут быть не в том регистре, как в тексте. Известно, что сумма длин первых двух строк входного файла не превосходит 100 символов, и в словаре нет слов более чем из 30 букв.

Выходные данные

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

Пример

Ввод

Trnrprgrmmngsklls
Aiyouoaii
6
programming
skill
skills
train
you
your

Вывод

TrAin your programming skills

Олимпиада

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

В олимпиаде по программированию участвовало P человек, пишущих на языке Pascal, и Q человек, пишущих на C++. Требуется узнать количество способов рассадить их за компьютеры, если организаторы хотят, чтобы было ровно K участников, использующих Pascal, таких что непосредственно перед каждым из них сидит человек, использующий C++ (люди, пишущие на одном языке, неразличимы). Все участники будут сидеть подряд, один за другим (в линию) за (P + Q) компьютерами.

Входные данные

В файле записаны три целых числа P, Q и K (1 <= K <= P <= 10000, 1 <= K <= Q <= 10000), записанные через пробел.

Выходные данные

Искомое количество способов, записанное в первой строке без лидирующих нулей.

Пример

Ввод

2 2 1

Вывод

4