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

На складе требуется разместить N контейнеров различного размера, каждый из которых имеет форму куба. Контейнеры имеют разные цвета, которые обозначаются кодами -- латинскими буквами. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если а) размер стороны внешнего контейнера превышает размер стороны внутреннего на K и более условных единиц и б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. В блок можно объединять до M контейнеров включительно. Каждый блок, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Блоки собирают по одному, начиная с самого большого контейнера. В него добавляют самый большой из оставшихся, подходящий по размеру и имеющий минимальный подходящий код цвета.

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

Входные данные представлены в файле 26-103.txt следующим образом. В первой строке входного файла записано число N (1 ≤ N ≤ 20000) -- количество контейнеров, число K (1 ≤ K ≤ 1000) -- наименьшая допустимая разница размеров вложенных соседних контейнеров и число M (1 ≤ M ≤ N) -- наибольшее допустимое количество контейнеров в блоке. Каждая из следующих N строк содержит натуральное число, не превышающее 10000 -- длину стороны очередного контейнера, и латинскую букву, обозначающую цвет этого контейнера.

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

7 5 3
2 A
18 B
47 A
16 B
38 A
55 A
48 B

Для такого набора контейнеров можно составить три блока, удовлетворяющих условию: (55, 48, 38), (47, 18, 2) и (16). Количество блоков с максимальным количеством контейнеров -- 2. Ответ: 3 2.

На складе требуется разместить N контейнеров различного размера, каждый из которых имеет форму куба. Контейнеры имеют разные цвета, которые обозначаются латинскими буквами. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если а) размер стороны внешнего контейнера превышает размер стороны внутреннего на K и более условных единиц и б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Блоки составляют следующим образом. Сначала выбирают наибольший контейнер. Затем вкладывают в него наибольший подходящий контейнер. Если таких контейнеров несколько, выбирают контейнер с наименьшим кодом цвета. Этот алгоритм повторяется, пока есть подходящие контейнеры. Затем так же составляется следующий блок и т. д.

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

Входные данные представлены в файле 26-102.txt следующим образом. В первой строке входного файла записано число N -- количество контейнеров (натуральное число, не превышающее 20 000) и число K (1 ≤ K ≤ 1000) -- наименьшая допустимая разница размеров вложенных соседних контейнеров. Каждая из следующих N строк содержит натуральное число, не превышающее 10000 -- длину стороны очередного контейнера, и латинскую букву, обозначающую цвет этого контейнера.

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

7 5
2 A
18 B
47 A
16 B
38 A
55 A
48 B

Для такого набора контейнеров можно составить два блока, удовлетворяющих условию: (55, 48, 38, 18, 2), (47, 16). Наибольшее количество контейнеров -- в первом блоке -- 5. Ответ: 2 5.

На складе требуется разместить N контейнеров различного размера, каждый из которых имеет форму куба. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на K и более условных единиц. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.

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

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

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

7 9
2
18
47
16
38
55
48

Для такого набора контейнеров можно составить три блока, удовлетворяющих условию: (55, 38, 18, 2), (48, 16) и (47). Наибольшее количество контейнеров -- в первом блоке -- 4. Ответ: 3 4.

(А. Рогов) Строительная организация возводит два высотных здания, находящихся на расстоянии M друг от друга. Из-за коммунальной аварии потребовалось срочно протянуть трубу от одного здания к другому. В распоряжении организации имеется N труб единичной длины. Известен диаметр каждой трубы. Трубы можно скреплять между собой только при условии, что их диаметр отличается не более чем на 11 единиц.

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

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

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

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

7 3
2
6
7
8
8
10
15

Для приведённого примера, при условии, что трубы могут отличаться не более чем на 3 единицы, можно составить трассы из труб с диаметрами 6 + 7 + 8, 6 + 8 + 8, 7 + 8 + 8, 8 + 8 + 10, максимальная пропускная способность возможна при варианте 8 + 8 + 10. Ответ: 8 10.

(А. Богданов) Транспортная компания владеет автомобилями с грузоподъемность M. Для транспортировки N грузов автомобили загружают предметами по убыванию веса, пока общая масса предметов не превышает грузоподъемность M. И далее процедуру повторяют для другого грузовика, до тех пор, пока все предметы не будут погружены. Нужно определить количество автомобилей для транспортировки всех предметов и общую загрузку предпоследнего автомобиля.

Входные данные представлены в файле 26-99.txt следующим образом. В первой строке записаны два числа -- количество грузов N и грузоподъёмность автомобиля M. В каждой из следующих N строк записано по одному натуральному числу, обозначающему вес груза.

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

6 100
30
10
40
50
10
20

В первый автомобиль будут погружены грузы весом 50, 40 и 10, во второй -- грузы весом 30, 20 и 10. Ответ: 2 100.

(А. Игнатюк) В текстовом файле представлен отчёт магазина о товарах и акциях за последний месяц. Всего имеется две категории товаров: А (низкая ценовая категория) и В (высокая ценовая категория). Символ С, указанный после категории товара, обозначает, что на товар действует скидка, равная 10% для товаров категории А и 20% для товаров категории B. Определите минимальную стоимость максимального количества товаров, которые можно купить с учетом имеющейся суммы, и цену самого дорогого приобретённого со скидкой товара, который можно приобрести при покупке максимального количества товаров.

При записи денежных сумм используете правила математического округления.

Входные данные представлены в файле 26-98.txt следующим образом. В первой строке даны два числа -- количество товаров N и сумма денег S. В каждой из следующих N строк через пробел указано два значения: цена товара без скидки и категория товара (возможно, с символом С).

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

8 820
200 A
300 BC
150 B
270 A
350 B
240 AC
200 BC
300 AC

Второй и три последних товара подешевеют на 20, 10, 20 и 10 процентов соответственно, их новые цены 240; 216; 160; 270. По условию задачи 1 покупается 4 товара с ценами 150, 160, 200, 216, при этом наибольшая возможная цена товара, приобретенного со скидкой, будет 270. Ответом для примера будет: 726 270.

(Е. Джобс) При перевозке труб для более компактной укладки решено перевозить трубы меньшего диаметра внутри труб большего диаметра. Для каждой трубы известен внешний диаметр D и толщина стенки S (в миллиметрах). Для предотвращения дефекта между трубами оставляют зазор в 3 миллиметра.

Несколько труб, вложенных одна в другую, называют пакетом. Определите максимальное количество труб, которые можно объединить в одном пакете, а также максимальный диаметр самой маленькой трубы в этом пакете.

Входные данные представлены в файле 26-97.txt следующим образом. В первой строке приведено число N -- количество труб. В каждой из следующих N строк приведены пары положительных целых чисел: внешний диаметр трубы D и толщина её стенки S.

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

5
100 5
80 3
74 4
62 5
60 3

При таких исходных данных можно собрать пакет из трёх труб: (100, 5), (80, 3), (62, 5). Ответ: 3 62.

(Е. Джобс) Спутник принимает сигналы от разных станций на земле. Каждый сигнал имеет координату источника -- широту и долготу с точностью до десятых, выраженных целочисленными значениями -- удесятеренными координатами. Например, координаты (55,7°; 37,6°) записываются как пара чисел 557 376.

Найдите значение долготы, с которой отправлено максимальное количество сигналов, а также количество различных градусов широты (от -90° до 90°, с отбрасыванием дробной части), с которых пришли сигналы для найденной долготы. Если из нескольких долгот пришло одинаковое число сигналов, следует выбрать долготу с наибольшим значением.

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

Запишите в ответе два целых числа: значение долготы и количество целых градусов широты для нее.

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

7
-123 407
-125 52
-128 52
802 407
809 52
805 407
850 53

Для приведённого примера видим две долготы с тремя сигналами: 5,2° и 40,7°. Cчитаем количество целых значений широт для наибольшей долготы 40,7° (--12,3°; 80,2°; 80,5°). Следовательно, принято три сигнала с двух различных широт: --12° и 80°. Ответ: 407 2.

(М. Ишимов) Управляющей компании поступили жалобы об отсутствии капитального ремонта. В каждой жалобе указан номер дома и номер подъезда, где необходим ремонт. Компания решила в первую очередь сделать ремонт в тех домах, в которых есть подъезд без жалоб (чтобы расположить в нём строительные материалы) и не менее чем в 3 соседних подъездах жалобы присутствуют.

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

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

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

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

8
1 5
1 6
1 7
1 9
2 1
2 12
1 10
2 24

При таких исходных данных есть два подходящих подъезда в 1-ом доме: № 4 (3 соседних подъезда с жалобами: 5, 6 и 7) и № 8 (4 соседних подъезда с жалобами: 6, 7, 9 и 10). Ответ: 1 4.

(М. Ишимов) Семья М. собирается купить билеты на самолет, чтобы полететь на отдых. Они выбрали рейс с двухэтажным самолётом. В семье, помимо папы и мамы, имеется двое детей, и билеты нужно купить так, чтобы вся семья летела в одном ряду на соседних местах. Дети хотят смотреть в окно, поэтому нужно одно место у окна. Места у окон считаются самые крайние места в каждом ряду (первое и последнее).

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

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

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

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

5 6
1 50 2
2 23 1
1 50 3
2 30 4
1 1 6

При таких исходных данных есть два подходящих ряда: 1-й ряд на 1-м этаже и 23-й ряд на 2-м этаже. Ответ: 23 2.

(М. Ишимов) В городе открылся новый торговый центр. Каждое помещение для торговой точки имеет «адрес», состоящий из номера этажа и номера места на этом этаже. Предприниматель собирается приобрести одно из помещений для открытия магазина. Чтобы привлечь как можно больше посетителей в свой магазин, ему нужно такое место, чтобы не менее M соседних помещений были уже куплены.

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

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

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

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

7 3
1 2
1 3
1 4
1 6
2 1
2 12
2 24

При таких исходных данных есть два подходящих места на 1-м этаже: № 1 (3 соседних места куплены: 2, 3 и 4) и № 5 (также 3 соседних места куплены: 3, 4 и 6). Ответ: 2 1.

(А. Богданов) При проведении эксперимента заряженные частицы попадают на чувствительный

экран, представляющий из себя матрицу пикселей размером 10000 на 10000 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 10000) и номер позиции в строке (целое число от 1 до 10000) и её заряд (+/-). Положительно заряженная частица включает пиксель, а отрицательно заряженная выключает. Положительная частица не влияет на включенный пиксель, как и отрицательно заряженная на выключенный. Определите на момент завершения эксперимента номер строки, в которой находится наибольшая непрерывная цепочка включенных пикселей.

Входные данные представлены в файле 26-92.txt следующим образом. В первой строке записано количество строк с данными N (1 ≤ N ≤ 1000000). В каждой из следующих N строк записаны два натуральных числа, не превышающих 10000 -- координаты сработавшего чувствительного элемента (сначала строка, затем позиция пикселя в этой строке), а затем -- знак «+» или «--», отделенный от чисел пробелом.

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

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

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

При таких исходных данных задачи на момент завершения эксперимента в строке 1 включен только пиксель в позиции 2, а в строке 2 -- три пикселя подряд в позициях 4, 5 и 6. Ответ: 3 2.

(М. Шагитов) На склад торговой базы поступают товары в ящиках, которые имеют стандартный размер и разный вес. Ящики размещаются в контейнерах, каждый из которых вмещает два пакета с суммарным весом не более D кг. Если при этом какие-то пакеты не удалось упаковать в контейнеры парами (из-за слишком большого веса), они размещаются по одному. Гарантируется, что вес каждого ящика не превышает D. Определите наибольшее количество контейнеров, в которые можно поместить по 2 ящика, и минимально возможный суммарный вес ящиков, которые размещаются по одному в контейнере.

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

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

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

10 130
60
52
63
55
59
83
54
81
57
61

При таких исходных данных задачи в 4-х контейнерах будут пары товаров {63, 61}, {60, 59}, {55, 57} и {54, 52}, а товары {81} и {83} (общим весом 164 кг) помещаются в отдельных контейнерах. Ответ: 4 164.

(ЕГЭ-2022) В супермаркете проводится акция «каждым четвёртый товар в чеке за полцены». Покупатель расположил товары на ленте так, чтобы заплатить за покупку одним чеком как можно меньше с учётом проходящей акции. Однако выяснилось, что программа для кассового аппарата не учитывает расположение товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки в рублях была максимально возможной.

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

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

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

4
80
30
50
40

При таких исходных данных если «каждый третий товар за полцены», предполагаемая и действительная суммы равны 0,5·80 + 30 + 50 + 40 = 160 и 80 + 0,5·30 + 50 + 40 = 185. Ответ: 160 185.

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

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

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

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

5
43
40
32
40
30

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно. В обоих случаях количество коробок равно 3, а максимальная длина стороны самой маленькой коробки равна 32. Ответ: 3 32.

(E. Джобс) В терминологии сетей TCP/IP IP-адресом называют 32-битную последовательность, позволяющую однозначно определить подключенное к сети устройство, маской сети называют 32-битное двоичное число, которое показывает, какая часть IP-адреса относится к адресу сети, а какая -- к адресу узла в этой сети. Адрес сети получается в результате применения поразрядной конъюнкции к заданному адресу узла и его маске. Например, при IP-адресе 174.23.88.201 и маске 255.255.192.0 адрес сети будет равен 174.23.64.0, адрес узла в этой сети -- 6345.

Журнал обращений к серверу содержит IP-адреса, с которых были получены запросы. Известно, что маска у всех сетей равна 255.255.224.0. Определите адрес сети, из которой пришло наибольшее количество запросов. Для этой сети определите количество узлов, отправлявших запросы.

Входные данные представлены в файле 26-88.txt следующим образом. В первой строке входного файла записано натуральное число N -- общее количество обращений к серверу (1 ≤ N ≤ 100 000). В каждой из следующих N строк находится IP-адрес -- четыре числа в диапазоне \[0; 255\], разделенные точками.

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

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

3
125.10.13.14
125.10.13.20
125.10.45.14

В данном случае первые два запроса пришли из сети 125.10.0.0, а один последний -- из сети 125.10.32.0. Ответ: 1251000 2.

(М. Шагитов) Для экрана размером 10000х10000 пикселей используется цветовая модель RGB. Графический адаптер считывает пиксели экрана и записывает в файл данные всех пикселей, кроме тех, для которых установлен белый цвет. Для каждого пикселя записывается номер строки, номер позиции в строке и цвет в виде шестнадцатеричного кода (например, #FFFFFF -- белый цвет). Найдите все пиксели с кодом #00FF00, слева и справа от которых записаны по три подряд идущих пикселя с кодом #0000FF. Определите общее количество подходящих пикселей, а также номер строки, в которой есть наибольшее количество таких пикселей. Гарантируется, что на экране есть хотя бы один подходящий пиксель.

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

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

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

11
1 1 #00FF00
1 3 #00FF00
2 1 #0000FF
2 2 #0000FF
2 3 #0000FF
2 4 #00FF00
2 5 #0000FF
2 6 #0000FF
2 7 #0000FF
3 3 #00FF00
3 5 #00FF00

В данном случае есть один подходящий пиксель (строка 2, позиция 4) с кодом цвета #00FF00, окруженный с двух сторон тройками пикселей с кодом #0000FF. Ответ: 1 2.

(Л. Шастин) Меню бургерной включает 1000 различных блюд, которым присвоены коды от 0 до 999. В отчёте фиксируют время начала и окончания приготовления каждого заказа. Если запись о заказе некоторого блюда встретилась первый раз -- это время начала приготовления; если второй раз, значит, он уже приготовлен (может случиться так, что некоторые заказы по каким-то причинам не были приготовлены). Готовить несколько блюд с одним номером одновременно нельзя.

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

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

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

8
60 5
40 1
90 5
45 5
20 2
55 1
10 2
50 5

Наибольшее количество заказов -- три -- было приготовлено за час времени от 10 до 70 (70 -- 10 = 60), это есть часовой максимум. Блюдо с кодом 1 в среднем готовилась 55 -- 40 = 15 минут, блюдо 2 готовилась 20 -- 10 = 10 минут, а блюдо 5 -- (30 + 5)/2 = 17,5 минут.

Ответ: 3 5.

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

Входные данные представлены в файле 26-85.txt следующим образом. В первой строке входного файла записано натуральное число N -- общее количество занятых мест (1 ≤ N ≤ 600 000). В каждой из следующих N строках находятся по целых числа, не превышающих 25 000. Первые два числа -- это номер ряда и место в ряду, занятое участником конференции (натуральные числа). Если третье число равно 0, то место занято участником из города Н, а если оно равно 1, то участником из другого города.

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

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

15
1 1 0
1 3 1
1 5 0
1 7 1
1 8 0
2 3 1
2 8 1
2 9 0
2 10 0
3 1 0
3 2 1
3 6 1
3 7 0
3 8 0
3 9 0

В примере требуется найти ряд, в котором есть ровно три свободных места между участниками из других городов, а также хотя бы четыре занятых места, занятые участниками из города Н.

В 3-м ряду есть 3 свободных места подряд между участниками из других городов (выделены жёлтым) и 4 места заняты участниками из города Н. В этом ряду 2 места заняты участниками из других городов (выделены зеленым). Ответ: 3 2.

(99 баллов) В университете Инфаполис учится N групп студентов, для обучения которых используется N аудиторий. Известно количество студентов в каждой группе и количество мест в каждой аудитории. Группа всегда занимает целую аудиторию (группы не объединяются). Администрацию университета заинтересовал вопрос: сколько существует способов рассадить все группы по аудиториям, и сколько групп (по одной) вмещаются в самую маленькую аудиторию.

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

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

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

3
2 3 4
5 6 3

При таких исходных данных всего есть 4 варианта размещения (A5: 2 означает, что в аудитории вместимостью 5 человек размещается группа из 2-х человек):

1) A5: 2, A6: 4, A3: 3,

2) A5: 4, A6: 2, A3: 3,

3) A5: 4, A6: 3, A3: 2,

4) A5: 3, A6: 4, A3: 2.

В самой маленькой аудитории (на 5 человек) можно разместить одну из двух 2 групп (из 2-х или 3-х человек). Ответ: 4 2.