jsMath

Олимпиадная информатика-1. Занятие 2. Бинарный поиск. Часть 1. Нахождение элемента в упорядоченном списке

Список задач

Двоичный поиск

Задача A. Двоичный поиск

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

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

В первой строке входных данных содержатся натуральные числа N и K (0NK100000 ). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 109

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

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

Примеры
Входные данные
10 5
1 2 3 4 5 6 7 8 9 10 
-2 0 4 9 12
Выходные данные
NO
NO
YES
YES
NO

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

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

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

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

В первой строке входных данных содержатся числа N и K (0NK100001 ). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2109.

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

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

Примеры
Входные данные
5 5
1 3 5 7 9 
2 4 8 1 6
Выходные данные
1
3
7
1
5

Мутанты

Задача C. Мутанты

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

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

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

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

Выходной файл должен содержать M строчек. Для каждого запроса выведите число зверюшек заданного цвета в питомнике.

Примеры
Входные данные
10
1 1 3 3 5 7 9 18 18 57
5
57 3 9 1 179
Выходные данные
1
2
1
2
0

Левый и правый двоичный поиск

Задача D. Левый и правый двоичный поиск

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

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

В первой строке входных данных записано два числа N и M (1NM20000 ). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках - целые 32-битные знаковые.

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

Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Примеры
Входные данные
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
Выходные данные
10 10
3 4
7 7
1 2
0