Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Расстояние Дамерау-Левенштейна#28421

Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	XABCDE ACBYDF	4

Динамическое программирование по подстрокам

✓ 200✗ 409700средняяВойти и решать

Проверка подпоследовательности#28420

Проверить, является ли последовательность подпоследовательностью заданного массива.

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

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

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

Выходные данные
Вывести "YES" если последовательность заданная в 4-ой строке является подпоследовательность заданного массива и "NO", если не является.

Ввод	Вывод
10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 5 4 6 7 8 9 10	NO
10 1 2 3 4 5 6 7 8 9 10 9 1 2 3 5 6 7 8 9 10	YES

Пояснение.
Не путать "подпоследовательность" с "подстрокой".

"Два указателя"

✓ 369✗ 793500лёгкаяВойти и решать

Расстояние по Левенштейну#28418

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

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

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

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

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	ABCDEFGH ACDEXGIH	3

Динамическое программирование по подстрокам

✓ 314✗ 485500лёгкаяВойти и решать

Наибольшая общая подпоследовательность с восстановлением ответа#28416

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

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 3 2 3 1	2 3

Динамическое программирование: последовательности

✓ 332✗ 489500лёгкаяВойти и решать

Наибольшая общая подпоследовательность#28415

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 3 2 3 1	2

Динамическое программирование: последовательности

✓ 493✗ 611400лёгкаяВойти и решать

Два одинаковых массива#28345

На вход подаются два массива A и В, отсортированных по неубыванию. Вам нужно узнать, существует ли такое число, которое содержится в обоих массивах. Если такое число существует, выведите 1, иначе выведите 0.

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно, (1 <= N, M <= 10⁸). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 10¹⁸.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	4 4 1 2 3 4 2 4 7 8	1

"Два указателя"Хеш

✓ 841✗ 2 034500лёгкаяВойти и решать

Метод двух указателей#28341

Дан массив из N положительных чисел. Найти в нем минимальное количество подряд идущих чисел, таких что их сумма больше K.

Входные данные
В первой строке записано число N, во второй - K (0<N<= 10⁶, 0<=K<= 10⁹). В третьей строке записаны натуральные числа последовательности.

Выходные данные
Выведите длину наименьшей последовательности чисел, сумма которых больше K. Если такой последовательности найдено не будет, то выведите -1.

Примеры

№	Входные данные	Выходные данные
1	6 7 3 1 3 2 4 3	3

"Два указателя"

✓ 944✗ 3 655400лёгкаяВойти и решать

Стильная одежда - 2#28333

Глеб обожает шоппинг. Как-то раз он загорелся идеей подобрать себе кепку, майку, штаны и ботинки так, чтобы выглядеть в них максимально стильно. В понимании Глеба стильность одежды тем больше, чем меньше разница в цвете элементов его одежды.

В наличии имеется \(N_1\) кепок, \(N_2\) маек, \(N_3\) штанов и \(N_4\) пар ботинок (\(1 \le N_i \le 100\,000\)). Про каждый элемент одежды известен его цвет (целое число от 1 до \(100\,000\)). Комплект одежды — это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.

Формат входных данных
Для каждого типа одежды \(i\) (\(i = 1, 2, 3, 4\)) сначала вводится количество \(N_i\) элементов одежды этого типа, далее в следующей строке — последовательность из \(N_i\) целых чисел, описывающих цвета элементов. Все четыре типа подаются на вход последовательно, начиная с кепок и заканчивая ботинками. Все вводимые числа целые, положительные и не превосходят \(100\,000\).

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

"Два указателя"

✓ 249✗ 451700средняяВойти и решать

Город Че#28332

В центре города Че есть пешеходная улица - одно из самых популярных мест для прогулок жителей города. По этой улице очень приятно гулять, ведь вдоль улицы расположено n забавных памятников.

Девочке Маше из города Че нравятся два мальчика из ее школы, и она никак не может сделать выбор между ними. Чтобы принять окончательное решение, она решила назначить обоим мальчикам свидание в одно и то же время. Маша хочет выбрать два памятника на пешеходной улице, около которых мальчики будут ее ждать. При этом она хочет выбрать такие памятники, чтобы мальчики не увидели друг друга. Маша знает, что из-за тумана мальчики увидят друг друга только в том случае, если они будут на расстоянии не более r метров.

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

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

В первой строке находятся два целых числа n и r (2<=n<=300 000, 1<=r<=10⁹) - количество памятников и максимальное расстояние, на котором мальчики могут увидеть друг друга.

Во второй строке задано n положительных чисел d1 ... dn, где di - расстояние от i-го памятника до начала улицы. Все памятники находятся на разном расстоянии от начала улицы. Памятники приведены в порядке возрастания расстояния от начала улицы (1<=d1 <d2< ... < dn<=10⁹).

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

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 4 1 3 5 8	2	В приведенном примере Маша может выбрать памятники 1 и 4 или памятники 2 и 4.

"Два указателя"

✓ 547✗ 1 146500лёгкаяВойти и решать

Ближайшее число#28311

Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.

Формат входных данных

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

Формат выходных данных
Вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.

Бинарный поиск

✓ 1 515✗ 4 930400лёгкаяВойти и решать

Количество сочетаний - 2#27317

По данным числам n и k (\(0 <= k <= n\), \(0< n<=60\)) вычислите количество сочетаний \(C_n^k\).

Примеры

№	Входные данные	Выходные данные
1	3 21	1330

Сочетания

✓ 84✗ 112600лёгкаяВойти и решать

Количество сочетаний#27316

По данным числам n и k (\(0 <= k <= n\), \(0< n<=12\)) вычислите количество сочетаний \(C_n^k\).

Примеры

№	Входные данные	Выходные данные
1	2 8	28

Сочетания

✓ 129✗ 128600лёгкаяВойти и решать

Шахматная доска#27315

Требуется найти число способов расставить на шахматной доске NxN K ладей так, чтобы они не били друг друга. Все ладьи считаются одинаковыми.

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

Во входном файле записаны натуральные числа N и K (\(1 <= N, K <= 8\)).

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

В выходной файл выведите одно целое число - ответ задачи.

Примеры

№	Входные данные	Выходные данные
1	8 8	40320

Сочетания

✓ 80✗ 206700средняяВойти и решать

Разность#27314

Вывести разность между количеством двоичных деревьев с N листьями и количеством разбиений N-угольника на треугольники.

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

На вход подаётся одно число - N (\(1 <= N <= 10\))

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

Выведите одно число - искомую разность

Примеры

№	Входные данные	Выходные данные
1	1	0

Комбинаторные структуры

✓ 71✗ 40500лёгкаяВойти и решать

Количество чисел Каталана#27313

Вывести N-ное число Каталана

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

Первая строка входных данных содержит одно число N (\(1 <= N <= 20\)).

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

Выведите одно число - N-ное число Каталана

Примеры

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

Комбинаторные структуры

✓ 73✗ 182700средняяВойти и решать

Тильда-омега-лямбда-исчисление#27311

Тильда-омега-лямбда-исчисление - ещё более инновационная разработка "British Scientists, Inc" в сфере функционального программирования. Его отличие от омега-лямбда-исчисления только в возможности ставить квадратные и фигурные скобки. Планировались также скобки в форме слоников, но стандарт ЮНИКОД у компании изменить не получилось.

На вход подаётся тильда-омега-лямбда-выражение длиной не более 10^7 символов. Нужно вывести результат его тильда-иззи-редукции, работающей так же, как и иззи-редукция для омега-лямбда-выражений, но с учётом квадратных и фигурных скобок.

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

Примеры

№	Входные данные	Выходные данные
1	main{izzy[lol](ttt)}	gg

Конечные автоматы Строки

✓ 96✗ 43500лёгкаяВойти и решать

Деление пополам#27290

Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа a.

Для решения используйте метод деления отрезка пополам.

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

Число a – действительное, неотрицательное, не превосходит 1000, задано с точностью до 6 знаков после запятой. Число n – натуральное, не превосходящее 10. Каждое число вводится в отдельной строке.

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

Программа должна вывести единственное число: ответ на задачу с точностью не менее 6 знаков после запятой.

Примеры

№	Входные данные	Выходные данные
1	2 2	1.41421356237

Бинарный поиск значения функции

✓ 376✗ 1 482500лёгкаяВойти и решать

Отрицательный цикл#27277

Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.

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

В первой строке содержится число N (1 <= N <= 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер по модулю меньше 100000. Если ребра нет, соответствующее значение равно 100000.

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

В первой строке выведите "YES", если цикл существует, или "NO", в противном случае.

Примеры

№	Входные данные	Выходные данные
1	3 100000 100000 -51 100 100000 100000 100000 -50 100000	YES

Алгоритм Флойда

✓ 211✗ 398500лёгкаяВойти и решать

Количество релаксаций#27274

Дан взвешенный ориентированный граф. Необходимо найти минимальное количество фаз с релаксациями в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1.

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

Программа получает на вход одно число количество вершин n (2 ≤ n ≤ 100) и количество ребер m (2 ≤m ≤ 10 000). В следующих m строках вводятся три числа: a, b и c, где a и b – начало ребра и его конец, а c – вес ребра (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10 000).

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

Программа должна вывести единственное целое число - минимальное количество релаксаций в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1.

Ввод	Вывод
4 3 1 2 1 2 3 1 3 4 1	1
4 3 2 3 1 1 2 1 1 3 4	2

(с) Шалдин В., 2017г.

Алгоритм Форда-Беллмана

✓ 28✗ 35500лёгкаяВойти и решать

Домой на электричках#27273

Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

Формат входных данных

Во входных данных записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (0 ≤ M ≤ 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа K_i (2 ≤ K ≤ N) — количества станций, на которых она останавливается, а далее следует K_i пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 10⁹). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

Формат выходных данных

Выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.

Алгоритм Дейкстры

✓ 167✗ 174700средняяВойти и решать