Problem A. Longest Ordered Subsequence

Author:Far-Eastern Subregional   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ., aN) be any sequence (ai1, ai2, ., aiK), where 1 ≤ i1 < i2 < ... < iK ≤ 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

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces.

Output file format

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Constraints

1 ≤ N ≤ 1000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
7
1 7 3 5 9 4 8
4

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

Автор:Известная   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 1000

0 ≤ ai, bi ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 3
1 2 3 4 5
2 4 4
2

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

Автор:algolist   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Выходной файл должен содержать единственный символ Y или N.

Ограничения

1 ≤ N, M ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
101
bab
Y
2
4 3
1001
bab
N

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

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:phones.in   Ограничение памяти:2 Мб
Выходной файл:phones.out  

Условие

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



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

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

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

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

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

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

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

Ограничения

Букв в названии и цифр в номере не более 70.

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

Входной файл (phones.in) Выходной файл (phones.out)
1
IBM
2426
2IBM
2
APPLE
27713
APP1E

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

Автор:А. Кленин   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

Входной файл содержит целые числа B, G, TB, TG, разделенные пробелами.

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

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

Ограничения

1 ≤ B, G ≤ 50, 1 ≤ TB, TG ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 5 1 10
38

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

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

Входной файл содержит числа N и M - количество чиновников и "условий" соответственно. Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.

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

Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников. Если такой последовательности не существует (бывает же и такое!), выведите 1.

Ограничения

1 ≤ N ≤ 100000; 0 ≤ M ≤ 100000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:128 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
()
0
2
))((()
1
1 4
3
)((()((()((()(((
2
1 16
2 7

0.045s 0.003s 21