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

Первый самый быстрый#29439

В массиве хранится информацию о максимальной скорости каждой из N марок легковых автомобилей. Определить порядковый номер первого встретившегося автомобиля с самой высокой скоростью.

Входные данные
В первой строке задается число N - количество авомобилей (0<N<=50). Во второй строке задаются значения скоростей N автомобилей (N чисел, каждое число положительное, не больше 10⁵).

Выходные данные
Вывести номер первого самого быстрого автомобиля.

Примеры

№	Входные данные	Выходные данные
1	5 4 3 5 3 5	3

Одномерные массивы

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

Сигма 2015#29437

В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 100 000. Все числа не превышают 10 000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным -1.

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

Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N>6\). В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.

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

Примеры

№	Входные данные	Выходные данные
1	12 45 5 3 1 7 23 21 20 19 18 1 7	18

ЕГЭ - вычислительные задачи

✓ 334✗ 1 368700средняяВойти и решать

Сокращение дроби#29423

Дана дробь \(a \over b\). Требуется ее сократить, то есть записать это же число в виде \(c \over d\), где c — целое число, d - натуральное число и d минимальное возможное.

Входные данные
Вводятся два целых числа a и b (\(-100<=a<=100,\ 0<b<=100\)).

Выходные данные
Выведите два числа c и d.

Примеры

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

НОД и алгоритм Евклида

✓ 1 331✗ 3 701400лёгкаяВойти и решать

Расстояние Дамерау-Левенштейна#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

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

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

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

Шаблон с ? и *#28419

Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.

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

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

Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

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

Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "No solution!"

Примеры

№	Входные данные	Выходные данные
1	`AB?` `*BC`	`ABC`

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

Наибольшая общая подпоследовательность с восстановлением ответа#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лёгкаяВойти и решать

Табуляция функции 1#28407

Напишите программу, которая вычисляет значение функции z(t) при изменении x от 4 до 28 с шагом 1.
\(z = 2t^2 - 5,5t - 2\), при \(t = x+2\).

Входные данные
Ничего с клавиатуры вводить не нужно.

Выходные данные
Необходимо вывести значения z(t) для всех значений x. По одной паре (x, z) в строке. Формат вывода смотри в примере.

Примеры

№	Входные данные	Выходные данные
1		x=4 z=37.0 x=5 z=57.5 ... x=27 z=1520.5 x=28 z=1633.0

Цикл for

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

Табуляция функции 2#28406

Напишите программу, которая вычисляет значение функции z(t) при изменении a от 2 до 17 с шагом 1.
\(z = 3,5t^2 - 7t +16\), при \(t = 4a\).

Входные данные
Ничего с клавиатуры вводить не нужно.

Выходные данные
Необходимо вывести значения z(t) для всех значений a. По одной паре (a, z) в строке. Формат вывода смотри в примере.

Примеры

№	Входные данные	Выходные данные
1		a=2 z=184.0 a=3 z=436.0 a=4 z=800.0 ... a=16 z=13904.0 a=17 z=15724.0

Цикл for

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

Расстояние между точками#28346

На окружности заданы N точек, надо найти пару точек, расстояние между которыми (по хорде окружности) максимально.

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

В первой строке задано N (1 <= N <= 100 000).

В следующей строке даны N пар вещественных чисел. Сначала описывается координата x, потом – y.

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

Вывести два числа – номера точек, расстояние между которыми максимально. Сначала идет наименьшее число, потом наибольшее.

Ввод	Вывод
3 1.4142 1.4142 0 2 -1.4142 -1.4142	1 3

"Два указателя"геометрия сортировки

✓ 1✗ 4141 400средняяВойти и решать

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

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

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

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

Примеры

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

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

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

Стильная одежда - 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\).

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

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

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

Город Че#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.

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

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

Красота превыше всего#28331

В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.

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

В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета

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

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

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

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

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

Номер максимального и минимального числа#28327

Дано число N и N различных целых чисел. Необходимо вывести позицию минимального и максимального чисел среди всех N чисел.

Входные данные
В первой строке вводится число N - количество чисел (\(N<=100\)). Далее идут N чисел, по одному в строке (все числа целые, не превышающие по модулю 10 000).

Выходные данные
Вывести на экран два числа через пробел, сначала номер позиции минимального числа, затем через 1 пробел, номер позиции максимального числа.

Примеры

№	Входные данные	Выходные данные
1	5 -2 1 2 3 0	1 4

При сложностях:
Теоретическая карточка содержит подсказку.

Цикл for

✓ 4 989✗ 11 860400лёгкаяВойти и решать

Минимальное не из всех#28326

Дано число N и последовательность из N чисел. Необходимо вывести минимальное четное число среди заданных N чисел.

Входные данные
В первой строке вводится число N - количество чисел (\(N<=100\)). Далее идут N чисел по одному в строке (все числа целые, не превышающие по модулю 10 000). Среди N чисел имеется хотя бы одно четное число.

Выходные данные
Вывести на экран минимальное четное число среди всех N чисел.

Примеры

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

Цикл for

✓ 5 832✗ 16 073300лёгкаяВойти и решать

Максимальное число в последовательности#28325

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

Входные данные
В первой строке вводится число N - количество чисел (\(N<=100\)). Далее по одному в строке идут N чисел (все числа целые, не превышающие по модулю 10 000).

Выходные данные
Вывести на экран максимальное число из всех N чисел.

Примеры

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

Цикл for

✓ 6 631✗ 16 228300лёгкаяВойти и решать

Trapped in the Haybales#28323

Фермер Джон получил груз из N больших стогов сена (1≤N≤4000) и разместил эти стога в различных точках дороги, ведущей к его амбару. К несчастью, он совсем забыл, что Беси пасётся вдоль этой дороги и может оказаться в ловушке из этих стогов.

Каждый стог с номером j имеет размер S_j и уникальную позицию P_j, задающую его положение вдоль одномерной дороги. Беси начинает движение в некоторой позиции, где не было стога и может передвигаться свободно вдоль дороги, вплоть до позиции, где размещён стог сена, но она не может перейти эту позицию. В качестве исключения, если она движется в некотором направлении D единиц расстояния, она набирает достаточно скорости, чтобы протаранить любой стог сена с высотой строго меньше, чем D. Конечно, после того, как она сделает это, перед ней открывается пространство с другими стогами сена, которые она тоже может протаранить.

Беси может выйти на свободу как после самого левого, так и после самого правого стога сена. Пожалуйста, определите общую длину дороги, состоящую из тех позиций, из которых Беси не сможет выбраться. Например, если Беси не может выбраться если она начинает с позиции между стогами в позициях 1 и 5, тогда ответ будет 4 (поскольку эти позиции ограничивают область размером 4).

ФОРМАТ ВВОДА:

Первая строка ввода содержит NN. Каждая из последующих NN строк описывает стог и содержит два целых числа, определяющих его размер и позицию, каждое в диапазоне 1…10⁹.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
5 8 1 1 4 8 8 7 15 4 20	14

Задачи на моделирование

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