Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Динамическое программирование: последовательности
---> 46 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#1709
Страх и ненависть в Вес-Лагасе
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В Вес-Лагасе построили новый отель. В отеле бесконечное количество номеров (отелей с конечным количеством номеров для гостей Вес-Лагаса не хватает).

Гости Вес-Лагаса очень суеверные: они испытывают страх перед числом 13 и ненавидят номера, в десятичной записи которых присутствует это число. Поэтому в отеле нет комнат, которые содержат 13 в записи своего номера. Например, в отеле нет комнат с номерами 13, 132, 913, 1308, 1313. Требуется определить, какой номер имеет N-я по счету комната.

Входные данные

Входной файл содержит несколько тестовых блоков. Первая строка содержит число T (1 ≤ T ≤ 100) – количество тестовых блоков.

Каждая из следующих T строк описывает один тестовый блок и содержит единственное число N 
(\(1 \leq N \leq 10^{18}\)).

Выходные данные

Выведите ответ для каждого тестового блока в отдельной строке.

Примеры
Входные данные
3
20
150
1
Выходные данные
21
162
1
#1720
НОВП
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Входные данные

Во входном файле записаны две последовательности. Каждая последовательность описывается двумя строками следующим образом: в первой строке идет длина последовательности \(M\) (1 \(\le\) \(M\) \(\le\) 500), во второй идут \(M\) целых чисел \(a_i\) (\(−2^{31}\) \(\le\) \(a_i\) < \(2^{31}\)) – члены последовательности. Нужно найти возрастающую последовательность наибольшей длины, являющейся подпоследовательностью обоих данных последовательностей.

Выходные данные

В первой строке выходного файла выведите \(N\) - длину наибольшей общей возрастающей подпоследовательности.

Во второй строке выходного файла выведите саму подпоследовательность.

Примеры
Входные данные
5
1 4 2 5 -12
4
-12 1 2 4
Выходные данные
2
1 2
#1790
НОП с восстановлением
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

Входные данные

В первой строке входных данных содержится число \(N\) – длина первой последовательности (1 ≤ \(N\) ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число \(M\) – длина второй последовательности (1 ≤ \(M\) ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Выходные данные

Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.

Примеры
Входные данные
3
1 2 3
3 
2 3 1
Выходные данные
2 3
#1791
Расстояние по Левенштейну
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

Дана текстовая строка. С ней можно выполнять следующие операции:

1. Заменить один символ строки на другой символ.

2. Удалить один произвольный символ.

3. Вставить произвольный символ в произвольное место строки.

Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.

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

Определите расстояние Левенштейна для двух данных строк.

Входные данные

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

Выходные данные

Требуется вывести одно число – расстояние Левенштейна для данных строк.

Примеры
Входные данные
ABCDEFGH
ACDEXGIH
Выходные данные
3
#1792
НВП с восстановлением ответа
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Дана последовательность, требуется найти её наибольшую возрастающую подпоследовательность.

Входные данные

В первой строке входных данных задано число \(N\) - длина последовательности (1 ≤ \(N\) ≤ 1000). Во второй строке задается сама последовательность (разделитель - пробел). Элементы последовательности - целые числа, не превосходящие 10000 по модулю.

Выходные данные

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

Примеры
Входные данные
6
3 29 5 5 28 6
Выходные данные
3 5 28
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест