Бинарный поиск Автоматизированная система генерации тестов

Твитнуть

Плюсануть

Класснуть

Запинить

Олимпиадный тренинг

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

Лучшее место

В зале ожидания на вокзале стоят N рядов из M кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено K мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером c в ряде r, а i-й роутер расположен на месте C_i в ряде R_i, то расстояние до i-го роутера вычисляется как max(|r−R_i|,|c−C_i|), где |x| – абсолютное значение x. Креслам в зале ожидания был присвоен приоритет от 1 до N⋅M−K, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.

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

Первая строка ввода содержит четыре целых чисел — количество рядов N (2 ≤ N ≤ 10⁹) и мест в ряду M (2 ≤ M ≤ 10⁹), количество роутеров K (1 ≤ K ≤ 100, K < N⋅M), количество запросов Q (1 ≤ Q ≤ 100). Далее следует K строк, содержащих два целых числа — местонахождение роутеров: номер ряда Ri (1 ≤ R_i ≤ N) и номер места в ряду C_i (1 ≤ С_i ≤ M). Среди них нет совпадающих. Далее следует строка, содержащая Q целых чисел в диапазоне от 1 до N⋅M−K – приоритеты кресел.

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

Ввод	Вывод
4 7 2 4 2 5 4 4 1 6 16 26	1 1 2 3

Сложность двоичного поиска

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

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?

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

Вводится одно число N

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

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

Ввод	Вывод
5	3

K-квест

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

В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены N персонажей, с каждым из которых может встретиться игрок. От общения с i-м персонажем карма игрока меняется на величину ai, которая может быть как положительной, так отрицательной или даже нулем.

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

Входные данные
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

Ввод	Вывод
5 3 -2 2 -1 2 4	2 4
7 1 1 -1 1 -1 1 -1 2	5 5
4 3 2 2 2 2	-1

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

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

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

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

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

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

Приближенный двоичный поиск

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

Реализуйте алгоритм приближенного бинарного поиска.

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

В первой строке входных данных содержатся числа N и K (\(0< N,\ K <100001\)). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию. В третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит \(2 \cdot 10^9\).

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

Agar.io

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

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 1 3 4	0 0 1 1	В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

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

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

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

Профессор называет последовательность целых чисел \(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

Чтение вслух

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

Том Сойер и Гекльберри Финн вместе читают вслух вырезку из газеты. Но получилось так, что Том Сойер начал читать с i-ого символа, а Гекльберри Финн с j-ого.
Сколько букв они смогут прочитать, прежде чем обнаружат, что начали читать с разных мест или пока оба не дочитают до конца?

Входные данные:
В первой строке дана строка S (1 <= |S| <= 10⁵), состоящая из строчных латинских букв - надпись из газетной вырезки.
В следующей строке дано натуральное число q - количество запросов.
В следующих q строках дано по два натуральных числа i и j - позиции, с которых начинают читать Том Сойер и Гекльберри Финн соответственно.

Выходные данные:
Выведите q строк, в каждой из которых должно быть одно целое число - количество символов, совпадающих при чтении подстрок, начинающихся с i-ого и j-ого символа.

Примеры:

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

Поиск вершины по центру описанной окружности (O)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка O – центр описанной окружности треугольника АВС_.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка O лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

Входные данные	Выходные данные
1 1 6 3 7 1 0 6	3.784
1 2 5 1 6 -1 1 5	3.207692

Поиск вершины по центру вписанной окружности (I, инцентр)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка I – центр вписанной окружности треугольника АВС (инцентр)_.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка I лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

Входные данные	Выходные данные
1 1 7 3 8 1 1 7	4.348182
-1 3 9 1 8 -1 -1 1	6.500895

Поиск вершины по ортоцентру (H)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка H – центр пересечения высот треугольника (ортоцентр) АВС_.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка H лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

Входные данные	Выходные данные
1 1 6 3 9 1 1 5	2.454545
1 2 5 1 6 -1 1 5	3.196078

Треугольник. Поиск вершины по положению центроида

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка G – центр пересечения медиан треугольника (центроид) АВС_.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка G лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

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

Описанный четырехугольник

Бинарный поиск Вычислительная геометрия

Известно, что вокруг выпуклого четырехугольника ABCD можно описать окружность.
Найдите площадь четырехугольника ABCD, если известно:
- координаты точек A, B, C;
- точка D принадлежит отрезку EF
Входные данные:
-в 1-й строке вводятся значения Ax, Ay, Bx, By Cx,Cy – координаты точек A, B, C
-в 2-й строке вводятся значения Ex, Ey, Fx, Fy – координаты вершин отрезка EF
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10^-5.
Пример:

Входные данные	Выходные данные
1 2 8 1 10 5 5 8 14 11	36.0
3 2 4 6 9 1 5 1 0 0	15.797687719

Количество чисел на диапазоне

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

Вам даны N целых чисел A₁, ..., A_N.
На каждый из Q запросов, заданных в формате L R X, выведите количество элементов среди A_L, ..., A_R, значения которых равны X.

Входные данные
В первой строке задано целое число N (1 <= N <= 2·10⁵).
Вторая строка содержит N целых чисел A_i (1 <= A_i <= N, 1 <= i <= N).
В третьей строке задано одно целое число Q (1 <= Q <= 2·10⁵).
Каждая из следующих Q строк содержит три целых числа L, R, X (1 <= L <= R <= N, 1 <= X <= N).

Выходные данные
Выведите на экран Q строк, i-я строка содержит ответ на i-й запрос.

Примеры

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

Кардиоида

Бинарный поиск Вычислительная геометрия

Кардиоида-- плоская алгебраическая кривая 4-го порядка, которая описывается фиксированной точкой окружности радиуса , катящейся по неподвижной окружности с таким же радиусом

В прямоугольной декартовой системе координат уравнение кривой имеет вид:

Найдите координаты точки пересечения кардиоиды и отрезка EF, если известно:
- коэффициент кардиоиды a;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри кардиоиды, а другая снаружи.
Рассмотрим функцию F(x,y,a)= (x²+y²+2ax)²-4a²(x²+y²). Если для точки M с координатами (x,y) F(x,y,a)<0, то точка M лежит внутри кардиоды с параметром a. Если значение функции будет положительным, то точка M лежит снаружи.

Входные данные:
-в 1-й строке вводится вещественное число - значениe коэффициента кардиоды a (по модулю не более 10)
-в 2-й строке вводятся целые значения Ex, Ey, Fx, Fy – координаты вершин отрезка EF (числа в интервале [-1000;1000]).
Выходные данные:
1 строка - абцисса точки пересечения (координата x), с точностью не менее 10^-5
2 строка - ордината точки пересечения (координата y), с точностью не менее 10^-5

Пример:

Входные данные	Выходные данные
1.0 -1 1 1 3	0 2
-2.5 10 4 1 1	8.91545419 3.63848473

Сфера и отрезок

Вычислительная геометрия Бинарный поиск

Найдите точку пересечения отрезка AB и сферы радиуса R, с центром в точке O . Все точки заданы декартовыми координатами в пространстве. Гарантируеся, что только одна из вершин отрезка расположена внутри сферы.
Входные данные
В 1-й строке вводятся числа чисел, разделённых пробелами. Вначале вводится радиус сферы R, затем координаты центра сферы
O (O_x,O_y,O_z).
В 2-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки A (A_x,A_y,A_z), затем координаты точки
B (B_x,B_y,B_z).
Выходные данные
Выводится три числа - координаты точки пересечения. Каждая координата в отдельной строке и с точностью не менее 10^-6.
Пример 1:

Входные данные	Выходные данные
10 0 0 0 7 6 5 2 4 6	6.37704215657 5.75081686263 5.12459156869

Пример 2:

Входные данные	Выходные данные
8 1 -1 2 5 6 -5 2 -4 6	4.45729353069 4.19097843564 -3.0100762792

Эллипс и отрезок

Информатика Бинарный поиск Вычислительная геометрия

Найдите координаты точки пересечения эллипса и отрезка, если известно:
- координаты точек фокусов эллипса A, B;
- R - сумма расстояний от точки эллипса до фокусов;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри эллипса, а другая снаружи
Входные данные:
-в 1-й строке вводятся значения Ax, Ay, Bx, By, R – координаты точек A, B и сумма расстояний R
-в 2-й строке вводятся значения Ex, Ey, Fx, Fy – координаты вершин отрезка EF
Все значения целые числа в интервале [-1000;1000].
Выходные данные:
1 строка - абцисса точки пересечения (координата x), с точностью не менее 10^-5
2 строка - ордината точки пересечения (координата y), с точностью не менее 10^-5

Пример:

Входные данные	Выходные данные
-10 3 -2 7 12 -14 -9 -8 6	-10 1
3 3 6 7 7 3 4 -1 7	1.7670862633 4.9246853025

Расстояние между отрезками - 3

Бинарный поиск Бинарный поиск Вычислительная геометрия

Найдите расстояние между отрезками AB и CD. Отрезки заданы декартовыми координатами границ в пространстве.
Расстояние между отрезками - минимальное расстояние между точками X,Y, где \(X \in [A,B], \ Y\in[C,D]\).
Входные данные
В 1-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки A (A_x,A_y,A_z), затем координаты точки B (B_x,B_y,B_z).
В 2-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки C (C_x,C_y,C_z), затем координаты точки D (D_x,D_y,D_z).
Выходные данные
Выводится одно число - расстояние между отрезками AB, CD.
Расстояние необходимо найти с точностью не менее 10^-6.
Пример 1:

Входные данные	Выходные данные
-7 8 6 -6 -5 8 -7 8 6 0 -8 9	0.0

Отрезки имеют общую точку, поэтому расстояние равно 0.0
Пример 2:

Входные данные	Выходные данные
-10 -10 -8 10 7 9 -7 4 0 2 -8 -2	0.14477985167371404

Расстояние между отрезками - 3

Бинарный поиск Бинарный поиск Вычислительная геометрия

Входные данные	Выходные данные
-7 8 6 -6 -5 8 -7 8 6 0 -8 9	0.0

Отрезки имеют общую точку, поэтому расстояние равно 0.0
Пример 2:

Входные данные	Выходные данные
-10 -10 -8 10 7 9 -7 4 0 2 -8 -2	0.14477985167371404

Книги Томми

"Два указателя" Бинарный поиск Задача на реализацию

Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге a_i страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.

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

Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.

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

Входные данные
Программа получает на вход несколько строк. Первая строка содержит два целых числа n и m (1 <= n, n <= 2·10⁵) - количество книг, взятых Томми из библиотеки и количество дней, в течении которых Томми читал книги. Во второй строке следует последовательность a₁, a₂, ... a_n (1 <= a₁<= 10¹⁰), где a_i равно количеству страниц в i-й книге. В третьей строке следует последовательность d₁, d₂, ... d_m (1 <= d_j<=a₁+ a₂+...+ a_n), где d_j равно общему числу страниц, прочитанных Томми к j-му дню. Все d_j заданы в порядке возрастания.

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

Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= a_k), на которой остановился Томми в текущий день.

Примеры

№	Входные данные	Выходные данные
1	3 6 10 15 12 1 9 12 13 15 17	1 1 1 9 2 2 2 3 2 5 2 7
2	2 3 5 10000000000 5 6 9999999999	1 5 2 1 2 9999999994

Автомобиль "Пантера" - 2

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

Однажды утром Глеб с ужасом осознал, что проспал, а пары в «Высшем университете» начинаются уже скоро. Опоздать было бы не так страшно, если бы он их и не вёл. К счастью, автомобиль Глеба «Пантера» довольно мощный: для упрощения будем считать, что за одну секунду он может сначала или увеличить скорость на 1, или уменьшить скорость на 1, или не менять её, а после этого его автомобиль проезжает x метров, где x - его текущая скорость в метрах в секунду. Потом он снова принимает решение об изменении скорости. Начальная скорость автомобиля преподавателя в момент, когда он только выезжает из дома, равна нулю. Путь до университета от его дома не близкий: нужно проехать d метров.

Глеб, обеспокоенный за знания своих студентов, хочет попасть в университет как можно раньше, чтобы успеть подготовиться к проведению лекции. К сожалению, у проезда на парковку университета установлен датчик движения: если скорость проезжающего транспортного средства будет превышать s, то администрация университета выпишет нарушителю дисциплинарное взыскание. Конечно, Глеб не хочет его получить, поэтому при въезде в университет, когда автомобиль проехал все d метров его скорость x должна быть не больше s.

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

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

В двух строках заданы два целых числа - d, s (1 <= d <= 10¹⁸, 0 <= s <= 10¹⁸), расстояние до университета и ограничение на конечную скорость.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.

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

Примечание

В первом тесте из условия Глебу выгодно действовать следующим образом:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра.

Таким образом, он потратит 2 секунды, и его конечная скорость будет равно 1 м/с, что не превышает s.

Во втором тесте из условия Глебу выгодно действовать, например, так:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с, что не превышает s.

Примеры

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

Автомобиль "Пантера"

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

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

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

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

Вводится одно целое число - d (1 <= d <= 10¹⁸), расстояние до университета.

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

Примечание

В первом тесте из условия Глебу выгодно действовать следующим образом:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 2 метра от дома.
Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

Таким образом, он потратит 3 секунды, и его конечная скорость будет равно 0 м/с.

Во втором тесте из условия Глебу выгодно действовать, например, так:

Увеличить скорость на один, проехать один метр; скорость 1 м/с, проехал 1 метр.
Увеличить скорость на один, проехать два метра; скорость 2 м/с, проехал 3 метра.
Увеличить скорость на один, проехать три метра; скорость 3 м/с, проехал 6 метров.
Уменьшить скорость на один, проехать два метра; скорость 2 м/с, проехал 8 метров.
Уменьшить скорость на один, проехать один метр; скорость 1 м/с, проехал 9 метров.
Не менять скорость, проехать один метр; скорость 1 м/с, проехал 10 метров.
Уменьшить скорость на один; скорость 0 м/с, проехал 10 метров.

Таким образом, он потратит 7 секунд, и его конечная скорость будет равно 0 м/с.

Примеры

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

Путь в никуда

Деревья Деревья Структуры данных Разреженные таблицы (sparse table) Бинарный поиск Префиксные суммы(минимумы, ...)

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

Совсем другие штурмовики

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

Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — d_t, здоровье — h единиц.

Бой происходит в пошаговом режиме, пока с обеих сторон есть живые солдаты. Каждый шаг боя представляет собой одновременный выстрел всех живых солдат с обеих сторон. Каждый солдат может атаковать любого противника, но только одного. Несколько солдат с одной стороны могут атаковать одного и того же вражеского солдата. Здоровье солдата уменьшается на суммарную силу атаки солдат, атакующих его в течение этого хода. Если здоровье солдата в конце хода стало меньше или равно нулю, он погибает.

Ваша задача — уничтожить армию неприятеля, задействовав минимальное число штурмовиков, вне зависимости от действий противника, либо определить, что уничтожить вражескую армию не получится.

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*10⁵), d_e, d_t , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( d_e, d_t , h <= 10⁹). В следующей строке задано n натуральных чисел a_i — число единиц здоровья i-го солдата армии противника (a_i <= 10⁹).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.

Ввод	Вывод
3 3 1 1 2 1 2 3	3
4 10 2 1 2 1 2 1 2	5
3 1 1 2 5 1 2 3	-1

Квадраты и кубы

Целые числа Арифметические алгоритмы (Теория чисел) Бинарный поиск Линейный поиск Вещественные числа

В лаборатории теории чисел одного университета изучают связь между

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

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных

чисел от a до b, включительно. Будем называть k-плотностью этого множества количество

пар натуральных чисел x и y, таких, что a ≤ x² ≤ b, a ≤ y³ ≤ b, причем |x²– y³| ≤ k.

Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как

подходят следующие пары:

x = 1, y = 1, |x²– y³| = |1 – 1| = 0;

x = 3, y = 2, |x²– y³| = |9 – 8| = 1;

x = 5, y = 3, |x²– y³| = |25 – 27| = 2.

Требуется написать программу, которая по заданным натуральным числам a и b, а

также целому неотрицательному числу k, определяет k-плотность множества натуральных

чисел от a до b, включительно.

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

Входные данные содержат три строки. Первая строка содержит натуральное число a,

вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное

число k (1 ≤ a ≤ b ≤ 10¹⁸, 0 ≤ k ≤ 10¹⁸).

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

Выходные данные должны содержать одно целое число: искомую k-плотность

множества натуральных чисел от a до b, включительно.

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

Улучшение успеваемости

Бинарный поиск Целые числа Вывод формулы

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

Примеры округления оценок приведены в таблице.

Оценки на уроках	Среднее арифметическое	Итоговая оценка
2, 3, 5	\({ {2 + 3 + 5} \over 3 }= 3 {1 \over 3}\)	3
3, 3, 4, 4	\({ {3 + 3 + 4 + 4} \over 4 }= 3 {1 \over 2}\)	4
5, 5, 5, 3, 5	\({ {5 + 5 + 5 + 3 + 5} \over 5 }= 4 {3 \over 5}\)	5

Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок.Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.

Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.

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

Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c (0 ≤ a, b, c ≤ 10¹⁵, a + b + c ≥ 1).

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

Выходные данные должны содержать одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.

Ввод	Вывод
2 0 0	2

Старая книга

Бинарный поиск "Два указателя" Вывод формулы

Группа юных археологов работает на раскопках здания древней библиотеки. Летом

они обнаружили остатки старой книги и, изучив их, сделали следующие выводы.

Книга содержит несколько страниц, каждая страница содержит либо текст, либо

иллюстрацию. Первые k страниц книги точно содержат иллюстрации. Все страницы книги

пронумерованы, но номер страницы написан только на страницах, содержащих текст. Сумма

номеров страниц с текстом равна s.

К сожалению, ни общее количество страниц в книге, ни количество иллюстраций

установить не удалось. Тем не менее, юных археологов заинтересовал вопрос, какое

минимальное количество иллюстраций могло быть в книге.

Например, если k = 1, а s = 8, то страницы книги могли иметь следующее содержание

(буквой «Т» обозначена страница, содержащая текст, а буквой «И» — страница, содержащая

иллюстрацию):

- И Т И И И Т, пронумерованы страницы 2 и 6, 4 иллюстрации;

- И И Т И Т, пронумерованы страницы 3 и 5, 3 иллюстрации;

- И И И И И И И Т, пронумерована страница 8, 7 иллюстраций.

Минимальное количество иллюстраций равно 3.

Требуется написать программу, которая по заданным целым числам k и s определяет

минимальное количество иллюстраций, которое могло быть в книге.

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

Первая строка входных данных содержит целое число k (0 ≤ k ≤ 10⁹).

Вторая строка входных данных содержит целое число s (k + 1 ≤ s ≤ 10¹²).

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

Требуется вывести одно целое число — минимальное количество иллюстраций в

книге.

Ввод	Вывод
1 8	3

Кардиоида

Бинарный поиск Вычислительная геометрия

Входные данные	Выходные данные
1.0 -1 1 1 3	0 2
-2.5 10 4 1 1	8.91545419 3.63848473

Поиск вершины по ортоцентру (H)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Входные данные	Выходные данные
1 1 6 3 9 1 1 5	2.454545
1 2 5 1 6 -1 1 5	3.196078

Умный обогреватель

Бинарный поиск Задача на реализацию

Квартира Максима еще не прошла реновацию, поэтому температура в ней сильно зависит от температуры на улице. Для поддержания комфортной температуры он купил обогреватель и установил систему <<Умный дом>>. В соответствующую программу Максим заложил два целых числа \(t_{min} \leq t_{max}\) и следующий алгоритм использования обогревателя:

Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был выключен, и в каждый из этих дней температура на улице была строго меньше \(t_{min}\), то надо включить обогреватель в этот день и считать, что он был включен весь день. Обогреватель остается включенным и в последующие дни до тех пор, пока программа его не выключит.
Если в течение последних пяти дней до текущего дня включительно обогреватель каждый день был включен, и в каждый из этих дней температура на улице была строго больше \(t_{max}\), то надо выключить обогреватель в этот день и считать, что он был выключен весь день. Обогреватель остается выключенным и в последующие дни до тех пор, пока программа его не включит.

Из-за кратковременного отключения электроэнергии программу необходимо настроить заново. Сами значения \(t_{min}\) и \(t_{max}\) Максим забыл, зато у него остались записи программы о температуре и состоянии обогревателя в каждые из \(n\) дней использования системы.

Максим помнит, что \(t_{min}\) и \(t_{max}\) были целыми числами, по модулю не превосходящими \(10^9\) и \(t_{min} \leq t_{max}\), также он помнит, что программа не учитывала дни до первого дня использования системы и не включала обогреватель в течение первых четырех дней. Наконец, Максим помнит, что он выбирал \(t_{min}\) и \(t_{max}\) как можно более близкими друг к другу.

Помогите найти два подходящих значения \(t_{min}\) и \(t_{max}\), не превосходящих \(10^9\) по абсолютной величине, таких, что выполняются правила использования обогревателя в каждые из \(n\) дней, \(t_{min}\) не превосходит \(t_{max}\) и величина \(t_{max} - t_{min}\) минимальна.

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

Формат входных данных
В первой строке задано целое число \(n\) (\(5 \leq n \leq 10^5\)) — количество дней, в течение которых работала система.

Во второй строке входных данных задаются \(n\) целых чисел \(t_1, \dots, t_n\) (\(-10^9 \leq t_i \leq 10^9\)) — температуры на улице в каждый из \(n\) дней.

В третьей строке входных данных задается строка из \(n\) символов, состоящая из 0 и 1 — если в \(i\)-й позиции данной строки записан 0, то это значит, что в \(i\)-й день обогреватель был выключен, а если 1, — то включен.

Формат выходных данных
В единственной строке выведите два целых числа \(t_{min}\) и \(t_{max}\) (\(t_{min} \leq t_{max}\)), по модулю не превосходящих \(10^9\) — значения температур, при вставке которых в программу обогреватель будет включен и выключен в те же дни, в которые он был включен и выключен при исходных значениях, а значение \(t_{max} - t_{min}\) минимально.

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

Примечание

В первом тестовом примере первые пять дней температура строго меньше \(7\) градусов, при этом до пятого дня обогреватель был в каждый из четырех дней выключен, следовательно в пятый день программа его включила. На данный тест корректен любой ответ удовлетворяющий условию \(6 \leq t_{min} = t_{max} \leq 10^9\).

Раскраска кубиков

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

На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все n своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке a[1], a[2],...,a[n]. Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами i[1], i[2],..., i[k] покрашены в один цвет, то a[i[1]] < a[i[2]] < ... < a[i[k]]. Петя хочет использовать как можно меньше цветов. Помогите ему!

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

Первая строка входного файла содержит число n - количество кубиков у Пети (1 <= n <= 250000). Затем следует n чисел, разделенных пробелами и/или переводами строки - a[1], a[2], ..., a[n].

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

На первой строке выходного файла выведите число L - наименьшее количество цветов, которое потребуется Пете. На следующей строке выведите n чисел из диапазона от 1 до L - цвета, в которые Петя должен покрасить кубики.

Выборы

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

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

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

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

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

Формат входных данных
Первая строка содержит целое число \(n\) — количество партий (\(1 \le n \le 10^5\)). Следующие \(n\) строк описывают партии. Каждая из этих строк содержит по два целых числа: \(v_i\) — количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и \(p_i\) — взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена (\(1 \le v_i \le 10^6\), \(1 \le p_i \le 10^6\) или \(p_i = -1\)). Если партия является идеологически устойчивой, то \(p_i\) равно \(-1\). Гарантируется, что хотя бы одно \(p_i\) не равно \(-1\).

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