Алгоритмы поиска

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

Формат входных данных
В единственной строке содержится одно слово, состоящее из строчных латинских букв от "a" до "z" (2 ≤ n ≤ 106) 

Формат выходных данных
Выведите одно слово - новое название компании. Если название не~изменилось, выведите изначальное название.
 
Задача на реализациюЛинейный поискСтроки
✓ 94✗ 458800средняяВойти и решать
Гласная подстрока#48030
Дана строка s. Определите длину самой длинной подстроки, состоящей только из гласных букв. В ответе укажите длину данной подцепочки.

Формат входных данных
Программа получает на вход строку s (10 <= s <= 106). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z). Гласные буквы английского алфавита: AEIOUY.

Формат выходных данных
Выведите ответ на задачу.
 
Поиск подстроки в строкеСтроки
✓ 71✗ 164600лёгкаяВойти и решать
Самая длинная подстрока#48025
Дана строка s  Определите длину самой длинной подцепочки, состоящей из одинаковых символов. В ответе укажите сначала символ, из которого строится данная подцепочка, затем, слитно без разделителей, длину данной подцепочки. Если таких подцепочек несколько, то укажите ту, в которой буква стоит раньше в алфавите.

Формат входных данных
Программа получает на вход строку s (10 <= s <= 106). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z).

Формат выходных данных
Выведите ответ на задачу.
ЕГЭ_информатикаПоиск подстроки в строкеСтроки
✓ 62✗ 330700средняяВойти и решать
Слияние списков#47668

У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список. 
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)). 
 

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

Выходные данные
Программа должна вывести последовательность неубывающих чисел, полученных объединением двух данных списков.
 
Примеры
№ Входные данные Выходные данные
1 1 5 7
2 4 4 5		 1 2 4 4 5 5 7
"Два указателя"Одномерные массивы
✓ 53✗ 191800средняяВойти и решать
Василий собирает ягоды#47308
Медведь Василий собирает ягоды. Он будет счастлив, если ягод малины в его корзинке окажется не менее трети от общего числа ягод. Медведь Василий уже собрал N ягод, из них K штук малины. Василий уже изрядно устал собирать ягоды, поэтому помогите ему понять, какое минимальное число ягод малины ему необходимо собрать, чтобы быть счастливым. 


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

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

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

 
Бинарный поиск по ответуВывод формулыЦелые числа
✓ 55✗ 635700средняяВойти и решать
Чебурашка и мандарины#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средняяВойти и решать
Первый, меньший данного#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
 
Бинарный поиск в массиве
✓ 263✗ 500400лёгкаяВойти и решать
Количество чисел - 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✗ 498600лёгкаяВойти и решать
Ближайшее слева#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
Бинарный поиск в массиве
✓ 429✗ 636400лёгкаяВойти и решать
Ближайшее справа#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
Бинарный поиск в массиве
✓ 204✗ 373400лёгкаяВойти и решать
Поделиться
Класснуть