Подпоследовательности слова

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

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

 

Задано слово S длины N. Рассмотрим все 2^N подпоследовательностей этой строки (они получаются стиранием символов из строки S). Отсортируем их лексикографически (как в словаре). Ваша задача найти K-ое слово в отсортированном списке.

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

В первой строке входного файла записана строка S. Она состоит из заглавных латинских букв. Ее длина - от 1 до 50 символов. Во второй строке записано целое число K (1 <= K <= 2000000000). Число K не превосходит 2^N.

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

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

Пример

Ввод

BAB
6

Вывод

BA

Пояснение

отсортированный список имеет вид: {"", "A", "AB", "B", "B", "BA", "BAB", "BB"}.

Коньколыжная гонка

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

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

 

На зимних Берляндских олимпийских играх ввели новую дисциплину - коньколыжную гонку. Так как этот вид спорта еще не приобрел популярность, в гонке приняли участие всего 3 спортсмена. Уже известны результаты гонки! Они заданы тремя числами A1, A2, A3. Число A1 обозначает номер спортсмена, финишировавшего первым. Число A2 - номер спортсмена, финишировавшего вторым, а A3 - третьим. Ваша задача для каждого спортсмена вывести вид медали, им завоеванной. Золотая медаль обозначается числом 1, серебряная - числом 2, а бронзовая - числом 3.

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

Во входном файле в первой строке записаны три различных целых числа A1, A2, A3 (1 <= A1, A2, A3 <= 3).

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

В выходной файл выведите три целых различных числа B1, B2, B3 (1 <= B1, B2, B3 <= 3), где B1 номинал медали, завоеванной первым участником, B2 - вторым, а B3 - третьим.

Пример

Ввод

Test #1
2 3 1

Test #2
1 2 3

Вывод

Test #1
3 1 2

Test #2
1 2 3

Часы

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

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

 

Электронные часы показывают время H1 часов и M1 минут. Для изменения текущего времени на часах есть две кнопки. При нажатии первой из них количество минут увеличивается на 1. При нажатии второй кнопки как часы, так и минуты увеличиваются на 1. Если после нажатия количество часов становится равным 24, то эта величина заменяется на 0. Аналогично, если количество минут становится равным 60, то значение заменяется на 0. Часы идут неправильно. Найдите наименьшее суммарное количество нажатий, чтобы установить на часах значение H2 часов M2 минут.

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

Во входном файле в первой строке записаны целые числа H1, M1 (0 <= H1 <= 23; 0 <= M1 <= 59). Во второй строке записаны целые числа H2, M2 (0 <= H2 <= 23; 0 <= M2 <= 59).

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

В выходной файл выведите искомое наименьшее количество нажатий.

Пример

Ввод

Test #1
1 10
2 18

Test #2
23 59
00 01

Test #3
1 59
1 0

Вывод

Test #1
8

Test #2
2

Test #3
1

Мышь

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

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

 

Операционная система "Berwin XP" обрабатывает нажатия клавиши мыши следующим образом. Если подряд (без паузы) идет два нажатия клавиши мыши, то она объединяет их в "двойной щелчок" (double click). В противном случае нажатие интерпретируется как одиночный щелчок. Нажатие будем обозначать символом "С", а паузу - символом "P". Например, последовательность действий "ССPCPPCCC" воспримется системой как двойной щелчок, затем одинарный, затем двойной и снова одинарный. Ваша задача написать программу, которая анализирует последовательность действий.

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

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

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

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

Пример

Ввод

CCPCPPCCC

Вывод

4
2 1 2 1

Экзамен

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

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

 

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

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

В первой строке входного файла содержится два целых числа N, D (1 <= N <= 10000; 0 <= D <= 10^6). Вторая строка содержит последовательность различных целых чисел X1, X2,..., XN, где Xi (0 <= Xi <= 10^6) обозначает координату вдоль оси Ox i-го студента

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

В первую строку выведите Q - наименьшее количество типов билетов, необходимых для проведения экзамена. Во вторую строку выведите последовательность N целых чисел от 1 до Q. i-ое число этой последовательности обозначает номер типа билета i-го студента. Если ответов несколько, выведите любой.

Пример

Ввод

Test #1
4 1
11 1 12 2

Test #2
4 0
11 1 12 2

Test #3
4 100
11 1 12 2

Вывод

Test #1
2
1 2 2 1

Test #2
1
1 1 1 1

Test #3
4
1 3 2 4

Шары и коробки

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

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

 

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

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

Первая строка входного файла содержит целое число N (1 <= N <= 1000). Вторая строка входного файла содержит последовательность N целых чисел A1, A2,.., AN (0 <= Ai <= N; A1 + A2 +... + AN <= N).

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

В выходной файл выведите искомое минимальное количество ходов.

Пример

Ввод

Test #1
3
0 0 3

Test #2
4
1 0 0 2

Test #3
7
1 0 0 0 2 3 1

Вывод

Test #1
2

Test #2
1

Test #3
7

 

Дорожные стрессы

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

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

 

В Берляндии N городов, некоторые пары из них соединены двунаправленными дорогами. Каждая дорога описывается своей кочковатостью. Высокопоставленного зарубежного гостя везут из северной столицы в южную. Состояние гостя в каждом городе описывается тремя величинами: наименьшей и наибольшей кочковатостью дорог, по которым он уже проехал, и кочковатостью последней посещенной им дороги. Если гость проезжает по дороге, кочковатость которой меньше наименьшей им ранее увиденной, то он испытывает стресс. Аналогично, он испытывает стресс, если проезжает по дороге с кочковатостью большей текущего наибольшего значения. Полученный стресс выражается значением, равным абсолютной величине разности между кочковатостью последней посещенной (текущая не считается) и новой наименьшей или наибольшей кочковатостью. Например, если состояние гостя описывается тройкой (10, 20, 18) (наименьшая, наибольшая и текущая кочковатости), и он проезжает по дороге с кочковатостью 22, то он получает стресс 4 и переходит в состояние (10, 22, 22). Если при проезде по дороге кочковатость не превышает границ (наименьшей и наибольшей), то гость не испытывает стресс. Заметим, что состояние гостя в начале пути не определено, но при первом же проезде по берляндским дорогам, он переходит в состояние (r, r, r), где r - кочковатость первой пройденной дороги (при этом он не испытывает стресс). Какой наименьший суммарный стресс может испытать гость во время пути?

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

В первой строке записана пара чисел N, M (2 <= N <= 128; 0 <= M <= 128), где N количество городов, а M количество дорог в Берляндии. Каждая следующая строка описывает дорогу. Дорога задается тремя целыми числами x, y, r (1 <= x, y <= N; x <> y; -10^6 <= r <= 10^6), где x, y - номера соединяемых городов, а r - кочковатость дороги. Между парой городов может быть более одной дороги. Последняя строка содержит два различных числа - номера северной и южной столиц.

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

Выведите искомый наименьший суммарный стресс. Если пути до южной столицы нет, выведите -1.

Пример

Ввод

Test #1
5 4
1 2 1
2 3 5
3 4 3
4 5 0
1 5

Test #2
5 5
1 3 1
3 4 2
4 2 3
1 5 10
5 2 -10
1 2

Test #3
5 4
1 3 1
4 2 3
1 5 10
5 2 -10
1 2

Вывод

Test #1
7

Test #2
2

Test #3
20

Мафия

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

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

 

Известно, что в Берляндии мафия настолько сильна, что включает в себя бесконечное число граждан. Мафия имеет иерархическую структуру. Во главе мафии стоит Дон Берлионе. Каждый мафиози имеет двух подчиненных ему мафиози. В целях конспирации каждому члену мафии был присвоен код. Код состоит из двух целых чисел. Дон Берлионе имеет код (1, 1). У мафиози с кодом (a, b) подчиненными являются члены мафии с номерами (a + b, b) и (a, a + b). Рангом называется длина пути в иерархии до Дона Берлионе (который имеет ранг 0). Найдите ранг члена мафии с кодом (x, y).

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

Входной файл содержит два натуральных числа x и y (1 <= x,y <= 10^9).

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

В выходной файл выведите искомый ранг. Если пара (x, y) не является кодом никакого члена мафии, то выведите -1.

Пример

Ввод

Test #1
3 2

Test #2
2 1

Test #3
1000000000 1

Вывод

Test #1
2

Test #2
1

Test #3
999999999

Переливания

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

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

 

У профессора есть N емкостей. Каждая емкость характеризуется своим объемом Vi и объемом находящейся в ней воды Ai. Каждый день профессор ставит эксперимент. В j-ый день он выбирает число Pj (1 <= Pj <= N) и начинает последовательно переливать воду из Pj-ой емкости в емкости с номерами Pj+1, Pj+2,..., N. При каждом переливании профессор сливает максимальный объем воды из первой емкости во вторую, таким образом, чтобы вторая емкость не переполнилась. Найдите объем воды в каждой емкости после N экспериментов.

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

В первой строке входного файла содержится натуральное число N (1 <= N <= 100). Далее в N строках записаны описания емкостей. Каждое описание состоит из пары целых чисел Vi, Ai (1 <= Vi <= 100; 0 <= Ai <= Vi). Следующая строка содержит последовательность N чисел P1, P2,..., PN (1 <= Pi <= N).

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

В выходной файл выведите последовательность B1, B2,..., BN, где Bi - объем воды в i-ой емкости после завершения N экспериментов.

Пример

Ввод

Test #1
2
10 7
5 3
2 1

Test #2
2
5 3
11 7
1 2

Test #3
3
5 3
5 1
7 5
2 1 2

Вывод

Test #1
5 5

Test #2
0 10

Test #3
0 2 7

Байдарочный поход

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

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

 

Компания из N человек собирается пойти в байдарочный поход, i-ый человек характеризуется своей массой Mi кг. На лодочной базе имеется в наличии неограниченное количество одинаковых байдарок. Каждая байдарка может вмещать одного или двух людей. Байдарки имеют грузоподъемность D кг. Какое наименьшее количество байдарок придется арендовать компании, чтобы всем отправиться в поход?

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

В первой строке входного файла содержится пара натуральных чисел N, D (1 <= N <= 15000; 1 <= D <= 15000). Во второй строке содержится последовательность натуральных чисел M1, M2,..., MN (1 <= Mi <= D).

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

В выходной файл выведите искомое наименьшее количество необходимых байдарок.

Пример

Ввод

Test #1
4 135
50 74 60 82

Test #2
6 135
50 120 74 60 100 82

Вывод

Test #1
2

Test #2
4

Парикмахер

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

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

 

Петин папа работает парикмахером. Его парикмахерская совсем не большая, и он - единственный парикмахер, который в ней работает. Парикмахерская открывается в 9:00 и закрывается в 17:00, но папа остается на работе, пока не обслужит всех клиентов, которые зашли в парикмахерскую до 17:00.
Обслуживание в парикмахерской происходит следующим образом. Когда очередной клиент заходит в парикмахерскую то, если парикмахер свободен, он немедленно начинает стричь клиента. В противном случае клиент ждет, пока закончится стрижка всех клиентов, которые вошли в парикмахерскую перед ним.
Папин помощник записывает каждый момент времени, когда в парикмахерскую заходит очередной клиент. По этим записям, а также по моменту времени, когда закончилось обслуживание последнего клиента, папа хочет определить, какое минимальное время могла продолжаться самая долгая стрижка. Помогите ему. Известно, что стрижка занимает не менее пяти минут.
Требуется написать программу, которая по информации о моментах входа в парикмахерскую всех клиентов, а также моменту окончания стрижки последнего клиента, определит, какое минимальное время могла продолжаться самая долгая стрижка.

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

Первая строка входного файла содержит число n - количество клиентов, обслуженных в рассматриваемый день (1 <= n <= 50). Следующие n строк содержат моменты входа клиентов в парикмахерскую в формате hh:mm. Последняя строка файла содержит время выхода последнего клиента в формате hh:mm. Времена входа клиентов заданы в порядке их входа в парикмахерскую, они находятся в диапазоне от 09:00 до 17:00. Время выхода последнего клиента находится в диапазоне от 09:00 до 18:59.

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

В выходной файл выведите искомое число. Ответ выводите не менее чем с 8 знаками после десятичной точки. Если решения не существует, выведите -1.

Пример

Ввод

Test #1
2
09:00
16:22
17:52

Test #2
3
09:00
09:22
09:22
10:11

Test #3
1
16:59
17:00

Вывод

Test #1
90.00000000000000000

Test #2
23.666666666667

Test #3
-1

Коробки

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

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

 

У команды программистов есть N коробок. Каждая коробка характеризуется своей массой Mi и своей прочностью Pi. Коробки можно выстраивать в вертикальную башню, ставя их друг на друга. На каждой коробке, кроме верхней, располагается одна другая коробка. Для каждой коробки суммарная масса всех коробок, расположенных выше нее, не должна превосходить ее прочности. Найдите наибольшую высоту башни, которую команда программистов сможет построить из данного набора коробок.

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

Первая строка входного файла содержит целое число N (1 <= N <= 1000). Далее N строк содержат описания N коробок. Каждая коробка задается парой целых чисел Mi, Pi (1 <= Mi <= 1000; 1 <= Pi <= 1000).

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

В выходной файл выведите искомую максимальную высоту башни.

Пример

Ввод

Test #1
3
10 11
20 100
30 10

Test #2
3
11 11
20 100
30 10

Test #3
5
200 1000
200 20
600 150
700 700
400 10

Вывод

Test #1
3

Test #2
2

Test #3
3

Реформа авиалиний

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

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

 

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

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

В первой строке входного файла записана пара целых чисел N, M (1 <= N <= 200; 0 <= M <= 40000), где N - количество аэропортов, а M - количество рейсов. Далее в M строках содержатся описания рейсов. Каждый рейс задан парой различных целых чисел A, B (1 <= A, B <= N), которая обозначает, что аэропорт A соединен рейсом с аэропортом B. Между парой аэропортов может быть более одного рейса.

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

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

Пример

Ввод

Test #1
2 0

Test #2
4 4
1 2
2 3
3 4
2 3

Test #3
6 6
1 4
4 3
3 2
3 5
5 4
5 6

Вывод

Test #1
2
2 1
1 2

Test #2
1
4 1

Test #3
2
2 6
6 1

Британские монеты

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

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

 

До 1971 года в Великобритании использовались различные виды монет. Основными денежными единицами были пенни, шиллинг и фунт. В одном шиллинге ровно 12 пенни, и в одном фунте - 20 шиллингов. Необходимо N пенни перевести в фунты, шиллинги и пенни. В первую очередь необходимо перевести максимальное количество пенни в фунты, а затем из оставшихся перевести максимальное количество пенни в шиллинги.

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

В первой строке входного файла содержится целое число N (0 <= N <= 10000).

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

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

Пример

Ввод

Test #1
533

Test #2
10000

Вывод

Test #1
2 4 5

Test #2
41 13 4

Чемпионат по футболу

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

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

 

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

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

В первой строке входного файла содержится целое число N (2 <= N <= 10000) -- количество команд, участвовавших в чемпионате. Далее следует N строк, каждая описывает результат одной команды. В каждой строке записано 2 числа: количество побед и количество ничейных игр команды.

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

В выходном файле должно быть одно число -- отрыв чемпионов от ближайшего преследователя.

Пример

Ввод

Test #1
3
1 1
3 0
0 1

Test #2
3
5 5
6 2
1 1

Вывод

Test #1
5

Test #2
0

Палиндром

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

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

 

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

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

В первой строке входного файла записано число N (1 <= N <= 100000). Во второй строке записана последовательность из N больших латинских букв (буквы записаны без пробелов).

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

В единственной строке выходного файла выдайте искомый палиндром.

Пример

Ввод

Test #1
3
AAB

Test #2
6
QAZQAZ

Test #3
6
ABCDEF

Вывод

Test #1
ABA

Test #2
AQZZQA

Test #3
A

Шахматный этюд

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

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

 

Поскольку для программистов простые шахматы это слишком скучно, то они придумывают новые правила.
Рассмотрим шахматную доску размера N x M, на которой имеются фигуры трех типов:
· Конь (ровно один);
· Низкие фигуры;
· Высокие фигуры.
Цель коня - добраться из текущего положения в заданное новое. Причем сделать это он хочет за наименьшее число ходов.
Правила, по которым ходит конь, следующие:
· Клетки, в которые может переместиться конь, такие же, как обычно, а именно ("h" - конь, числа - возможные ходы):

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

Если на пути обоих "прыжков" встречаются высокие фигуры, то конь не может сделать такой ход. Например, обозначая низкие фигуры "+", высокие - "*":

заметим, что конь может сделать ходы, обозначенные как 1, 4 и 5. Хотя для хода 3 имеется свободное пространство, конь не умеет прыгать "зигзагом" и такой ход невозможен.

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

В файле записано 2 целых числа -- N и M (1 < N, M < 16). Далее идут N строк по M символов каждая. Символ -- это один из: "." -- пустая клетка, "+" -- низкая фигура, "*" -- высокая фигура, "h" -- начальное положение коня (ровно одно), "s" -- конечное положение коня (ровно одно).

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

Выведите L -- наименьшее количество прыжков, необходимое для перемещения из "h" в "s", либо "-1", если такое перемещение невозможно.

Пример

Ввод

4 4
h.+.
**..
.s+.
+.+.

Вывод

3

Покрытие квадратами

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

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

 

Задано квадратное поле, состоящее из символов "~" (пустое пространство) и "#" (препятствие). Ваша задача покрыть все символы "~" (и только их) заданного поля квадратами. Для этого используйте следующую стратегию:
· выбирается самый верхний (если таких несколько, то из них самый левый) непокрытый символ "~";
· выбранный символ используется как левый верхний угол некоторого нового квадрата покрытия;
· новый квадрат покрытия должен иметь наибольший возможный размер (помните, что он не должен выходить за край поля, и не должен покрывать символ/символы "#").
Какое количество квадратов будет использовано для покрытия заданного поля?

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

В первой строке входного файла записано целое число N (1 <= N <= 100) -- размер поля. Следующие N строк содержат по N символов каждая -- описание поля.

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

Выведите искомое значение.

Пример

Ввод

5
~~~~~
~~#~~
~~~~~
~~~#~
~~~~~

Вывод

9

Текст

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

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

 

Профессор Далл очень любит крупные буквы. Поэтому его студенты сдают ему курсовые, написанные исключительно заглавными буквами. Такие работы нравятся профессору. Студенты решили пойти дальше и писать работы так, что каждая буква составляет квадрат со стороной K, в котором треугольник под главной диагональю (включая диагональ) заполнен соответствующей буквой, а треугольник выше главной диагонали заполнен символами "~" (тильда, код символа 126).
Напишите программу, которая по заданному K и тексту выводит этот текст в увеличенном виде (см. примеры).

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

В первой строке входного файла записано натуральное число K (1 <= K <= 32). Во второй строке записан текст. Текст состоит из заглавных латинских букв, длина текста не менее 1 символа и не более 100.

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

Выведите искомый текст.

Пример

Ввод

Test #1
2
YES

Test #2
3
NO

Test #3
6
K

Вывод

Test #1
Y~E~S~
YYEESS

Test #2
N~~O~~
NN~OO~
NNNOOO

Test #3
K~~~~~
KK~~~~
KKK~~~
KKKK~~
KKKKK~
KKKKKK

Проверка орфографии

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

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

 

Профессор Далл разработал новую систему проверки и исправления орфографии. Расстоянием между двумя латинскими буквами в одинаковом регистре называется кратчайшее расстояние между ними по алфавиту, записанному по кругу. Например, d(B, G) = 5, а d(Z, A) = 1. Расстояние между буквами разных регистров равно расстоянию между соответствующими буквами одного регистра. Например, d(a, A) = 0, d(Z, a) = 1.
Расстоянием между двумя строками одинаковой длины называется сумма расстояний между соответствующими буквами. Метод профессора основывается на словаре правильных слов и представляет введенную последовательность в виде конкатенации слов из словаря таким образом, чтобы расстояние между заданным текстом и результатом было наименьшим. Регистр букв в тексте сохраняется. Реализуйте метод Далла.
Слово из словаря может использоваться более одного раза.

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

В первой строке входного файла содержится N (1 <= N <= 100), обозначающее количество слов в словаре. Далее в N строках содержатся слова из словаря. Длины слов -- от 1 до 32 символов включительно.
Последняя строка файла содержит текст. Текст состоит из латинских букв, длина текста не менее 1 символа и не более 1000. Возможно, словарь содержит одинаковые слова. Слова в словаре записываются буквами произвольного регистра.

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

Выведите результат. Если решений несколько, выведите любое. Если решения не существует, выведите -1.

Пример

Ввод

4
SaratoV
StaTe
The
University
SaratofStataUniversitI

Вывод

SaratovStateUniversitY

Векторы

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

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

 

Задан набор N двумерных векторов (xi, yi). Разрешается выбрать некоторый поднабор векторов и найти длину суммы векторов в поднаборе. Какое наибольшее значение можно получить?

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

Во входном файле задано число N -- количество векторов (1 <= N <= 50). Затем в N строках заданы описания векторов - парами своих координат. Все координаты целые числа, по абсолютной величине не превосходят 1000.

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

Выведите искомое значение. Абсолютная или относительная погрешность выводимого значения не должна превышать 10^-9.

Пример

Ввод

Test #1
4
1 0
0 1
0 -1
1 0

Test #2
4
1 0
0 1
-1 0
0 -1

Вывод

Test #1
2.23606797749

Test #2
1.414213562373

Каталоги

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

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

 

Задан набор путей до каталогов от корневой директории. Ваша задача по списку путей вывести в отформатированном виде дерево каталогов (см. примеры).

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

Первая строка входного файла содержит целое число N (1 <= N <= 500) -- количество заданных путей. Далее перечислены сами пути, по одному в строке. Пути не содержат пробелов. Длина каждого пути не превосходит 80 символов. Каждый путь представляет собой последовательность имен директорий, разделенных символом слэш ("\"). Длина имени каждой директории - от 1 до 8 символов. В именах директорий могут присутствовать заглавные латинские буквы, цифры и символы из набора:!#$%&'()-@^_`{}~.

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

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

Пример

Ввод

Test #1
6
USERS\KATE\01
USERS\SVETA\BOOKS\GEOMETRY
USERS\KATE\02\LECTIONS\GRAPHS
USERS\KATE\01\TASKS
USERS\SVETA\BOOKS\TREES!
WINNT

Test #2
7
WINNT\SYSTEM32\CONFIG
GAMES
WINNT\DRIVERS
HOME
WIN\SOFT
GAMES\DRIVERS
WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86

Вывод

Test #1
USERS
.KATE
..01
...TASKS
..02
...LECTIONS
....GRAPHS
.SVETA
..BOOKS
...GEOMETRY
...TREES!
WINNT

Test #2
GAMES
.DRIVERS
HOME
WIN
.SOFT
WINNT
.DRIVERS
.SYSTEM32
..CERTSRV
...CERTCO~1
....X86
..CONFIG

Пояснение

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

Обратная задача LCA

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

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

 

Дерево -- связный неориентированный граф без циклов. Корневое дерево содержит одну специальную вершину, называемую корнем дерева (вершина 2 на рисунке). Вершина w предок вершины v, если w лежит на кратчайшем пути из корня в v (в частности, вершина предок самой себя). Вершина w родитель вершины v, если w предок вершины v, и вершина w непосредственно связана с v. Например, вершины 0, 2, 4 -- предки вершины 0, а вершина 4 ее родитель.

Наименьший общий предок (LCA) вершин w и v -- такой общий предок этих двух вершин, который наиболее удален от корня. Например, LCA вершин 1 и 3 -- 2, а 5 и 0 -- 4.
Вам задан квадратный массив A целых чисел. Элемент Aij равен наименьшему общему предку вершин i и j. Восстановите структуру дерева по заданной информации. Результат выведите в виде последовательности pi, где pi -- родитель вершины. Если у вершины нет родителя (т.е. это корень), то значение pi считайте равным -1.

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

В первой строке входного файла записано натуральное число N (1 <= N <= 50) -- количество вершин в дереве. Далее в N строках записана матрица A. Все индексы в этой задаче - отсчитываются от 0. Массив Aij соответствует действительному дереву, следовательно, решение всегда существует.

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

В выходной файл выведите последовательность pi.

Пример

Ввод

7
0 2 2 2 4 4 2
2 1 2 2 2 2 6
2 2 2 2 2 2 2
2 2 2 3 2 2 2
4 2 2 2 4 4 2
4 2 2 2 4 5 2
2 6 2 2 2 2 6

Вывод

4 6 -1 2 2 4 2

Строки

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

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

 

Строка называется pi-строкой, если ее некоторое начало (префикс) совпадает с некоторым ее концом (суффиксом). Конечно, префикс (суффикс) не может быть пустым или состоять из всей строки целиком. Например, строки "AA", "ABCABC" -- pi-строки, а "AB", "ABCB" -- нет. Строка называется N-строкой, если она удовлетворяет следующим условиям:
· Она содержит только буквы из первых N букв латинского алфавита;
· Если дописать справа любую из первых N букв латинского алфавита, то в результате получится pi-строка.
Например, строка "ABBA" является 2-строкой, потому что она содержит только первые две буквы алфавита и обе строки "ABBAA" и "ABBAB" являются pi-строками. Вообще, существует бесконечное количество N-строк, но мы будем рассматривать только N-строки наименьшей длины.
Вам заданы числа N, K, left и right. Рассмотрим список всех кратчайших N-строк, упорядоченный лексикографически. Выведите подстроку с позиции left (включительно) по right (не включительно) K-ой строки в этом списке. Выведите пустую строку, если K-ая строка содержит менее right символов или она не существует. Символы строки пронумерованы от 0.

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

В первой строке входного файла находятся целые числа N, K, left, right (1 <= N <= 26; 0 <= K <= 10^9; 0 <= left <= 10^9; left + 1 <= right <= left + 1000).

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

Выведите искомую строку или пустую строку, если K-ая строка содержит менее right символов или она не существует.

Пример

Ввод

2 0 1 3

Вывод

BA