Задачи по программированию с проверкой решений

Найдено задач: 55Страница 1 из 5

Поиск парных маяков

В исследовательской экспедиции на неизведанной планете установлена цепь из $n$ энергетических маяков, каждый из которых излучает сигнал мощности $ai$ . Для активации защитного портала исследователю необходимо выбрать два различных маяка, суммарная мощность которых в точности равна целевому значению $k$ . Гарантируется, что среди всех маяков существует ровно одна подходящая пара. Помогите экспедиции найти 0-индексированные позиции (индексы) этих двух маяков в порядке возрастания. Входные данные - В первой строке задано целое число $n$ ( $2 \le n \le 10^5$ ) — количество маяков. - Во второй строке заданы $n$ целых чисел $a0, a1, \dots, a{n-1}$ ( $-10^9 \le ai \le 10^9$ ) — мощности маяков. - В третьей строке задано целое число $k$ ( $-2 \cdot 10^9 \le k \le 2 \cdot 10^9$ ) — требуемая суммарная мощность. Выходные данные Выведите два целых числа через пробел — 0-индексированные позиции двух маяков в порядке возрастания. --- Примеры Пример 1 Входные данные: text 4 2 7 11 15 9 Выходные данные: text 0 1 Примечание: Элементы на позициях 0 и 1 равны 2 и 7, $2 + 7 = 9$ . Пример 2 Входные данные: text 3 3 2 4 6 Выходные данные: text 1 2 Примечание: Элементы на позициях 1 и 2 равны 2 и 4, $2 + 4 = 6$ .

МассивыХеш-таблица+1

Решить

#02

Средняя

Оптимизация LRU-буфера

В ядре высоконагруженного сервиса разрабатывается модуль LRU-кэширования (Least Recently Used) фиксированной емкости $C$ . Кэш хранит пары $(key, value)$ и обрабатывает поток команд: 1. PUT key value — записать значение value по ключу key. Если ключ уже существует, обновить его значение. Если емкость $C$ исчерпана, предварительно удалить элемент, к которому обращались дольше всего (LRU). 2. GET key — запросить значение по ключу key. Если ключ присутствует в кэше, вернуть его значение и пометить ключ как самый свежий. Если ключ отсутствует, вернуть -1. Входные данные - В первой строке задано целое число $C$ ( $1 \le C \le 10^4$ ) — максимальная емкость кэша. - В последующих строках содержатся операции в формате PUT key value или GET key ( $1 \le key, value \le 10^9$ ) до конца входных данных. Выходные данные Для каждой операции GET выведите возвращенное значение в отдельной строке. --- Примеры Пример 1 Входные данные: text 2 PUT 1 1 PUT 2 2 GET 1 PUT 3 3 GET 2 PUT 4 4 GET 1 GET 3 GET 4 Выходные данные: text 1 -1 -1 3 4

Хеш-таблицаСвязный список+1

Решить

#03

Сложная

Медиана двух хроник

С двух независимых космических зондов получены отсортированные по неубыванию массивы временных меток $A$ длины $n$ и $B$ длины $m$ . Необходимо вычислить медиану объединённого отсортированного массива за асимптотическое время $O(\log(\min(n, m)))$ . Медиана объединённого массива длины $K = n + m$ : - Если $K$ нечётно, медиана равна центральному элементу с индексом $\lfloor K/2 \rfloor$ . - Если $K$ чётно, медиана равна среднему арифметическому двух центральных элементов. Входные данные - Первая строка содержит целое число $n$ ( $0 \le n \le 10^5$ ) — размер массива $A$ . - Вторая строка содержит $n$ целых чисел $A1, A2, \dots, An$ ( $-10^9 \le Ai \le 10^9$ ). Если $n = 0$ , строка пустая. - Третья строка содержит целое число $m$ ( $0 \le m \le 10^5$ , $n + m \ge 1$ ) — размер массива $B$ . - Четвёртая строка содержит $m$ целых чисел $B1, B2, \dots, Bm$ ( $-10^9 \le Bi \le 10^9$ ). Выходные данные Выведите одно число — медиану с точностью не менее 5 знаков после запятой (например, 2.00000 или 2.50000). --- Примеры Пример 1 Входные данные: text 2 1 3 1 2 Выходные данные: text 2.00000 Примечание: Объединённый массив $[1, 2, 3]$ , медиана $2.0$ . Пример 2 Входные данные: text 2 1 2 2 3 4 Выходные данные: text 2.50000 Примечание: Объединённый массив $[1, 2, 3, 4]$ , медиана $(2 + 3) / 2 = 2.5$ .

Бинарный поискМассивы+1

Решить

#04

Средняя

Слияние временных окон

Орбитальный комплекс ведёт мониторинг гравитационных аномалий. За время дежурства было зафиксировано $n$ интервалов активности. Каждый интервал задаётся парой чисел $[li, ri]$ — моментом начала и окончания аномалии. Если два или более интервала пересекаются или соприкасаются (т.е. $ri \ge lj$ при $li \le lj$ ), они объединяются в единое непрерывное окно наблюдения. Найдите минимальный набор непересекающихся интервалов, полностью покрывающих все зафиксированные аномалии. Входные данные - В первой строке задано целое число $n$ ( $1 \le n \le 10^5$ ) — количество интервалов. - В следующих $n$ строках заданы по два целых числа $li$ и $ri$ ( $0 \le li \le ri \le 10^9$ ) — границы интервалов. Выходные данные Выведите итоговые объединенные интервалы по одному в строке, упорядоченные по возрастанию времени начала. В каждой строке выведите два числа — левую и правую границу через пробел. --- Примеры Пример 1 Входные данные: text 4 1 3 2 6 8 10 15 18 Выходные данные: text 1 6 8 10 15 18 Примечание: Интервалы $[1, 3]$ и $[2, 6]$ перекрываются и объединяются в $[1, 6]$ . Пример 2 Входные данные: text 2 1 4 4 5 Выходные данные: text 1 5

Нарушения порядка

Посчитайте индексы i от 2 до n, для которых a[i] меньше предыдущего элемента. Входные данные В первой строке n. Во второй — n целых чисел a[i]. Выходные данные Количество соседних нарушений. Ограничения 1 ≤ n ≤ 100000; −10^9 ≤ a[i] ≤ 10^9. Пример 1 Ввод: text 5 3 2 2 1 4 Вывод: text 2 Пример 2 Ввод: text 1 7 Вывод: text 0

Минимальный разрыв

Найдите минимальную разность двух различных позиций после сортировки значений. Входные данные В первой строке n. Во второй — n целых чисел a[i]. Выходные данные Минимальная абсолютная разность. Ограничения 2 ≤ n ≤ 100000; −10^9 ≤ a[i] ≤ 10^9. Пример 1 Ввод: text 4 10 3 8 1 Вывод: text 2 Пример 2 Ввод: text 2 -9 9 Вывод: text 18

Сумма за один проход

Найдите сумму массива за один проход. Входные данные В первой строке n. Во второй — n целых чисел a[i]. Выходные данные Сумма всех элементов. Ограничения 1 ≤ n ≤ 100000; −10^9 ≤ a[i] ≤ 10^9. Пример 1 Ввод: text 4 1 2 -3 5 Вывод: text 5 Пример 2 Ввод: text 1 -7 Вывод: text -7

Индекс равновесия

Найдите первый индекс, для которого сумма элементов слева равна сумме справа. Сам элемент не входит в суммы. Входные данные В первой строке n. Во второй — n целых чисел a[i]. Выходные данные Индекс с 1 или −1, если такого нет. Ограничения 1 ≤ n ≤ 100000; −10^9 ≤ a[i] ≤ 10^9. Пример 1 Ввод: text 5 1 2 9 2 1 Вывод: text 3 Пример 2 Ввод: text 1 7 Вывод: text 1

Минимум лодок

В лодку помещается не более двух человек общей массы не выше c. Найдите минимум лодок. Масса каждого не превышает c. Входные данные В первой строке n. Во второй — n целых чисел a[i]. В третьей строке c. Выходные данные Минимальное число лодок. Ограничения 1 ≤ n ≤ 100000; 1 ≤ a[i] ≤ c ≤ 10^9. Пример 1 Ввод: text 4 3 2 2 1 3 Вывод: text 3 Пример 2 Ввод: text 1 5 5 Вывод: text 1

Покупки по бюджету

Купите максимум предметов, каждый не более одного раза, при бюджете b. Входные данные В первой строке n. Во второй — n целых чисел a[i]. В третьей строке b. Выходные данные Максимальное число покупок. Ограничения 1 ≤ n ≤ 100000; 1 ≤ a[i] ≤ 10^9; 0 ≤ b ≤ 10^14. Пример 1 Ввод: text 4 5 2 4 1 7 Вывод: text 3 Пример 2 Ввод: text 1 2 0 Вывод: text 0

Минимум коробок

В коробку помещается k предметов. Найдите минимальное число коробок для n предметов. Входные данные Числа n и k. Выходные данные Минимальное число коробок. Ограничения 0 ≤ n ≤ 10^12; 1 ≤ k ≤ 10^12. Пример 1 Ввод: text 10 3 Вывод: text 4 Пример 2 Ввод: text 0 7 Вывод: text 0

Ближайшие значения

Найдите минимальную абсолютную разность двух элементов на различных позициях. Входные данные В первой строке n. Во второй — n целых чисел a[i]. Выходные данные Минимальная разность. Ограничения 2 ≤ n ≤ 500; −10^9 ≤ a[i] ≤ 10^9. Пример 1 Ввод: text 3 1 10 4 Вывод: text 3 Пример 2 Ввод: text 2 -5 5 Вывод: text 10

Перебор

Решить

Каталог задач

Поиск парных маяков

Оптимизация LRU-буфера

Медиана двух хроник

Слияние временных окон

Нарушения порядка

Минимальный разрыв

Сумма за один проход

Индекс равновесия

Минимум лодок

Покупки по бюджету

Минимум коробок

Ближайшие значения