Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Бинарный поиск

Условие задачи  
ID 32967
Лучшее место
Темы: Бинарный поиск    Сканирующая прямая   

В зале ожидания на вокзале стоят N рядов из M кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено K мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером c в ряде r, а i-й роутер расположен на месте Ci в ряде Ri, то расстояние до i-го роутера вычисляется как max(|r−Ri|,|c−Ci|), где |x| – абсолютное значение x. Креслам в зале ожидания был присвоен приоритет от 1 до N⋅M−K, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.
 

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

Первая строка ввода содержит четыре целых чисел — количество рядов N (2 ≤ N ≤ 109) и мест в ряду M (2 ≤ M ≤ 109), количество роутеров K (1 ≤ K ≤ 100, K < N⋅M), количество запросов Q (1 ≤ Q ≤ 100). Далее следует K строк, содержащих два целых числа — местонахождение роутеров: номер ряда Ri (1 ≤ Ri ≤ N) и номер места в ряду Ci (1 ≤ Сi ≤ M). Среди них нет совпадающих. Далее следует строка, содержащая Q целых чисел в диапазоне от 1 до N⋅M−K – приоритеты кресел.

Вывести для каждого запроса на отдельной строке одно целое число — расстояние до ближайшего роутера от кресла с заданным приоритетом.
 
Ввод Вывод
4 7 2 4
2 5
4 4
1 6 16 26
1
1
2
3

ID 33009
Сложность двоичного поиска
Темы: Бинарный поиск   

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
 
Входные данные
Вводится одно число N
 
Выходные данные
Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.
 
Ввод Вывод
5 3

ID 34879
K-квест
Темы: Бинарный поиск    Быстрая сортировка   

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

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

Входные данные
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

Ввод Вывод
5 3
-2 2 -1 2 4
2 4
7 1
1 -1 1 -1 1 -1 2
5 5
4 3
2 2 2 2
-1

 

ID 28311
Ближайшее число
Темы: Бинарный поиск   

Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.
 
Входные данные:
- в первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива;
- во второй строке содержатся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000);
- в третьей строке вводится одно целое число x, не превосходящее по модулю 1000.
 
Выходные данные: вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.
 
Примеры
Входные данные Выходные данные
1
5
1 2 3 4 5
6
5
2
5
5 4 3 2 1
3
3

ID 27279
Приближенный двоичный поиск
Темы: Бинарный поиск   

Реализуйте алгоритм приближенного бинарного поиска.
 
Входные данные:
- в первой строке входных данных содержатся числа N и K (\(0< N,\ K <100001\));
- во второй строке задаются N чисел первого массива, отсортированного по неубыванию; 
- в третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит \(2 \cdot 10^9\).
 
Выходные данные: для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.
 
Примеры
Входные данные Выходные данные
1
5 5
1 3 5 7 9 
2 4 8 1 6 
1
3
7
1
5

ID 38466
Agar.io
Темы: Бинарный поиск   

В многопользовательской игре Agar.io игроки управляют бактериями. У каждой бактерии есть размер — целое положительное число. Если встречаются две бактерии разного размера, то бактерия большего размера поглощает меньшую бактерию. При этом меньшая бактерия исчезает, а размер большей бактерии увеличивается на размер меньшей бактерии. Если встречаются две бактерии равного размера, то ничего не происходит. Побеждает игрок, чья бактерия останется на игровом
поле одна.
В игре участвуют n игроков, вам даны размеры их бактерий. Определите, какие из игроков имеют возможность выиграть в этой игре.

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 105 — количество игроков. Следующие n строк содержат по одному числу ai — размеры бактерий, 1 ≤ ai ≤ 109. Числа ai заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
ai) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры
Входные данные Выходные данные Пояснение
1 4
1
1
3
4
0
0
1
1
В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут
съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3
может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет
съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.