Задание №168964: Информация и кодирование

11 класс, 16.02.2026 Задача B. Очередь в столовую Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Женя пришел в столовую и увидел, что в очереди стоит n человек. У каждого человека есть предел терпения t — сколько секунд он готов ожидать своей очереди, и время заказа k — сколько i i секунд он делает заказ. Время ожидания человека — это суммарное время заказа для всех людей перед ним. Гарантируется, что изначально время ожидания для каждого человека в очереди не превосходит его предел терпения. Женя — очень дружелюбный человек, поэтому знает всех, кто стоит в очереди, и может встать в любое место. Он хочет встать как можно ближе к началу очереди, но не хочет, чтобы из-за него чье-то время ожидания превысило предел терпения. При этом у самого Жени терпение бесконечно. Формат входных данных В первой строке дано одно целое число cases (1 ⩽ cases ⩽ 10000) — количество наборов входных данных. Далее следуют описания каждого из наборов входных данных. В первой строке каждого набора входных данных записано два целых числа n и d (1 ⩽ n ⩽ 105, 1 ⩽ d ⩽ 109) — количество людей в очереди и длительность заказа Жени. В i-й из последующих n строк записаны два целых числа t и k (1 ⩽ t ,k ⩽ 109) — предел i i i i терпения и длительность заказа i-го человека в очереди. Пусть N равно сумме n по всем наборам входных данных. Гарантируется, что N ⩽ 106 Формат выходных данных Выведите, на какое минимальное по счёту место может встать Женя. Система оценки Всего в этой задаче 20 тестов (не считая теста из условия). Оценка потестовая, каждый из тестов, кроме теста из условия, оценивается в 5 баллов. На некоторые из тестов наложены дополнительные ограничения, указанные в таблице. Обозначим за N сумму по n по наборам входных данных. Номер теста Дополнительные ограничения Комментарий 1 — Тест из условия 2,3 n ⩽ 10,N ⩽ 100 — 4,5,6 Все t равны — i 7,8,9 k = d = 1 — i 10,11,12,13,14 n ⩽ 1000,N ⩽ 10000 — 15,16,17,18,19,20,21 — — Пример стандартный ввод стандартный вывод 2 1 3 2 5 5 1 6 2 10 3 4 3 2 2 4 1 5 3 8 2 Страница 2 из 9 Высшая проба 2026