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

76 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Бинарный поиск в невозрастающем массиве - 4.2#49455
Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 
Бинарный поиск в массиве
✓ 94✗ 271500лёгкаяВойти и решать
Бинарный поиск в невозрастающем массиве - 4.1#49454
Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 
Бинарный поиск в массиве
✓ 111✗ 313500лёгкаяВойти и решать
Бинарный поиск в невозрастающем массиве - 3#49453
Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 
Бинарный поиск в массиве
✓ 119✗ 212500лёгкаяВойти и решать
Бинарный поиск в невозрастающем массиве - 2#49452
Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента большего или равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 
Бинарный поиск в массиве
✓ 117✗ 264500лёгкаяВойти и решать
Бинарный поиск в невозрастающем массиве - 1#49451
Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента большего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 
Бинарный поиск в массиве
✓ 115✗ 578500лёгкаяВойти и решать
Гласная подстрока#48030
Дана строка s. Определите длину самой длинной подстроки, состоящей только из гласных букв. В ответе укажите длину данной подцепочки.

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

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

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

Формат выходных данных
Выведите ответ на задачу.
ЕГЭ_информатикаПоиск подстроки в строкеСтроки
✓ 62✗ 330700средняяВойти и решать
Василий собирает ягоды#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✗ 627700средняяВойти и решать
Чебурашка и мандарины#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средняяВойти и решать
Доставка товаров#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средняяВойти и решать
Первый, меньший данного#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лёгкаяВойти и решать
Поделиться
Класснуть