Problem A. Knuth-Morris-Pratt ≡

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
yezhiki nachinayut i vyygryvayut
yut
 
16

Задача 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

Problem C. 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
0.254s 0.020s 17