Задача A. Быстрая помощь ≡

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности a_i минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

Требуется определить минимальное время в минутах, требуемое на перелёт и разгрузку всех самолётов.

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

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

Ограничения

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

2 10
8 5

25

Задача B. Шалтай-Болтай ≡

Условие

Шалтай-Болтай очень любит ходить по своей стене в разные стороны и кушать пирожки. Сверху стена выглядит как длинная полоска из одинаковых клеток, пронумерованных по возрастанию слева направо. Каждый день Шалтай-Болтай может выполнить одно из трёх действий:

• сдвинуться влево на R_i клеток;
• сдвинуться вправо на R_i клеток;
• скушать пирожок.

Число клеток R_i зависит от текущего дня недели. Шалтай-Болтай считает, что в неделе M дней.

В начальный момент времени Шалтай-Болтай находится на клетке с номером ноль, имеет K пирожков и считает, что сейчас первый день недели.

Требуется найти минимальное количество дней Q, через которое он может оказаться в клетке с номером D, или определить, что это невозможно.

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

Во входном файле содержатся числа D K M. Далее следует M целых чисел R_i — количество клеток, на которое Шалтай может сдвинуться в i-й день недели.

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

В выходном файле должно содержаться единственное число Q, либо −1, если добраться до клетки D невозможно.

Ограничения

−2 × 10⁴ ≤ D ≤ 2 × 10⁴

0 ≤ K ≤ 10

1 ≤ M ≤ 10

1 ≤ R_i ≤ 2 × 10⁴

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

4 1 2
2 10

3

1 5 1
3

-1

Задача C. Vasin Multimedia Player ≡

Условие

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

Изучив некоторые аналогичные программы, Вася решил реализовать следующий алгоритм: когда пользователь выбирает файл для воспроизведения, то вместе с этим файлом добавляются также все "похожие" на него файлы в алфавитном порядке. Файлы добавляются даже в случае, если они уже есть в списке воспроизведения. Файлы считаются "похожими", если их имена имеют (непустое) одинаковое начало, после которого идёт символ разделителя либо конец строки. Разделителями считаются символы ' ' (пробел, ASCII 32), '_' (подчёркивание, ASCII 95) и '-' (минус, ASCII 45).

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100; 0 ≤ M ≤ 100. Все имена файлов различны, состоят из маленьких латинских букв, цифр и разделителей и имеют длину от 1 до 100 символов.

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

11
five_-_dont_wanna_let_u_go
symphony 40 part 2 andante
ace of base_-_all_that_she_wants
queen - radio ga ga
symphony 40 part 1 allegro
ace of base_-_happy_nation
symphony
five and queen_-_we will rock you
symphony 40
ace of base_-_beautiful_life
queen - the_show_must_go_on
4
symphony 40
queen - radio ga ga
five and queen_-_we will rock you
symphony 40 part 1 allegro

symphony
symphony 40
symphony 40 part 1 allegro
symphony 40 part 2 andante
queen - radio ga ga
queen - the_show_must_go_on
five and queen_-_we will rock you
five_-_dont_wanna_let_u_go
symphony
symphony 40
symphony 40 part 1 allegro
symphony 40 part 2 andante

Задача D. Этажерка ≡

Условие

Изображение этажерки состоит из H × S + D − 1 строк по W + D − 1 символов.

Этажерка имеет четыре вертикальных ножки, обозначаемые символом '|' (ASCII 124), S полок, обозначаемых символом '/' (ASCII 47) и 2 × S горизонтальных перекладин длиной W, обозначаемых символом '=' (ASCII 61).

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

Все символы изображения, не относящиеся к этажерке, должны быть равны '.' (ASCII 46).

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

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

Ограничения

1 ≤ S ≤ 100

2 ≤ W, H, D ≤ 100

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

2 20 5 4

...====================
..////////////////////|
.////////////////////.|
====================..|
|..|...............|..|
|..================|===
|./////////////////|//|
|//////////////////|/.|
====================..|
|..|...............|..|
|..................|...
|..................|...
|..................|...