Информатика

(М. Крючков) В лесу выделено несколько мест (кластеров), где растёт много деревьев, предназначенных для вырубки После спиливания дерева его нужно доставить в точку сбора, которая совпадает с одним из деревьев кластера. Стоимость доставки определяется как расстояние от дерева до точки сбора, умноженное на высоту дерева. Под расстоянием понимается расстояние Евклида между двумя точками 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.

(В. Ланская, Р. Ягафаров) Шёл 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(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 для файла А, во второй строке ‐ аналогичные данные для файла Б.

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

(ЕГЭ-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.

*Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток), а также сумма, которую компания-организатор готова заплатить за аренду зала. Два мероприятия можно провести, если время окончания одного из них строго меньше времени начала другого. Определите максимальное время, в течение которого конференц-зал может быть занят, и общую сумму, которую в этом случае удастся получить за аренду. Гарантируется, что последовательность мероприятий, обеспечивающая максимальное время занятости, единственна.

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

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

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

5
10 90 1
100 130 2
120 135 5
130 170 3
140 180 4

Для приведённого примера наибольшее время 153 = (90-10+1) + (130-100+1) + (180-140+1) конференц-зал будет занят при проведении первого и второго по счёту мероприятий в списке. Общая выручка за аренду составит 1 + 2 + 4 = 7. Ответ: 153 7.

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

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

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

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

8 7
50 R
48 G
43 B
40 R
36 B
34 G
22 B
17 R

Пример входного файла приведён для случая трёх коробок красного цвета, двух коробок зелёного цвета и трёх коробок синего цвета. При таких исходных данных условию задачи удовлетворяет набор коробок 50, 43, 34, 22, то есть количество коробок равно 4, а длина стороны самой маленькой коробки 22. Ответ: 4 22.

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

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

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

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

5
129
120
96
120
90

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 90, 120 и 129 или 96, 120 и 129 соответственно. В обоих случаях количество коробок равно 3, а максимальная длина стороны самой маленькой коробки равна 96. Ответ: 3 96.

Входной файл содержит сведения о заявках на проведение занятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток), а также сумма, которую компания-организатор готова заплатить за аренду зала. Два мероприятия можно провести, если время окончания одного из них строго меньше времени начала другого. Определите максимальную выручку, которую можно получить за аренду в течение суток, а также общую длительность мероприятий, которые будут проведены в этом случае. Гарантируется, что последовательность мероприятий, обеспечивающая максимальную выручку, единственна.

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

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

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

5
10 90 1
100 130 2
120 135 5
130 170 3
140 180 4

Для приведённого примера наибольшая выручка (10) может быть получена при проведении первого, третьего и последнего мероприятий в списке. Общая длительность этих мероприятий равна (90-10+1) + (135-120+1) + (180-140+1) = 138. Ответ: 10 138.

Участники викторины отвечают на 10 вопросов, сложность которых оценивается числом от 10 до 100. При удачном ответе на вопрос стоимостью Q участник получает Q баллов, при неправильном ответе на такой вопрос он получает Q штрафных баллов, которые вычитаются из результата. Участник может не отвечать на какие-то вопросы, при этом его сумма баллов не изменяется. Чтобы определить победителей, для каждого участника вычисляются три показателя:

1)    сумма – сумма набранных баллов;
2)    штрафы – сумма штрафных баллов за неправильные ответы;
3)    пропуски – количество вопросов, на которые участник вообще не отвечал.

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

Входные данные представлены в файле 26-156.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 --- количество участников викторины. Вторая строка содержит 10 чисел, разделённых пробелом: «стоимости вопросов». В каждой из следующих N строках через пробел записаны через пробел 11 чисел: сначала код участника, а затем 10 чисел, характеризующих ответы этого участника на вопросы (1, если ответ верный; -1, если ответ неверный и 0, если участник не отвечал на вопрос).

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

Участники викторины отвечают на 10 вопросов, сложность которых оценивается числом от 10 до 100. При удачном ответе на вопрос стоимостью Q участник получает Q баллов, при неправильном ответе на такой вопрос он получает Q штрафных баллов, которые вычитаются из результата. Участник может не отвечать на какие-то вопросы, при этом его сумма баллов не изменяется. Чтобы определить победителей, для каждого участника вычисляются три показателя:
1)    сумма – сумма набранных баллов;
2)    штрафы – сумма штрафных баллов за неправильные ответы;
3)    пропуски – количество вопросов, на которые участник вообще не отвечал.

В таблице результатов участники располагаются по убыванию суммы, при равенстве сумм -- по возрастанию штрафов, при равенстве сумм и штрафов -- по возрастанию пропусков. При равенстве всех трёх показателей участники располагаются в итоговой таблице в порядке возрастания их личных номеров. Победителями считаются участники, занявшие места в первой трети

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

Входные данные представлены в файле 26-156.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 --- количество участников викторины. Вторая строка содержит 10 чисел, разделённых пробелом: «стоимости вопросов». В каждой из следующих N строках через пробел записаны через пробел 11 чисел: сначала код участника, а затем 10 чисел, характеризующих ответы этого участника на вопросы (1, если ответ верный; -1, если ответ неверный и 0, если участник не отвечал на вопрос).

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

Участники викторины отвечают на 10 вопросов, сложность которых оценивается числом от 10 до 100. При удачном ответе на вопрос стоимостью Q участник получает Q баллов, при неправильном ответе на такой вопрос он получает Q штрафных баллов, которые вычитаются из результата. Участник может не отвечать на какие-то вопросы, при этом его сумма баллов не изменяется. Чтобы определить победителей, для каждого участника вычисляются три показателя:

1)    сумма – сумма набранных баллов;
2)    штрафы – сумма штрафных баллов за неправильные ответы;
3)    пропуски – количество вопросов, на которые участник вообще не отвечал.

В таблице результатов участники располагаются по убыванию суммы, при равенстве сумм -- по возрастанию штрафов, при равенстве сумм и штрафов -- по возрастанию пропусков. При равенстве всех трёх показателей участники располагаются в итоговой таблице в порядке возрастания их личных номеров. Победителями считаются участники, занявшие места в первой четверти

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

Входные данные представлены в файле 26-156.txt следующим образом. В первой строке входного файла записано натуральное число N, не превышающее 10 000 --- количество участников викторины. Вторая строка содержит 10 чисел, разделённых пробелом: «стоимости вопросов». В каждой из следующих N строках через пробел записаны через пробел 11 чисел: сначала код участника, а затем 10 чисел, характеризующих ответы этого участника на вопросы (1, если ответ верный; -1, если ответ неверный и 0, если участник не отвечал на вопрос).

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