Задача A. Наибольшая возрастающая подпоследовательность ≡

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

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

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

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

Ограничения

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

5
123 456 124 124 125

3
1 4 5

Задача B. Наибольшая общая подпоследовательность ≡

Условие

Найдите наибольшую общую подпоследовательность двух строк.

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

В первой строке находится первая строка, во второй строке находится вторая строка. Строки состоят только из маленьких латинских букв.

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

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

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

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

ababaca
acaba

aaba

Задача C. Геройская армия ≡

Условие

Слон Пахом любит играть в игру "Герои меча и магии". У Пахома есть N героев. У каждого героя в армии содержится ровно 7 различных видов существ (существ одного вида может быть много). Всего в игре существует 14 различных существ (7 видов, 1-го или 2-го уровня). У каждого существа есть сила p_i. Существа первого и второго уровня считаются различными, и их нельзя объединять без предварительного улучшения существ 1-го уровня до 2-го. Сила существа второго уровня не меньше силы того же существа первого уровня. Существа первого уровня обозначаются маленькими буквами латинского алфавита (a, b, c, d, e, f, g), второго — большими буквами латинского алфавита (A, B, C, D, E, F, G). Любое существо 1-го уровня можно улучшить до 2-го уровня потратив c_i денег. Пахому лень разделять группы существ, поэтому он может улучшить группу существ в какой либо армии только полностью. Улучшения происходят следующим образом a->A, b->B, c->C и т.д.

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

Наиболее сильную армию можно было бы получить, улучшив всех существ и собрав армию из 7 видов существ 2-го уровня. Однако на это может не хватить монет, поэтому необходимо выбрать, какие группы существ улучшать. Помогите Пахому собрать максимально сильную армию и при этом потратить не более M монет.

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

Первая строка входного файла содержит два числа N и M, количество героев и количество денег игрока.

Вторая строка содержит 14 чисел p_i, мощность одного существа видов a, b, c, d, e, f, g, A, B, C, D, E, F, G. соответственно.

Третья строка содержит 7 чисел с_i, стоимость улучшения одного существа видов a, b, c, d, e, f, g, соответственно.

Далее следует N строк, каждая строка содержит 7 пар, t_ij q_ij — вид существа и количество существ этого вида у i-го героя.

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

Выходной файл должен содержать одно число — максимальную силу собранной армии.

Ограничения

1 ≤ N ≤ 50

0 ≤ M ≤ 5000

0 ≤ p_i, c_i, q_i ≤ 1000

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

2 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
a 5 b 5 c 6 d 6 e 6 f 7 g 8
A 10 B 10 C 10 D 10 E 10 F 10 G 10

80

2 50 
0 1 2 3 4 5 6 1 2 3 4 5 6 7
1 1 1 1 1 1 1
A 10 B 20 C 30 D 40 E 50 F 60 G 70
a 400 B 300 C 100 D 100 E 100 F 400 G 500

9100

3 50 
0 1 2 3 4 5 6 1 2 3 4 5 6 7
1 1 1 1 1 1 1
a 1000 b 500 c 0 d 0 e 0 f 0 g 0
A 10 B 20 C 30 D 40 E 50 F 60 G 70
a 400 B 300 C 100 D 100 E 100 F 400 G 500

9590

Задача E. Унисон ≡

Условие

Два друга-ирландца Фаолан и Леон очень любят петь, особенно в праздники, когда они могут собраться и петь песни вместе. Хоть они и друзья, у них не так много общих песен, но это не мешает им пытаться петь разные песни одновременно.

Друзья обнаружили, что разные строки двух песен совместимы и могут быть спеты в унисон, если у строк одинаковая интонация, а количество слогов в этих строках совпадает. Интонация строки считается восклицательной, если в строке есть восклицательный знак (ASCII 33), и нейтральной во всех остальных случаях.

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

Когда Фаолан и Леон поют, они следуют по текстам своих песен слева направо, сверху вниз, с удовольствием распевая в унисон совместимые строки и пропуская все остальные.

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

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

В первой строке входных данных содержатся целые числа N M: количество строк в первой и второй песне соответственно. Далее следуют N + M строк, содержащих текст первой и затем второй песни. Каждая строка может состоять только из печатных ASCII символов.

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

Выходные данные должны содержать одно целое число: максимальное количество децисекунд, в течение которых друзья могут петь в унисон.

Ограничения

1 ≤ N, M ≤ 10⁶

N*M ≤ 10⁷

Длина каждой строки не превосходит 50.

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

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

3 4
It's funny how the war goes on
Without John, without our John
La la la la la, la la!
We're so young and so gone
Let's chase the dragon from our home
Ah ah from our home!
From our home

17

Задача F. Автобусы ≡

Условие

Перевозка пассажиров происходит по следующему алгоритму: автобус приходит на вокзал и ожидает пассажиров, пока они не займут все M мест. Новый автобус приходит на вокзал каждые d минут, первый автобус приезжает в момент времени 0. Время ожидания пассажира  — это время, пока он стоит на остановке (если автобус стоит на остановке, а пассажир находится в нём, это не считается за ожидание).

Перевозчику пришли новые требования к перевозке пассажиров: теперь суммарное время ожидания для всех пассажиров не должно превышать T минут.

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

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

Первая строка входного файла содержит три целых числа N, M и T. Следующая строка содержит N целых чисел t_i. Гарантируется, что первый автобус не может забрать всех пассажиров.

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

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

Ограничения

0 ≤ N, M ≤ 10⁶; 1 ≤ t_i ≤ 10⁶; 1 ≤ T ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

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

5 3 3
5 4 3 2 1

6

6 3 6
6 6 6 6 6 6

8