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

141 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Доставка товаров#45044

На конвейерной ленте расположены посылки, которые необходимо доставить из одного порта в другой в течение d дней. Судно отправляется в другой порт один раз в сутки. i-я упаковка на конвейерной ленте имеет вес wi. Судно принимает на борт грузы в том порядке, в котором они располагаются на ленте. Причем, судно не сможет вместить больше посылок, чем его максимальная грузоподъемность.

Вам известно, в каком порядке расположены посылки на конвейерной ленте. Найдите минимальную грузоподъемность судна, на котором вы сможете доставить все ваши посылки в другой порт за d дней.

 

Входные данные
Первая строка входных данных содержит натуральное число N (N <= 5·104) - количество посылок, которое необходимо доставить. Во второй строке записаны N чисел wi. i-е число означает вес i-го груза на конвейерной ленте (1 <= i <= N,1 <= wi <= 500). Груз с весом w1 погружается на судно первым.  В третьей строке записано число d (1 <= d <=  5·104)


Выходные данные
Выведите минимальную грузоподъемность судна, на котором можно доставить все посылки за d дней.
 


Пояснение
В первом примере минимальная грузоподъемность судна равна 15. Тогда судно сможет доставить наши посылки в 5 дней следующим образом:
1-й день: 1, 2, 3, 4, 5
2-й день: 6, 7
3-й день: 8
4-й день: 9
5-й день: 10
Обратите внимание, что груз должен быть отправлен в указанном порядке, поэтому использовать судно грузоподъемностью 14 и разделить посылки на части, такие как (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) не допускается.
 
Примеры
№ Входные данные Выходные данные
1 10
1 2 3 4 5 6 7 8 9 10
5		 15
2 6
3 2 2 4 1 4
3		 6
3 5
1 2 3 1 1
4		 3
Бинарный поиск по ответу
✓ 151✗ 314700средняяВойти и решать
Промежуток на числовой оси#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—Войти и решать
MEX(A)#44939
Определим функцию mex следующим образом: mex(A) — это минимальное положительное целое число, которое отсутствует в множестве A. 

Например, mex множества {1, 2, 3, 5, 100}  равен 4, а mex множества {2, 3, 4, 5}  равен 1.

У вас есть множество чисел A, состоящее из n целых положительных чисел, и положительное число k. Затем вы k раз произвели следующую операцию: добавили в множество A ещё одно число, равное mex(A), тем самым, каждый раз увеличивая размер множества A на один.

По заданному множеству A и числу k определите последнее число, которое было добавлено в множество.

Входные данные
В первой строке заданы два целых числа n и k (1<=n<=100000, 1<=k<=109) — количество чисел в множестве и количество операций добавления числа.
Вторая строка содержит n различных целых чисел a1, a2, ..., an (1<=ai<=100000) — элементы множества A.

Выходные данные
Выведите одно целое число — последнее число, которое было добавлено в множество.

Примечание
В первом примере mex множества {1, 2, 4, 5}  равен 3, после добавления mex в множество, оно станет равным {1, 2, 3, 4, 5}.

 
Примеры
№ Входные данные Выходные данные
1 
4 1
4 2 1 5
 
3
2 
7 10
1 3 20 2 7 45 5
 
15
 
Бинарный поиск по ответу
✓ 24✗ 68800средняяВойти и решать
Остановки автобуса#44938
Василий живет вдоль длинного проспекта. Вдоль проспекта по прямой ходит автобус. От метро до дома Василия N автобусных остановок. Будем считать, что метро находится у нулевой остановки, в точке с координатой 0. 

Выйдя из метро, Василий очень торопится домой, но ждать автобус на остановке Василий не любит. Так как автобус Василий не ждет никогда, то, подойдя к остановке и не увидев автобуса, он идет дальше вдоль проспекта. В случае же, если Василий заметит автобус, то он либо возвращается на остановку, либо продолжает свой путь к следующей остановке. 
Василий идет со скоростью U, автобус едет со скоростью V. Найдите минимальное расстояние L, которое должно просматриваться перед нулевой остановкой, чтобы он мог идти со своей скоростью в сторону дома, не опасаясь, что автобус его обгонит между остановками.

Входные данные
В первой строке входных данных находятся три числа N, U и V (N <= 1000, U и V – положительные вещественные), вторая строка содержит N вещественных чисел – X1, X2,... Xn (0 < X1 < X2 < … < Xn < 106), разделенных пробелами. 

Выходные данные
В выходной файл ваша программа должна вывести число L с точностью до 10-4.

 
Примеры
№ Входные данные Выходные данные
1 
1 1 10
2
 
9.0000
2 
5 1 10
1 2 4 8 16
 
28.0000
 
Бинарный поиск по ответу
✓ 27✗ 1501 000средняяВойти и решать
Эстафета#44937
На сборы по программированию пригласили N учащихся. Вечерний досуг было решено провести в виде эстафеты. Для проведения эстафеты необходимо разбить всех учащихся на R команд по С человек в каждой. По мнению руководителя сборов, команда будет тем успешнее на эстафете, чем менее будет различаться рост учащихся в одной команде. 
Числом неуспешности команды будем называть разность между ростом самого высокого и ростом самого низкого членов этой команды (если в команде только один человек, то эта разница равна 0).
Вожатые решили сформировать команды так, чтобы максимальное из чисел неуспешности сформированных команд было минимально. Пока вожатые заняты расселением учащихся по домикам, помогите им и вычислите наименьше возможное значение максимального числа неуспешности сформированных команд.

Рассмотрим следующий пример. Пусть на сборах 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две команды по три человека в каждой. Тогда одним из вариантов является такой:
1 команда: учащиеся с ростом 225, 205, 225
2 команда: учащиеся с ростом 160, 190, 170
При этом число неуспешности первой команды будет равно 20, а число неуспешности второй — 30. Максимальное из чисел неуспешности будет 30, и это будет наилучший возможный результат.

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

Выходные данные
Выведите одно число - наименьше возможное значение максимального числа неуспешности сформированных команд.

 
Примеры
№ Входные данные Выходные данные
1 
8 2 3
170
205
225
190
260
130
225
160
 
30
 
Бинарный поиск по ответу
✓ 45✗ 141800средняяВойти и решать
Исследование зеркальных цветов#44936
Члены экипажа космического корабля «Пегас» приземлились на третьей планете Системы Медуза, для изучения зеркальных цветов. Их корабль приземлился в начале узкого поля фермы, на которой выращивают цветы. Зеркальные цветы начинают прорастать после полуночи. Любезные работники фермы предоставили экипажу план прорастания цветов в виде точки и времени прорастания. Экипажу корабля необходимо улетать с планеты в следующую полночь. Исследовательская группа корабля может передвигаться по планете с максимальной скоростью vmax. На исследование одного цветка группе необходимо время d. Исследовать цветок необходимо сразу весь, нельзя будет к нему вернуться позже. Цветы прорастают тем позже, чем дальше они расположены от начала поля. В одной точке прорастает только один цветок, и каждый цветок прорастает в свой момент времени. Нет двух цветков, которые бы проросли одновременно.
Команда экипажа хочет определить момент времени, когда исследовательская группа сможет вернуться на корабль, исследовав все цветы и затратив на исследование как можно меньше времени.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит 2 целых числа через один пробел: vmax (в см/мин) и d (в минутах), 0 < vmax <= 200, 0 <= d <= 500.
Вторая строка содержит одно число N – количество цветов (в штуках). 0 <= N <= 1400 при d = 0, в противном случае 0 <= N <= 200.
Далее идут N строк, в каждой из которых записано по два числа через пробел: целое число xi – расстояние от цветка до начала поля (в сантиметрах), 0 <= xi <= 32767, и число ti – момент прорастания цветка (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

Выходные данные
Выведите момент времени возвращения исследовательской группы на корабль (в формате hh:mm), округленный до целых минут в большую сторону.

Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Можно считать, что исследовательская группа не меняет направления движения до тех пор, пока не дойдет до последнего цветка.

 
Примеры
№ Входные данные Выходные данные
1 
3 1 
1
100 00:01
 
01:08
 
Бинарный поиск по ответуЗадачи на моделирование
✓ 8✗ 631 100средняяВойти и решать
Первый, меньший данного#44935

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите минимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1).


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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 105) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅109 .


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

Для каждого из k запросов выведите минимальный номер элемента массива, меньше данного. Если таких нет, выведите 0.

 
Примеры
№ Входные данные Выходные данные
1 
5 5
9 8 5 3 3
2 4 8 1 10
 
0
4
3
0
1
Бинарный поиск в массиве
✓ 168✗ 405600лёгкаяВойти и решать
Последний элемент, не меньший данного - 2#44934

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, не меньше данного (нумерация элементов массива начинается с 1).


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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 105) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅109 .


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

Для каждого из k запросов выведите максимальный номер элемента массива, не меньше данного. Если таких нет, выведите 0.

 
Примеры
№ Входные данные Выходные данные
1 
5 5
9 8 5 3 3
2 4 8 1 10
 
5
3
2
5
0
Бинарный поиск в массиве
✓ 233✗ 395500лёгкаяВойти и решать
Последний элемент > x#44931

Дан массив из n чисел, отсортированный по невозрастанию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, большего данного (нумерация элементов массива начинается с 1).


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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 105) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅109 .


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

Для каждого из k запросов выведите максимальный номер элемента массива, большего данного. Если таких нет, выведите 0.

 
Примеры
№ Входные данные Выходные данные
1 
5 5
9 8 5 3 3
2 4 8 1 10
 
5
3
1
5
0
Бинарный поиск в массиве
✓ 260✗ 469500лёгкаяВойти и решать
Последний элемент, меньший данного#44915

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, меньший данного (нумерация элементов массива начинается с 1).


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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 105) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅109 .


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

Для каждого из k запросов выведите максимальный номер элемента массива, меньший данного. Если таких нет, выведите 0.

 
Примеры
№ Входные данные Выходные данные
1 
5 5
3 3 5 8 9
2 4 8 1 10
 
0
2
3
0
5
 
Бинарный поиск в массиве
✓ 261✗ 499400лёгкаяВойти и решать
Количество чисел - 2#44662

Дан массив a из n целых чисел a1, a2,..., an. Научитесь быстро отвечать на запросы «Сколько чисел имеют значения от l до r»?


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

В первой строке находится целое число n (1<=n<=105) — длина массива. Во второй строке находятся n целых чисел a1, a2,..., an (−109<=ai<=109). В третьей строке находится целое число k (1<=k<=105) — число запросов. В следующих k строках находятся пары чисел l r (−109<=l<=r<=109).


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

Выведите k чисел (каждое в отдельной строке) - ответы на запросы.

 
Примеры
№ Входные данные Выходные данные
1 
5
10 1 10 3 4
4
1 10
2 9
3 4
2 2
 
5
2
2
0
Бинарный поиск в массиве
✓ 264✗ 492600лёгкаяВойти и решать
Ближайшее слева#44661

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите максимальный номер элемента массива, не большего данного (нумерация элементов массива начинается с 1).


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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 105) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅109 .


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

Для каждого из k запросов выведите максимальный номер элемента массива, не большего данного. Если таких нет, выведите 0.

 
Примеры
№ Входные данные Выходные данные
1 
5 5
3 3 5 8 9
2 4 8 1 10
 
0
2
4
0
5
Бинарный поиск в массиве
✓ 423✗ 607400лёгкаяВойти и решать
Ближайшее справа#44660

Дан массив из n чисел, отсортированный по неубыванию, и k запросов. Для каждого запроса выведите минимальный номер элемента массива, не меньшего данного (нумерация элементов массива начинается с 1).


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

В первой строке входных данных содержатся числа n и k (0 < n,k <= 105) - длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы - целые числа, каждое из которых по модулю не превосходит 2·109 .


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

Для каждого из k запросов выведите минимальный номер элемента массива, не меньшего данного. Если таких нет, выведите n+1.

 
Примеры
№ Входные данные Выходные данные
1 
5 5
3 3 5 8 9
2 4 8 1 10
 
1
3
4
1
6
Бинарный поиск в массиве
✓ 195✗ 359400лёгкаяВойти и решать
МОШ и числа#44659

На заключительный этап МОШ по информатике в 2023 году пришло N участников. Так получилось, что у каждого ребенка на каком либо из предметов одежды было записано одно число. При регистрации, один из организаторов решил записать все эти числа. Позже выяснилось, что каким-то чудесным образом, все участники зарегистрировались в порядке неубывания этих чисел на одежде.  

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


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

В первой строке входного файла содержится единственное число N (0 <= N <= 105) — количество участников заключительного этапа. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 109 и разделенных пробелами — числа, записанные у участников на одежде. В третьей строке файла записано число M (1<=M<=100000) — количество чисел, информацию о которых хотят узнать судьи. В четвертой строке через пробел записаны M целых неотрицательных чисел (не превышающих 109+1).


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

Выведите M чисел, каждое в отдельной строке. Для каждого заданного в четвертой строке числа  выведите количество участников с таким числом на одежде.

Бинарный поиск в массивеСловари
✓ 75✗ 310700средняяВойти и решать
Бесконечная Дженга#44658

Громозека и Алиса придумали правила игры в бесконечную Дженгу.
В бесконченой Дженге каждый ход заключается в одном из двух действий на выбор игрока:

  • если в башне есть хотя бы один брусок, то можно вытащить и убрать из башни ровно один брусок (количество брусков в башне уменьшается на 1);
  • поставить на башню количество брусков на 1 больше, чем ставили в последний раз перед этим.
Первым ходом всегда устанавливается один брусок в пустую башню. Формально говоря, после первого хода башня состоит из одного бруска. Если после какого-то хода башня оказалась пустая (не имеет ни одного бруска), то в такую башню можно только установить брусок. Брусков для установки на башню у Алисы и Громозеки бесконечное количество.

Например, можно выполнить такую последовательность действий при игре:

1) установить один брусок на башню;
2) установить два бруска на башню;
3) убрать один брусок из башни;
4) убрать один брусок из башни;
5) установить три бруска на башню;
6) убрать один брусок из башни;
7) установить четыре бруска на башню;
8) убрать один брусок из башни;
9) установить пять брусков на башню.

После 9 ходов, количество брусокв в башне в итоге будет равно 11, а по ходу игры из башни извлекли 4 бруска.

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

 

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

В первой строке входных данных заданы два целых числа n и k (1<=n<=109; 0<=k<=109) - суммарное количество ходов и количество брусков в башне после n ходов. Гарантируется, что для заданных n и k ответ существует.


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

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

 
Примеры
№ Входные данные Выходные данные
1 
1 1
 
0
2 
9 11
 
4
3 
5 0
 
3
4 
3 2
 
1
Бинарный поиск по ответу
✓ 147✗ 156700средняяВойти и решать
Номера равных заданному#44657

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

 

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

В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве.

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

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 106.

В четвертой строке вводится M натуральных чисел, не превосходящих 109.

 

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

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

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

 
Примеры
№ Входные данные Выходные данные
1 
4
1 2 2 3
4
4 3 2 1
 
0 0
4 4
2 3
1 1
Бинарный поиск в массиве
✓ 96✗ 192600лёгкаяВойти и решать
2022#44582

Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных пар индексов, у которых первый индекс в паре меньше второго, таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует пар 1 <= i,j <= n, для которых выполняется ai+aj=2022.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.



Входные данные
В первой строке содержится одно целое число n (1 <= n <= 100000) - количество элементов массива. Во второй строке заданы n целых чисел a1, a2, ..., an (0 <= ai <= 2022) - элементы массива Эвелины.

Выходные данные
Выведите одно число - количество подходящих пар.

Примечание

В первом примере не существует пар с суммой 2022.

Во втором подходят пары (1, 2), (3, 4).

В третьем примере подходят все пары (2, 4), (2, 5), (3, 4), (3, 5). 

 
Примеры
№ Входные данные Выходные данные
1 
2
1 2022
 
0
2 
4
1000 1022 1001 1021
 
2
3 
5
700 1 1 2021 2021
 
4
Алгоритмы обработкиБинарный поиск в массивеИспользование сортировки
✓ 5✗ 22900средняяВойти и решать
Автомобиль "Пантера"#44581

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

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

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



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

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

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


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

Примечание

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

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

  3. Уменьшить скорость на один; скорость 0 м/с, проехал 2 метра от дома.

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

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

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

     

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

 
Примеры
№ Входные данные Выходные данные
1 
2

3
2 
10

7
Бинарный поиск по ответу
✓ 78✗ 274800средняяВойти и решать
Автомобиль "Пантера" - 2#44505

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

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

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



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

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

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


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

Примечание

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

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

     

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

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

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

     

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

 
Примеры
№ Входные данные Выходные данные
1 
2
1
 
2
2 
10
0
 
7
Бинарный поиск по ответу
✓ 37✗ 1981 000средняяВойти и решать
Подстрока#43798
В этой задаче Вам требуется найти максимальную по длине подстроку данной строки, такую что каждый символ встречается в ней не более k раз.

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

Выходные данные
В выходной файл выведите два числа – длину искомой подстроки и номер её первого символа. Если решений несколько, выведите любое.
Примеры
№ Входные данные Выходные данные
1 3 1
abb		 2 1
2 5 2
ababa		 4 1
"Два указателя"Бинарный поиск по ответуСтроки
✓ 23✗ 59900средняяВойти и решать
Поделиться
Класснуть