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

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

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

В офисе есть \(n\) стульев, \(i\)-й из которых имеет высоту \(h_i\) и ширину \(w_i\). Влад планирует выбрать любой набор офисных стульев \([i_1, i_2, \ldots, i_k]\) и расположить в ряд, чтобы на них можно было лечь. Рост Влада равен \(H\), поэтому, чтобы он мог удобно лежать, необходимо, чтобы суммарная ширина выбранных стульев была не меньше \(H\), то есть \[\sum\limits_{j=1}^k w_{i_j} \ge H \text{.}\]

Очевидно, что спать на стульях разной высоты неудобно. Назовем неудобностью выбранного набора максимальную разность высот двух соседних стульев в ряду, то есть \(\max\limits_{j=2}^k |h_{i_j} - h_{i_{j-1}}|\). Если набор состоит из одного стула, его неудобность равна \(0\).

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

Формат входных данных
В первой строке ввода через пробел даны два целых числа \(n\) и \(H\) — количество стульев и рост Влада (\(1 \le n \le 2 \cdot 10^5\); \(1 \le H \le 10^9\)).

Во второй строке ввода через пробел перечислены \(n\) целых чисел \(h_i\) — высоты стульев (\(1 \le h_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(w_i\), равных ширине стульев (\(1 \le w_i \le 10^9\)).

Гарантируется, что \(H\) не превосходит суммы всех \(w_i\).

Формат выходных данных
Выведите единственное число — минимальное возможное неудобство среди всех подходящих наборов.


Замечание

В первом примере нужно выставить стулья \(2\) и \(4\) в любом порядке.

Во втором примере можно выбрать, например, следующие наборы: \([1, 5]\), \([2, 4, 3]\). Обратите внимание, что порядок стульев в наборе важен: неудобность набора \([2, 3, 4]\) равна \(\max(|5 - 3|, |4 - 5|) = \max(2, 1) = 2\), что больше, чем для набора \([2, 4, 3]\).

Бинарный поиск по ответуИспользование сортировкиСортировка событий
✓ 31✗ 70300лёгкаяВойти и решать
Тайлер украшает площадь#49743
Мэр Цветочного города попросил лучшего плиточника Тайлера замостить квадратную зону площади плиткой. Тайлеру были выданы коробки, в каждой из которых содержится ai квадратных плиток размером 1х1. Тайлеру поставили условие, что он должен обязательно использовать все плитки, которые ему были выданы. 
Помогите Тайлеру определить, сможет ли он использовать все плитки, чтобы замостить из всех них квадрат какого-либо размера или ему придется идти к мэру и просить еще плиток?
Считайте, что на площади можно замостить квадрат любого размера. 

Формат входных данных
В первой строке вводится натуральное число n (1 ≤ n ≤ 2·105)- количество коробок, выданных Тайлеру. Во второй строке записаны n чисел ai (1 ≤ ai ≤ 109)- количество плиток в i-й коробке.

Формат выходных данных
Выведите YES, если Тайлер сможет из всех плиток замостить квадрат какого-либо размера на площади, в противном случае выведите NO.
Бинарный поиск по ответу
✓ 23✗ 65400лёгкаяВойти и решать
Лестница#49636
Вы хотите построить лестницу и приготовили n блоков. Лестница строится путем наложения блоков друг на друга.  В i-м ряду лестницы размещается ровно i блоков. 
Определите количество полных рядов лестницы, которую вы сможете построить.



Решите задачу двоичным поиском.

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 231 - 1) - количество блоков.

Формат выходных данных
Выведите ответ на задачу.
Бинарный поиск по ответу
✓ 172✗ 393600лёгкаяВойти и решать
Бинарный (двоичный) поиск по ответу (C++)#49462
Вы - руководитель команды по разработке программных продуктов. В настоящее время вместе с командой занимаетесь выпуском нового релиза. К сожалению, последний релиз не прошел проверку качества. Поскольку каждый следующий релиз разрабатывается на основе предыдущих, все версии следующие за неудачной, также неуданы.

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими. 

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия резила плохой (возвращает True, если версия плохая, и False если хорошая).

Теперь вам необходимо реализовать функцию для поиска первой плохой версии. Вы должны как можно быстрее определить с какой версии пошел плохой релиз, поэтому количество использования функции isBadVersion(version) должно быть минимальным.
Ваша функция должна вернуть номер первого плохого релиза.
Бинарный поиск по ответу
✓ 89✗ 494900средняяВойти и решать
Бинарный (двоичный) поиск по ответу (Python)#49461
Вы - руководитель команды по разработке программных продуктов. В настоящее время вместе с командой занимаетесь выпуском нового релиза. К сожалению, последний релиз не прошел проверку качества. Поскольку каждый следующий релиз разрабатывается на основе предыдущих, все версии следующие за неудачной, также неудачны.

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими. 

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия релиза плохой (возвращает True, если версия плохая, и False если хорошая).

Теперь вам необходимо реализовать функцию для поиска первой плохой версии. Вы должны как можно быстрее определить с какой версии пошел плохой релиз, поэтому количество использования функции isBadVersion(version) должно быть минимальным.

Ваша функция должна вернуть номер первого плохого релиза.
 
Бинарный поиск по ответу
✓ 326✗ 1 428600лёгкаяВойти и решать
Бактерии#48971

В биологической лаборатории проводят эксперимент. В начале у ученых есть \(n\) замороженных бактерий, пронумерованных от \(1\) до \(n\).

Согласно плану эксперимента замороженная бактерия с номером \(i\) попадёт в чашку Петри через \(a_i\) секунд после начала эксперимента. Если таких бактерий несколько, они все попадают туда одновременно.

Как только замороженная бактерия оказывается в чашке Петри, она размораживается и начинает созревать. Созревание бактерии с номером \(i\) занимает \(t_i\) секунд. Как только бактерия созрела, она начинает размножаться: немедлено превращается в две созревшие бактерии, и затем каждая созревшая бактерия в конце каждой секунды снова делится на две созревшие бактерии.

Размером колонии называется общее количество бактерий в чашке Петри. Цель эксперимента — определить, через сколько секунд размер колонии будет в точности равен \(m\).

Помогите ученым определить искомое число секунд или выясните, что размер колонии никогда не будет в точности равен \(m\).

Формат входных данных
В первой строке даны целые числа \(n\), \(m\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le m \le 10^{9}\)) — количество замороженных бактерий и желаемый размер колонии.

Во второй строке даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)) — времена перемещения замороженных бактерий в чашку Петри.

В третьей строке даны \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le 10^{9}\)) — продолжительность созревания замороженных бактерий.

Формат выходных данных
Если размер колонии никогда не будет равен \(m\), выведите \(-1\).

В противном случае выведите число секунд после начала эксперимента, через которое размер колонии будет в точности равен \(m\).

Рассмотрим, как развивается эксперимент в первом примере.

Время Бактерия 1 Бактерия 2 Бактерия 3 Бактерия 4 Всего
0 заморожена заморожена заморожена заморожена 0
1 заморожена заморожена в чашке Петри, созревает заморожена 1
2 заморожена заморожена в чашке Петри, созревает заморожена 1
3 в чашке Петри, созревает заморожена в чашке Петри, созрела, 2 бактерии заморожена 3
4 в чашке Петри, созревает заморожена в чашке Петри, созрела, 4 бактерии заморожена 5
5 в чашке Петри, созрела, 2 бактерии в чашке Петри, созревает в чашке Петри, созрела, 8 бактерий заморожена 11
Бинарный поиск по ответу
✓ 7✗ 571 000средняяВойти и решать
Василий собирает ягоды#47308
Медведь Василий собирает ягоды. Он будет счастлив, если ягод малины в его корзинке окажется не менее трети от общего числа ягод. Медведь Василий уже собрал N ягод, из них K штук малины. Василий уже изрядно устал собирать ягоды, поэтому помогите ему понять, какое минимальное число ягод малины ему необходимо собрать, чтобы быть счастливым. 


Входные данные
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N, K<=109, N<=2*109), записанные в отдельных строках, — текущее количество ягод в корзинке медведя Василия и количество ягод малины в корзинке.

Выходные данные
Выведите единственное число — минимальное число ягод малины, которое необходимо собрать.

 
Примеры
№ Входные данные Выходные данные Примечание
1 27
7		 3 В примере всего ягод в корзинке 27, из которых малины 7 ягод.
Если в собрать ещё 3 ягоды малины, то в корзинке станет 30 ягод, из которых малины будет 10.

 
Бинарный поиск по ответуВывод формулыЦелые числа
✓ 54✗ 632700средняяВойти и решать
Чебурашка и мандарины#45059

Чебурашка обожает мандарины. Сейчас он оказался на новогодней ярмарке среди большого количества ящиков с мандаринами. В i-м ящике bi мандаринов. Ярмарка начинает свою работу через h часов.

Чебурашка очень умный и может выбрать скорость поедания мандаринов -  k мандаринов в час. Затем он каждый час выбирает ящик мандаринов и уплетает k штук из этого ящика. Если в ящике меньше k мандаринов, то Чебурашка съест их все и больше не притронется ни к одному мандарину в течение этого часа.

Чебурашка любит есть медленно, но желает съесть все мандарины до открытия ярмарки.

Помогите найти Чебурашке минимальную скорость поедания мандаринов, но такую, чтобы он все-таки смог съесть все мандарины.
 


Входные данные
В первой строке записано число n (1 <= n <= 104) - количество ящиков с мандаринами. Вторая строка содержит n чисел bi - количество мандаринов в i-м ящике (1 <= bi <= 109). В третьей строке записано число h (n <= h <= 109) - через сколько часов открывается ярмарка.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 4
3 6 7 11
8		 4
2 5
30 11 23 4 20
5		 30
3 5
30 11 23 4 20
6		 23
Бинарный поиск по ответу
✓ 220✗ 274700средняяВойти и решать
Распределение продуктов#45058

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

- Каждому магазину распределяется не более одного типа товара, но любое его количество.
- После распределения каждому магазину предоставляется некоторое количество товаров (возможно нулевое).

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

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



Входные данные
Первая строка входных данных содержит два натуральных числа, записанных через пробел: n и m (1 <= m <= n <= 105) - количество розничных магазинов и количество типов товаров. Во второй строке содержится m целых чисел qi - количество i-го типа товара (0 <= i < 105,  1 <= qi <= 105).
 
Выходные данные
Выведите минимально возможное x.
 
Примечание
В первом тестовом примере оптимальным распределением будет следующее:
- 11 продуктов типа 0 распределяются по первым четырем магазинам в следующих количествах: 2, 3, 3, 3
- 6 продуктов типа 1 распределяются по двум другим магазинам в следующих количествах: 3, 3
Максимальное количество товаров, предоставляемых в любой магазин, составляет max(2, 3, 3, 3, 3, 3) = 3.
Примеры
№ Входные данные Выходные данные
1 6 2
11 6		 3
2 7 3
15 10 10		 5
3 1 1
100000		 100000
Бинарный поиск по ответу
✓ 71✗ 167800средняяВойти и решать
Доставка товаров#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средняяВойти и решать
Бесконечная Дженга#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средняяВойти и решать
Автомобиль "Пантера"#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средняяВойти и решать
Чтение вслух#39673
Том Сойер и Гекльберри Финн вместе читают вслух вырезку из газеты. Но получилось так, что Том Сойер начал читать с i-ого символа, а Гекльберри Финн с j-ого. 
Сколько букв они смогут прочитать, прежде чем обнаружат, что начали читать с разных мест или пока оба не дочитают до конца?

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

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

Примеры:
 
Входные данные Выходные данные
abacaba
4
1 5
3 5
4 2
2 6		 3
1
0
2
Бинарный поиск по ответуПрефиксные суммы(минимумы, ...)Хеш
✓ 1✗ 131 300средняяВойти и решать
Поделиться
Класснуть