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

Промежуток на числовой оси#44940

На числовой оси, в промежутке от L до R, Василий нарисовал N вертикальных палочек. Подумав, Василий решил, что ему на числовой оси необходим пустой промежуток шириной не менее W.
Помогите определить Василию, какое минимальное количество палочек необходимо стереть Василию и какие именно.
После того как Василий сотрет некоторое количество палочек, должен найтись промежуток шириной больше или равной W. Промежуток может располагаться между двумя оставшимися палочками, или между оставшейся палочкой и концом промежутка числовой оси, или между двумя концами промежутка числовой оси.

Входные данные
Первая строка содержит два целых числа N и W — количество нарисованных палочек и минимально необходимую ширину промежутка соответственно. Гарантируется, что 0 <= N <= 1 000 000 и 0 <= W <= 1 000 000.
Во второй строке находятся два числа L и R — координаты левого и правого конца промежутка числовой оси (L <= R). В третьей строке записаны N чисел — координаты нарисованных палочек. Все координаты (включая L и R) — различные целые числа, по модулю не превосходящие 1 000 000. Гарантируется, что все палочки нарисованы между левым и правым концами стороны.

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

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

Примеры

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

Бинарный поиск по ответу

✓ 1✗ 5—Войти и решать

Эффективные сборы#43870

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

1 <= l <= r <= n;
a_l = a_l+1 = a_l+2 =…=a_r;
l = 1 или a_l-1 > a_l;
r = n или a_r < a_r+1;

Примеры

Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:

1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);

2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);

3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).

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

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 2·10⁵) — длину массива. Вторая строка n целых чисел a_i (1 <= a_i<= 10⁹) — количество решенных Лукой задач в i-й день .

Выходные данные
Выведите YES, если сборы Луки оказались эффективными, и NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	`7` `5 3 3 2 3 3 4`	YES
2	`11 2 2 2 3 4 4 5 6 7 7 8`	YES
3	`7 1 2 3 4 3 2 1`	NO

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

✓ 6✗ 12—Войти и решать

Треугольник Максима#43772

С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент — треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.

У Максима есть профессиональный музыкальный тюнер, с помощью которого можно проигрывать ноту с заданной частотой. Максим действует следующим образом: он включает на тюнере ноты с разными частотами и для каждой ноты на слух определяет, ближе или дальше она к издаваемому треугольником звуку, чем предыдущая нота. Поскольку слух у Максима абсолютный, он определяет это всегда абсолютно верно.

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

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

Входные данные
Первая строка входного файла содержит целое число n — количество нот, которые воспроизводил Максим с помощью тюнера (2 ≤ n ≤ 1000). Последующие n строк содержат записи Максима, причём каждая строка содержит две компоненты: вещественное число f_i — частоту, выставленную на тюнере, в герцах (30 ≤ f_i ≤ 4000), и слово «closer» или слово «further» для каждой частоты, кроме первой.

Слово «closer» означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: |f_i−f_треуг.| < |f_i−1−f_треуг.|

Слово «further» означает, что частота данной ноты дальше, чем предыдущая.

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

Гарантируется, что результаты, полученные Максимом, непротиворечивы.

Выходные данные
В выходной файл необходимо вывести через пробел два вещественных числа — наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом. Числа должны быть выведены с точностью не хуже 10⁻⁶.

Примеры

№	Входные данные	Выходные данные
1	3 440 220 closer 300 further	30.0 260.0
2	4 554 880 further 440 closer 622 closer	531.0 660.0

"Два указателя"Пересечение множеств

✓ 2✗ 0—Войти и решать

Гармоничная последовательность#39381

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка входного файла содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 300 000\)).

Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .

Выходные данные
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Примеры

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

Бинарный поиск Префиксные суммы(минимумы, ...)

✓ 3✗ 5—Войти и решать

Вырубка леса#33093

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Программа должна работать быстрее, чем за линейный поиск

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

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X (1 ≤ A, B ≤ 109 , 2 ≤ K, M ≤ 1018, 1 ≤ X ≤ 1018).

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

Выходной файл должен содержать одно целое число — искомое количество дней.

Ввод	Вывод
2 4 3 3 25	7

Бинарный поиск по ответу

—Войти и решать

Ski Course Rating#27302

Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.

Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет успешно достичь как минимум T ячеек решётки (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D.

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

INPUT FORMAT:

* Строка 1: Целые числа M, N, T.

* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.

* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка

OUTPUT FORMAT:

* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).

INPUT DETAILS:

Местность описывается решеткой из 3 х 5 высот.

Верхняя левая и правая нижняя ячейки являются стартовыми точками.

Из каждой стартовой точки мы должны быть способны добраться до 10 ячеек.

OUTPUT DETAILS:

Рейтинг трудности верхнего левого угла равен 4.

Рейтинг трудности правого нижнего угла равен 20.

Ввод	Вывод
3 5 10 20 21 18 99 5 19 22 20 16 17 18 17 40 60 80 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1	24

Бинарный поиск по ответу графы Поиск компонент связности

—Войти и решать