Хабрахабр

[Из песочницы] Разбор задач. Бинпоиск_1

Серия статей содержит разбор задач, которые дают в 8 классе на уроках информатики в Челябинском физико-математическом лицее №31. Здравствуйте, уважаемые хабровчане. Ученики регулярно побеждают на олимпиадах всероссийского и международного уровня.
Данная статья лишена теории, она содержит только способы решения задач. Немного истории… Наш лицей — одно из сильнейших учебных заведений России, который в рейтинге по конкурентоспособности выпускников занимает 5 место, уступив школам Москвы и Санкт-Петербурга. Как мы знаем бинпоиск — это алгоритм поиска объектов по заданному признаку в множестве объектов. Подробно про бинпоиск описано здесь.
Так вот, перейдем к задачам. Эти задачи подразумевают собой использование бинарного поиска, в том числе бинпоиска по ответам. Всего 4 задачи, 2 из которых направлены на применение "алгоритма без изюминок". Применяем для отсортированных по возрастанию/убыванию списков.

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

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

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for x in b: left = -1 right = len(a) #левый бинпоиск, который ищет левую границу while right - left > 1: middle = (right + left) // 2 if a[middle] < x: left = middle else: right = middle left_1 = -1 right_1 = len(a) #правый бинпоиск, который ищет правый границу while right_1 - left_1 > 1: middle = (right_1 + left_1) // 2 if a[middle] <= x: left_1 = middle else: right_1 = middle if left == left_1 and right == right_1: print(0) #возращение к следующей итерации с пропуском, что идет после него continue if right == left_1: print(right + 1, right + 1) else: print(right + 1, left_1 + 1)

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

Тут надо так преобразовать поиск, чтобы выполнялось даже для чисел, которых нет в данном для поиска списке. Вот эта задачка с изюминкой! Все это делаем, пока левая граница меньше правой. Здесь мы также ищем середину в “граничном списке”, затем элемент, который посередине сравниваем с числом, если он меньше него, мы записываем в левую границу(который индекс) индекс середины + 1(то есть не включаем прошлую середину в граничный список), в ином случае в правую границу записываем индекс середины. Поэтому выводим a[left — 1], в ином случае a[left]. После нахождения left и right рассматриваем случай, когда числа нет в списке и расстояние до того, что левее меньше или равно, чем то, что правее.

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for x in b: left = 0 right = n - 1 while left < right: middle = (left + right) // 2 if a[middle] < x: left = middle + 1 else: right = middle if left > 0 and a[left] != x and abs(a[left - 1] - x) <= abs(a[left] - x): print(a[left - 1]) else: print(a[left])

Квадратный корень и квадратный квадрат

Задача на бинарный поиск по ответу. Тадам! Далее как в типичном бинпоиске ищем середину, позже сравниваем. Для начала из библиотеки math подключим функцию sqrt, которая вычисляет квадратный корень, после определим для левой границы 0, а для правой 1e10, то есть 10 миллиардов, исходя из ограничений, которые указаны в условии. Тут middle — это x в уравнении. Но что тут интересного? С). Ввиду этого определяем значение уравнения и сверяем с реальным ответом(т.е. Позже умножаем на миллион, округляем, переводим в int и вещественное деление на тот же миллион. Ну и двигаем границы, до тех пор, пока разность границ не будет меньше или равна 10-ти миллиардным, это и есть точность измерения.

from math import sqrt
c = float(input())
left = 0
right = 1e10#1 c 10-тью нулями
while right - left > 10e-10:#10 нулей и 1 middle = (left + right) / 2 if middle * middle + sqrt(middle) >= c: right = middle else: left = middle
#умножаем на 10e6, округляем, преобразуем в int, делим на 10e6
print(int(round(left*10e6))/10e6)

Очень Легкая Задача

Разбор на эту задачу уже есть, поэтому приложу только код.

n, x, y = map(int, input().split())
min1 = min(x, y)
if n == 1: print(min1)
else: left = 0 right = n * (x + y - min1 + 1) while right - left > 1: middle = (right + left) // 2 if n - 1 <= middle // x + middle // y: right = middle else: left = middle print(min1 + left + 1)

Для закрепления материала можно порешать задачи отсюда.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть