Problem A. Longest Ordered Subsequence ≡

Statement

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence (a₁, a₂, ., a_N) be any sequence (a_i1, a_i2, ., a_iK), where 1 ≤ i₁ < i₂ < ... < i_K ≤ N. For example, the sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences of this sequence are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input file format

Output file format

Constraints

Sample tests

7
1 7 3 5 9 4 8

4

Задача B. Лотерея ≡

Условие

Недавно организация ACM (Association Consuming Money) объявила о проведении лотереи по новой схеме. Участник, купив билет, должен написать в нем последовательность чисел некоторой длины. При розыгрыше случайным образом выбирается другая последовательность, причем ее элементы могут повторяться.

Общая подпоследовательность определяется как последовательность чисел, которую можно получить вычеркиванием чисел как из первой последовательности, так и из второй.

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

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

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

Вторая строка содержит N целых чисел a_i разделенных пробелами — последовательность участника.

Третья строка содержит M целых чисел b_i разделенных пробелами — последовательность, полученная при розыгрыше.

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

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

Ограничения

1 ≤ N, M ≤ 1000

0 ≤ a_i, b_i ≤ 10⁹

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

5 3
1 2 3 4 5
2 4 4

2

Задача C. 0 - a, 1 - ab ≡

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

• заменять символ 0 на строку из одного или более символов a
• заменять символ 1 на строку из одного или более символов a, либо на строку из одного или более символов b

Требуется определить, можно ли преобразовать строку s в строку t при помощи указанных действий.

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

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

Вторая строка входного файла содержит строку s.

Третья строка входного файла содержит строку t.

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

Ограничения

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

3 3
101
bab

Y

4 3
1001
bab

N

Задача D. Телефонный номер ≡

Условие

Вероятно, вы обращали внимание, что клавиатура многих телефонов выглядит следующим образом:



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

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

Например, если фирма называется IBM, а номер телефона — 246, то замена его на BIM недопустима, тогда как замена на 2IM или B4M является правильной.

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

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

Ограничения

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

IBM
2426

2IBM

APPLE
27713

APP1E

Задача E. Мальчики, девочки и бревно ≡

Условие

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

Известно время T_B, за которое перейдет по бревну мальчик и время T_G, за которое перейдет девочка. Требуется найти минимальное время T, за которое может переправиться вся группа.

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

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

Ограничения

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

2 5 1 10

38

Задача F. Бюрократия ≡

Условие

В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата. Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник. Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого. Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы гарантировала, что никто из них ему не откажет.

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

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

Ограничения

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

4 3
1 2
1 3
3 4

1 3 2 4

Задача G. Замена скобок: минимизация шагов ≡

Условие

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

• пустая строка является правильной скобочной последовательностью;
• если S — правильная скобочная последовательность, то (S) — тоже правильная скобочная последовательность.
• если A и B — правильные скобочные последовательности, то AB — тоже правильная скобочная последовательность.

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

Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной последовательности и скобки в ней меняются на противоположные, то есть все символы '(' в этой подстроке заменяются на ')', а все символы ')' — на '('.

Требуется написать программу, которая по скобочной последовательности рассчитает минимальное количество шагов N, необходимое для превращения её в правильную.

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

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

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

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

Если решения не существует, выведите единственное число −1.

Ограничения

Длина исходной последовательности находится в диапазоне от 1 до 3000 символов

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

()

0

))((()

1
1 4

)((()((()((()(((

2
1 16
2 7