Экзамены и диагностики

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... (см. условие задачи из демо-варианта 2025 года). Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px ‐ среднее арифметическое абсцисс центров кластеров, и Py ‐ среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 100 000, затем целую часть абсолютного значения произведения Py × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Исходные данные находятся в файлах 27-29a.txt и 27-29b.txt.

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... (см. условие задачи из демо-варианта 2025 года). Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px ‐ среднее арифметическое абсцисс центров кластеров, и Py ‐ среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 100 000, затем целую часть абсолютного значения произведения Py × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Исходные данные находятся в файлах 27-28a.txt и 27-28b.txt.

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба... (см. условие задачи из демо-варианта 2025 года). Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. При расчётах аномалии учитывать не нужно.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px ‐ среднее арифметическое абсцисс центров кластеров, и Py ‐ среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 100 000, затем целую часть абсолютного значения произведения Py × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Исходные данные находятся в файлах 27-27a.txt и 27-27b.txt.

(М. Крючков) В лесу выделено несколько мест (кластеров), где растёт много деревьев, предназначенных для вырубки После спиливания дерева его нужно доставить в точку сбора, которая совпадает с одним из деревьев кластера. Стоимость доставки определяется как расстояние от дерева до точки сбора, умноженное на высоту дерева. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁, y₁) и B(x₂, y₂) на плоскости, которое вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\). В каждом кластере нужно найти оптимальную точку сбора (центроид), такую что суммарная стоимость доставки в это место всех спиленных деревьев данного кластера минимальна. Аномалиями назовём точки, находящиеся на расстоянии более 30 м от точек кластеров. При расчётах аномалии учитывать не нужно.

В файле A хранятся данные о двух кластерах. Каждый кластер имеет форму прямоугольника размером 100 100 м. Каждая строка файла содержит три характеристики одного дерева: координату x, затем координату y и затем высоту дерева. Количество деревьев в каждом кластере не превышает 1000. В файле Б той же структуры хранятся данные о трёх кластерах, каждый из которых имеет вид прямоугольника размером не более 100 200 м. Количество точек в каждом кластере не превышает 10 000.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px ‐ среднее арифметическое абсцисс центров кластеров, и Py ‐ среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 100 000, затем целую часть абсолютного значения произведения Py × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Исходные данные находятся в файлах 27-26a.txt и 27-26b.txt.

(В. Ланская, Р. Ягафаров) В городе X тестируется проект по оптимизации размещения кранов на складах. Оптимальное местоположение для крана (или центроид) будет таким, при котором сумма расстояний Чебышева от этого места до всех других точек на складе была минимальной. Расстояние Чебышева между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется как максимум модулей разностей их координат: \(d(A, B) = max ( | x2 ‐ x1 |, | y2 ‐ y1 | ).\)

В файле A хранятся данные о двух складских комплексах (кластерах). Каждый комплекс имеет форму прямоугольника. Каждая строка файла содержит координаты одной точки на складе: сначала x, затем y. Количество точек в каждом комплексе не превышает 1000. В файле Б той же структуры хранятся данные о трёх кластерах, каждый из которых имеет вид прямоугольника размером H = 6 и W = 8. Количество точек в каждом комплексе не превышает 10 000.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px ‐ среднее арифметическое абсцисс центров кластеров, и Py ‐ среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 10 000, затем целую часть абсолютного значения произведения Py × 10 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Исходные данные находятся в файлах 27-25a.txt и 27-25b.txt.

(В. Ланская, Р. Ягафаров) Шёл 2077 год. Ученому необходимо провести кластеризацию населенных пунктов двух больших районов на картах планет Информатикус и Алгоритмикус. Район (кластер) -- это группа населенных пунктов, которые находятся внутри прямоугольника высотой H и шириной W. Каждый населенный пункт обязательно принадлежит только одному району. Столица района (или центроид) -- это такой населенный пункт, сумма манхэттенских расстояний от которого до всех других населённых пунктов в кластере минимальна. Манхэттенское расстояние между двумя точками A(x₁, y₁) и B(x₂, y₂) вычисляется как сумма модулей разностей их координат: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).

В файле A хранятся данные о населенных пунктах двух районов (кластеров) планеты Информатикус, где H = 3, W = 3 для каждого кластера. В каждой строке записаны координаты одного населенного пункта в условных единицах: сначала x, затем y. Известно, что количество звёзд не превышает 1000. В файле Б той же структуры хранятся данные о населенных пунктах трёх кластеров планеты Алгоритмикус, где H = 3, W = 3 для каждого кластера. Известно, что количество населенных пунктов не превышает 10 000.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px -- среднее арифметическое абсцисс центров кластеров, и Py -- среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 10 000, затем целую часть абсолютного значения произведения Py × 10 000 для файла А, во второй строке -- аналогичные данные для файла Б.

Исходные данные находятся в файлах 27-24a.txt и 27-24b.txt.

 

(В. Ланская, Р. Ягафаров) Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте звёздного неба. Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости, которое вычисляется по формуле:  \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).

В файле A хранятся координаты точек двух кластеров,. В каждой строке записана информация о расположении на карте одной точки: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000.
В файле Б хранятся данные о звёздах четырех кластеров. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична файлу А.
Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px – среднее арифметическое абсцисс центров кластеров, и Py – среднее арифметическое ординат центров кластеров.

В ответе запишите четыре числа:
в первой строке сначала целую часть произведения Px × 10 000, затем целую часть произведения Py × 10 000 для файла А, во второй строке – аналогичные данные для файла Б.
Значения в каждой строке разделяйте одним пробелом.

Исходные данные находятся в файлах 27-23a.txt и 27-23b.txt.

(В. Шубинкин) В ходе эксперимента были зафиксированы очаги радиации. Чтобы изучить данное явление, решили провести кластеризацию источников излучения. Кластер ‐ это набор источников (точек) на графике, лежащий внутри прямоугольника высотой H и шириной W. Каждая точка обязательно принадлежит только одному из кластеров. Истинный центр кластера, или центроид, ‐ это одна из точек на графике, сумма расстояний от которой до всех остальных звёзд кластера минимальна. Под расстоянием понимается расстояние Евклида между двумя точками A(x₁, y₁) и B(x₂, y₂) на плоскости, которое вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. Аномалии следует исключить при проведении расчётов.

В файле A хранятся данные о точках двух кластеров, где H=3, W=3 для каждого кластера. В каждой строке записаны координаты одной точки в условных единицах: сначала x, затем y. Известно, что количество точек не превышает 1000.

В файле Б той же структуры хранятся данные о точках трёх кластеров, где H=3, W=3 для каждого кластера; количество точек не превышает 10 000.

Для каждого файла определите координаты центра каждого кластера, затем вычислите два числа: Px ‐ среднее арифметическое абсцисс центров кластеров, и Py ‐ среднее арифметическое ординат центров кластеров. В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения Px × 100 000, затем целую часть абсолютного значения произведения Py × 100 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Возможные данные одного из файлов иллюстрированы графиком.

(В. Шубинкин) При проведении эксперимента заряженные частицы попадают на чувствительный экран размером 12 на 9 условных единиц. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания в условных единицах. При анализе результатов выделяют кластеры ‐ группы точек на экране, в которые попали частицы. Размер каждого кластера ‐ не более W условных единиц в ширину и не более H условных единиц в высоту. Каждая точка принадлежит только одному кластеру. Минимальное (максимальное) расстояние между кластерами ‐ это минимальное (максимальное) расстояние между двумя точками, одна из которых принадлежит одному кластеру, а вторая ‐ другому. Расстояние между двумя точками A(x₁,y₁) и B(x₂,y₂) вычисляется по формуле \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).

Аномалиями назовём точки, находящиеся на расстоянии более одной условной единицы от точек кластеров. Аномалии следует исключить при проведении расчётов.

В файле A хранятся данные о точках двух кластеров, где W=4, H=4 для каждого кластера. В каждой строке записана информация о расположении одной точки: сначала координата x, затем координата y. Значения даны в условных единицах. Известно, что общее количество точек не превышает 1000.

В файле Б, который имеет ту же структуру, что и файл А, хранятся данные о точках трёх кластеров, где W=3, H=3 для каждого кластера. Известно, что общее количество точек не превышает 10 000.

Для каждого файла определите минимальное d_min и максимальное d_max расстояния между двумя кластерами. В ответ запишите 4 числа: в первой строке целую часть абсолютного значения произведения d_min × 10 000, затем целую часть абсолютного значения произведения d_max × 10 000 для файла А, во второй строке ‐ аналогичные данные для файла Б.

Исходные данные находятся в файлах 27-21a.txt и 27-21b.txt.

(ЕГЭ-2025) На соревнованиях по спортивному ориентированию каждый участник должен пройти маршрут, посещая контрольные точки. Все контрольные точки пронумерованы натуральными числами, начиная с 1. В начале сезона соревнований каждому спортсмену присваивается уникальный номер -- натуральное число, не превышающее 1 000 000. Жюри фиксирует факт прохождения спортсменом контрольной точки. На разных этапах соревнований спортсмен может посетить одну и ту же контрольную точку в произвольном порядке несколько раз или не посетить совсем. Тренер в конце сезона анализирует результаты этапов соревнования, чтобы выявить контрольную точку, которую посетило наибольшее число спортсменов с идущими подряд номерами. Определите максимальное число спортсменов с идущими подряд номерами и номер найденной контрольной точки. Если таких групп спортсменов несколько, укажите наименьший номер посещённой группой контрольной точки.

Входные данные представлены в файле 26-174.txt следующим образом. Первая строка входного файла содержит число N (натуральное число, не превышающее 1 000 000) -- количество посещений спортсменами контрольных точек в течение всего сезона соревнований. Каждая из следующих N строк содержит два натуральных числа, не превышающих 1 000 000: номер спортсмена и номер посещённой им контрольной точки. Запишите в ответе два натуральных числа: максимальное число спортсменов с идущими подряд номерами, посетивших одну и ту же

точку, и номер этой точки.

Пример входного файла:

9
41 3
43 125
50 33
42 125
42 126
42 127
41 125
50 126
42 126

Для приведённого примера точку с номером 125 посетили три спортсмена с номерами 41, 42 и 43. Ответ: 3 125.

(ЕГЭ-2025) Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток). Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту, начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит. Определите, сколько граждан сможет попасть на приём в МФЦ в течение 24 часов, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.

Входные данные представлены в файле 26-173.txt следующим образом. Первая строка входного файла содержит натуральное число К, не превышающее 1000, -- количество окон в МФЦ. Во второй строке записано натуральное число N (N ≤ 10 000), обозначающее количество граждан. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанные в заявке время начала и время окончания приёма (в минутах от начала суток).

Запишите в ответе два числа: количество граждан, которые смогут воспользоваться услугами МФЦ, и номер окна, в котором специалист примет последнего гражданина.

Пример входного файла:

2
5
30 60
40 100
59 60
61 100
101 144

При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, равен 1, так как будут свободны окна 1 и 2.

(ЕГЭ-2025) На производстве штучных изделий N деталей должны быть отшлифованы и окрашены. Для каждой детали известно время её шлифовки и время окрашивания. Детали пронумерованы начиная с единицы. Параллельная обработка деталей не предусмотрена. На ленте транспортёра имеется N мест для каждой из N деталей. На ленте транспортёра детали располагают по следующему алгоритму:

-- все 2N чисел, обозначающих время окрашивания и шлифовки для N деталей, упорядочивают по возрастанию;

-- если минимальное число в этом упорядоченном списке -- это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место от её начала;

-- если минимальное число -- это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортёра

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

Этот алгоритм применяется последовательно для размещения всех N деталей. Определите номер последней детали, для которой будет определено её место на ленте транспортёра, и количество деталей, которые будут отшлифованы до неё.

Входные данные представлены в файле 26-172.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) -- количество деталей. Следующие N строк содержат пары чисел, обозначающих соответственно время шлифовки и время окрашивания конкретной детали (все числа натуральные, различные).

Запишите в ответе два натуральных числа: сначала номер последней детали, для которой будет определено её место на ленте транспортёра, затем количество деталей, которые будут отшлифованы до неё.

Пример входного файла:

5
30 50
100 155
150 170
10 160
120 55

При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте транспортёра деталь 3. При этом до неё будут отшлифованы три детали. Ответ: 3 3.

(А. Пасхин) В мастерской есть станок A и станок B. Для обработки детали требуется последовательно выполнить две операции: на станках A и В. Для каждой детали известны порядок операций и длительность каждой операции. В недельной технологической карте указаны время поступления детали в мастерскую на обработку в минутах от 00 ч. 00 мин. понедельника, длительность обработки на станке А и длительность обработки на станке B, а также какая операция выполняется первой. Гарантируется, что никакие две детали не поступают в мастерскую одновременно. Обработка новой детали на каждом станке может начинаться сразу по окончании обработки предыдущей детали. На перенос детали от станка A к станку B или, наоборот, от станка B к станку A дополнительное время не требуется (перенос уже учтён в длительности операций). Если станок свободен, то сразу начинается обработка очередной детали, если станок занят, то деталь попадает в соответствующую очередь. Если две детали поступают на станок одновременно, то первой в очередь попадает деталь, которая поступила в мастерскую раньше.

Входные данные представлены в файле 26-171.txt следующим образом. Первая строка входного файла содержит целое число N -- общее количество деталей. Каждая из следующих N строк содержит три числа и букву A или B. Первое число -- время поступления в мастерскую, второе число -- длительность обработки на станке А, третье число -- длительность обработки на станке B, буква показывает какая операция должна выполняться первой. В ответе запишите два целых числа: сначала количество деталей, которые попали на обработку на станке A после ожидания, затем время окончания обработки всех деталей на станке B (в минутах от 00 ч. 00 мин. понедельника).

Пример входного файла:

4
4 3 5 A
7 4 4 B
17 2 3 B
18 6 7 A

По этим данным детали будут обрабатываться в следующем порядке: деталь1, станок А, 4 -- 7 мин; деталь1 , станок B, 7 -- 12 мин.; деталь 2, станок B, 12 -- 16 мин (после ожидания); деталь 2, станок A, 16 -- 20 мин; деталь 3, станок B, 17 -- 20 мин; деталь 4, станок А, 20 -- 26 мин (после ожидания); деталь 3, станок A, 26 -- 28 мин (после ожидания); деталь 4, станок B, 26 -- 33 мин. Станок А ожидали две детали. Обработка на станке B завершена в 33 мин. Ответ: 2 33.

(ЕГКР-2025) В банке дистанционной проверяющей системы имеется более 100000 заданий. Все задачи пронумерованы, начиная с единицы. Эти задания в течение учебного периода решают участники различных курсом. Каждому студенту при регистрации присваивается уникальный идентификатор -- натуральное число, не превышающее 1000000. Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно из них.

Преподаватель сделал выгрузку результатов за некоторый период времени и выбрал студента, который решил наибольшее количество задач из банка через одну (одну решил, следующую -- нет).

Определите идентификационный номер студента, который решил наибольшее количество задач через одну, и количество решённых им задач. Если несколько студентов решили одинаковое максимальное количество задач, то укажите наименьший идентификационный номер.

Входные данные представлены в файле 26-170.txt следующим образом. В первой строке находится число N -- количество зачтённых решений за некоторый период времени (натуральное число, не превышающее 60000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100000: идентификатор студента и номер правильно решённой задачи.

Запишите в ответе два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество решённых задач через одну.

Пример входного файла:

9
40 3
60 33
60 33
50 124
50 126
50 128
40 4
50 72
50 126

Для приведённого примера студент с идентификационным номером 50 решил наибольшее количество задач через одну (3 задачи с номерами 124, 126 и 128). Ответ: 50 3.

*(автор неизвестен) На прямоугольном поле размером M × K клеток в некоторых клетках стоят домики. M -- это количество горизонтальных рядов, нумерация которых идет сверху вниз и начинается с 1, а K -- количество вертикальных рядов, нумерация столбцов происходит слева направо и также начинается с 1. Нужно на одном из домиков разместить камеру так, чтобы она просматривала наибольшее количество полей (не считая поле, на котором стоит домик). Просматриваемыми полями считаются те, которые идут от домика с камерой до ближайшего домика или края поля. Камера просматривает поля в четырех направлениях: север, юг, восток и запад. Если таких домиков на поле несколько, то нужно выбрать тот, который располагается в самом правом столбце, если и таких домиков несколько, то выбираем тот, который находится в самой верхней строке. В качестве ответа нужно указать два числа: номер горизонтального ряда домика, где нужно установить камеру, и количество просматриваемых полей.

Входные данные. В первой строке входного файла 26-169.txt записаны три натуральных числа, не превышающие 100 000: N -- количество домиков, M -- количество горизонтальных рядом и K -- количество вертикальных рядов. В каждой из следующих N строк находятся по два натуральных числа: номера горизонтального и вертикального рядов, на пересечении которых находится домик. Первое из этих чисел не превышает M, второе не превышает K. Запишите в ответе два числа: номер горизонтального ряда домика, где нужно поставить камеру, и количество просматриваемых клеток.

Пример входного файла:

8 6 7
1 5
2 2
2 4
3 3
4 4
5 7
6 1
6 4

При таких исходных данных максимальное количество клеток, которые будет просматривать камера, равно 11. Так будет при расположении домика в клетках с координатами (1, 5), (3, 3) или (5, 7). Выбрать нужно клетку с наибольшим номером столбца -- это клетка (5,7). Ответ: 5 11.

*(Л. Шастин) Группа авантюристов хочет добраться до максимально возможно отдаленной от экватора зоны Земли, для чего им предстоит пересечь множество других зон в качестве перевалочных пунктов. При посещении очередной зоны авантюристы затрачивают некоторую сумму денежных единиц на организацию перевала, эта сумма может варьироваться в зависимости от отправной и конечной зоны. Группа начинает свой путь в зоне № 1, а изначальные затраты средств равны нулю. Известно, что чем больше номер зоны, тем дальше она расположена от экватора. Имеется N записей, каждая из которых содержит информацию о какой-то зоне: номер текущей зоны, номер переходной зоны, до которой можно добраться отсюда и сумма средств для посещения переходной зоны. Каждая зона может быть представлена в нескольких вариантах с разными переходными пунктами и ценами за переход. Из каждой зоны можно попасть только в зону с бóльшим номером. Некоторые записи также могут содержать информацию о недостижимых зонах (в которые невозможно попасть, начав движение из зоны № 1). Определите номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет K денежных единиц, а также максимальный возможный остаток средств при этих условиях.

Входные данные. В первой строке входного файла 26-168.txt записаны два натуральных числа: N (N ≤ 100 000) -- количество записей о зонах и K (K ≤ 1 000 000) -- бюджет, которым располагает группа. В каждой из следующих N строк находятся по три числа: номер текущей зоны, номер переходной зоны (в которую можно передвинуться из текущей) и сумма средств, необходимая для перехода. Все числа натуральные и не превосходят 1 000 000.

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

Пример входного файла:

8 100
1 4 20
2 4 30
1 3 10
3 4 5
4 5 5
1 2 10
3 5 20
2 5 50

При таких исходных данных можно достигнуть максимум зоны №5 несколькими способами. Оптимальным вариантом движения будет переход из зоны 1 в зону 3 за 10 единиц, затем из зоны 3 в зону 4 за 5 единиц и в конце из зоны 4 в зону 5 за 5 единиц. Остаток бюджета при этом составит 100 -- 20 = 80 единиц. Ответ: 5 80.

**Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. Каждому файлу присвоен ранг важности -- целое число, которое показывает, насколько важную информацию содержит файл. По заданной информации об объёме файлов пользователей, их рангах важности и свободном объёме на архивном диске определите, какие файлы сохранить на диске, чтобы их суммарный ранг важности был максимальным. Если для приведённых данных есть несколько решений задачи, следует выбрать вариант, при котором остается меньше свободного места на архивном диске. Если и таких вариантов несколько, выбирается вариант, где самый большой файл имеет наибольший размер.

Входные данные. В первой строке входного файла 26-167.txt находятся два числа: S -- размер свободного места на диске (натуральное число, не превышающее 1 000 000) и N -- количество пользователей (натуральное число, не превышающее 10000). В каждой из следующих N строк находятся два числа: объём файла (натуральное число, не превышающее 5000) и его ранг важности (натуральное число, не превышающее 10). Запишите в ответе два числа: сначала максимальный суммарный ранг важности файлов, помещённых в архив, затем размер наибольшего файла, который был сохранён на диске.

Пример входного файла:

100 4
80 3
30 6
50 5
40 5

При таких исходных данных наибольший суммарный ранг важности (11) достигается при размещении на архивном диске пары файлов с объемами 30 и 50 или 30 и 40. Во втором случае на диске остается больше места, чем в первом, поэтому выбираем первый вариант. Ответ: 11 50.

**В магазине для упаковки подарков есть N кубических коробок разной стоимости. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на K единиц меньше длины стороны другой коробки. Определите наименьшую стоимость упаковки, при которой количество вложенных друг в друга коробок не меньше Q, и длину стороны самой маленькой коробки, где при этом будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку. Если есть несколько подходящих вариантов упаковки с одинаковой стоимостью, выберите вариант с наименьшей внутренней (самой маленькой) коробкой.

Входные данные представлены в файле 26-165.txt следующим образом. В первой строке входного файла находится число N -- количество коробок в магазине (натуральное число, не превышающее 10 000), число K -- минимально допустимая разница длин сторон соседних коробок в матрёшке, и число Q -- минимально допустимое количество вложенных коробок. В каждой из следующих N строк записаны длина стороны коробки и стоимость коробки (натуральные числа, не превышающие 10 000).

Запишите в ответе два целых числа: наименьшую стоимость упаковки, при которой количество вложенных друг в друга коробок не меньше Q, и длину стороны самой маленькой коробки, где при этом будет находиться подарок.

Пример входного файла:

5 7 2
50 1
45 1
30 5
20 5
10 5

При таких исходных данных минимальную сумму (6) при упаковке минимум в две коробки можно получить при использовании пары коробок с длинами сторон 50 и 30, 50 и 20, 50 и 10, 45 и 30, 45 и 20, 45 и 10. Из них наименьшая последняя коробка имеет сторону 10. Ответ: 6 10.

**В магазине для упаковки подарков есть N кубических коробок разной стоимости. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на K единиц меньше длины стороны другой коробки. Определите наименьшую стоимость упаковки, при которой количество вложенных друг в друга коробок не меньше Q, и длину стороны самой маленькой коробки, где при этом будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку. Если есть несколько подходящих вариантов упаковки с одинаковой стоимостью, выберите вариант с наибольшей внутренней (самой маленькой) коробкой.

Входные данные представлены в файле 26-165.txt следующим образом. В первой строке входного файла находится число N -- количество коробок в магазине (натуральное число, не превышающее 10 000), число K -- минимально допустимая разница длин сторон соседних коробок в матрёшке, и число Q -- минимально допустимое количество вложенных коробок. В каждой из следующих N строк записаны длина стороны коробки и стоимость коробки (натуральные числа, не превышающие 10 000).

Запишите в ответе два целых числа: наименьшую стоимость упаковки, при которой количество вложенных друг в друга коробок не меньше Q, и длину стороны самой маленькой коробки, где при этом будет находиться подарок.

Пример входного файла:

5 7 2
50 1
45 1
30 5
20 5
10 5

При таких исходных данных минимальную сумму (6) при упаковке минимум в две коробки можно получить при использовании пары коробок с длинами сторон 50 и 30, 50 и 20, 50 и 10, 45 и 30, 45 и 20, 45 и 10. Из них наибольшая последняя коробка имеет сторону 30. Ответ: 6 30.

**В магазине для упаковки подарков есть N кубических коробок разной стоимости. Самой интересной считается упаковка подарка по принципу матрёшки: подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на K единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, так чтобы стоимость упаковки не превысила M единиц, и минимальную итоговую стоимость этой упаковки. Размер подарка позволяет поместить его в самую маленькую коробку. Если есть несколько вариантов упаковки с одинаковым наибольшим количеством коробок, выберите вариант с наименьшей стоимостью.

Входные данные представлены в файле 26-164.txt следующим образом. В первой строке входного файла находится число N -- количество коробок в магазине (натуральное число, не превышающее 10 000), число K -- минимально допустимая разница длин сторон соседних коробок в матрёшке, и число M -- максимально допустимая стоимость упаковки. В каждой из следующих N строк записаны длина стороны коробки и стоимость коробки (натуральные числа, не превышающие 10 000).

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

Пример входного файла:

5 3 10
50 5
40 6
30 5
20 3
10 15

При таких исходных данных максимальное количество коробок (2) при минимальной стоимости (8) получается при использовании коробок со сторонами 50 и 20. Ответ: 2 8.