| Условие задачи | | Прогресс |
|
Темы:
Бинарный поиск
Сканирующая прямая
В зале ожидания на вокзале стоят 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
|
| |
![]()
|
|
Темы:
Бинарный поиск
Бинарный поиск в массиве
Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
Входные данные
Вводится одно число N
Выходные данные
Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.
| |
![]()
|
|
Темы:
Бинарный поиск
Быстрая сортировка
В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены 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 |
| |
![]()
|
|
Темы:
Бинарный поиск
Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.
Входные данные:
- в первой строке задается одно натуральное число 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 |
| |
![]()
|
|
Темы:
Бинарный поиск
Бинарный поиск в массиве
Реализуйте алгоритм приближенного бинарного поиска.
Входные данные:
- в первой строке входных данных содержатся числа 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 |
| |
![]()
|
|
Темы:
Бинарный поиск
Бинарный поиск по ответу
В многопользовательской игре 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. |
| |
![]()
|
|
Темы:
Бинарный поиск
Префиксные суммы(минимумы, ...)
Цикл лекций в университете Флатландии посвящен изучению последовательностей.
Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .
Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)
В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .
Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.
Входные данные
Первая строка входного файла содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 300 000\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .
Выходные данные
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 0 0 |
2 |
| |
![]()
|
|
Темы:
"Два указателя"
Бинарный поиск
Задача на реализацию
Томми очень любит читать. Он взял из библиотеки n книг (в i-й книге ai страниц, страницы нумеруются с 1). Томми очень бережно относится к книгам, поэтому каждую из них обернул в обложку. Но, так как у него не оказалось ни одной прозрачной обложки, он пронумеровал книжки от 1 до n и написал номер на обложке каждой книги.
Томми читает уже m дней подряд. Книги он читает строго по порядку, начиная с книги с номером 1. Каждый день он записывает на доску общее число страниц, которые прочитал к текущему дню.
Например, если бы Томми взял 2 книги и, при этом, в в первой книге 3 страницы, а во второй - 5 страниц, то прочитав в первый день 2 страницы, а во второй день - 4 страницы у Томми на доске было бы записано два числа 2 и 6.
Томми сделал небольшой перерыв, а когда вернулся к чтению понял, что забыл какую книгу читал и на какой странице остановился. Также он не хочет терять статистику, но желает исправить ее, дописав в какой день какую книгу он читал и на какой странице остановился. Помогите Томми, по записанным числам на доске, определить в какой день какую книгу он читал и на какой странице остановился.
Входные данные
Программа получает на вход несколько строк. Первая строка содержит два целых числа n и m (1 <= n, n <= 2·105) - количество книг, взятых Томми из библиотеки и количество дней, в течении которых Томми читал книги. Во второй строке следует последовательность a1, a2, ... an (1 <= a1<= 1010), где ai равно количеству страниц в i-й книге. В третьей строке следует последовательность d1, d2, ... dm (1 <= dj <= a1 + a2 +...+ an), где dj равно общему числу страниц, прочитанных Томми к j-му дню. Все dj заданы в порядке возрастания.
Выходные данные
Выведите m строк. В каждой строке выведите по два числа - номер книги k (1 <= k <= n) и номер страницы в этой книге s (1 <= s <= ak), на которой остановился Томми в текущий день.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 6
10 15 12
1 9 12 13 15 17 |
1 1
1 9
2 2
2 3
2 5
2 7 |
| 2 |
2 3
5 10000000000
5 6 9999999999 |
1 5
2 1
2 9999999994 |
| |
![]()
|