Даны две последовательности, требуется найти длину их наибольшей общей подпоследовательности.
В первой строке входных данных содержится число \(N\) – длина первой последовательности \((1 \leq N \leq 10^3)\). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие \(10^4\) по модулю.
В третьей строке записано число \(M\) – длина второй последовательности \((1 \leq M \leq 10^3)\). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие \(10^4\) по модулю.
Требуется вывести одно число – длину наибольшей общей подпоследовательности двух данных последовательностей или 0, если такой подпоследовательности нет.
| Ввод | Вывод |
|---|---|
3 1 2 3 3 2 3 1 |
2 |
3 1 2 3 3 3 2 1 |
1 |
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.
В первой строке входных данных содержится число \(N\) – длина первой последовательности \((1 \leq N \leq 10^3)\). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие \(10^4\) по модулю.
В третьей строке записано число \(M\) – длина второй последовательности \((1 \leq M \leq 10^3)\). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие \(10^4\) по модулю.
Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.
| Ввод | Вывод |
|---|---|
3 1 2 3 3 2 3 1 |
2 3 |
3 1 2 3 3 3 2 1 |
1 |
Дана последовательность, требуется найти длину её наибольшей возрастающей подпоследовательности. Подпоследовательностью последовательности называется некоторый набор её элементов, не обязательно стоящих подряд.
В первой строке входных данных задано число \(N\) - длина последовательности \((1 \leq N \leq 10^3)\). Во второй строке задается сама последовательность (разделитель - пробел). Элементы последовательности - целые числа, не превосходящие \(10^4\) по модулю.
Требуется вывести длину наибольшей строго возрастающей подпоследовательности.
| Ввод | Вывод |
|---|---|
6 3 29 5 5 28 6 |
3 |
10 4 8 2 6 2 10 6 29 58 9 |
5 |
Дана последовательность, требуется найти её наибольшую возрастающую подпоследовательность.
В первой строке входных данных задано число \(N\) - длина последовательности \((1 \leq N \leq 10^3)\). Во второй строке задается сама последовательность (разделитель - пробел). Элементы последовательности - целые числа, не превосходящие \(10^4\) по модулю.
Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности. Если таких подпоследовательностей несколько, необходимо вывести одну (любую) из них.
| Ввод | Вывод |
|---|---|
6 3 29 5 5 28 6 |
3 5 28 |
10 4 8 2 6 2 10 6 29 58 9 |
4 8 10 29 58 |
Числовая последовательность задана рекуррентной формулой: \(a_{i+1} = k \cdot a_i + b \mod m\). Найдите длину её наибольшей возрастающей подпоследовательности.
Программа получает на вход пять целых чисел: длину последовательности \(n\) \((1 \leq n \leq 10^5)\), начальный элемент последовательности \(a_1\), параметры \(k\), \(b\), \(m\) для вычисления последующих членов последовательности \((1 \leq m \leq 10^4)\), \(0 \leq k \lt m\), \(0 \leq b \lt m, 0 \leq a_1 \lt m\)).
Требуется вывести длину наибольшей возрастающей подпоследовательности данной последовательности.
| Ввод | Вывод |
|---|---|
5 41 2 1 100 |
3 |
7 1 2 1 10 |
4 |
Числовая последовательность задана рекуррентной формулой: \(a_{i+1} = k \cdot a_i + b \mod m\). Найдите длину её наибольшей возрастающей подпоследовательности.
Программа получает на вход пять целых чисел: длину последовательности \(n\) \((1 \leq n \leq 10^5)\), начальный элемент последовательности \(a_1\), параметры \(k\), \(b\), \(m\) для вычисления последующих членов последовательности \((1 \leq m \leq 10^4)\), \(0 \leq k \lt m\), \(0 \leq b \lt m, 0 \leq a_1 \lt m\)).
Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности, разделяя числа пробелами. Если таких последовательностей несколько, необходимо вывести одну (любую) из них.
| Ввод | Вывод |
|---|---|
5 41 2 1 100 |
41 67 71 |
7 1 2 1 10 |
1 3 5 7 |
Дана текстовая строка. С ней можно выполнять следующие операции:
1. Заменить один символ строки на другой символ.
2. Удалить один произвольный символ.
3. Вставить произвольный символ в произвольное место строки.
Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.
Минимальное количество таких операций, при помощи которых можно из одной строки получить другую, называется стоимостью редактирования или расстоянием Левенштейна.
Определите расстояние Левенштейна для двух данных строк.
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
Требуется вывести одно число – расстояние Левенштейна для данных строк.
| Ввод | Вывод |
|---|---|
ABCDEFGH ACDEXGIH |
3 |