Информатика

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

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

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

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

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

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

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

При таких исходных данных в строке 2 имеются две точки в чётных позициях (3 и 5). Ответ: 2 2.

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

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

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

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

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

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

При таких исходных данных в строке 1 имеются две точки в чётных позициях (2 и 4). Ответ: 2 1.

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

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

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

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

7
1 3
1 5
1 8
2 2
2 5
3 1
3 9

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

(Досрочный ЕГЭ-2022) В лесополосе осуществляется посадка деревьев: саженцы высаживают рядами на одинаковом расстоянии. Спустя некоторое время с помощью аэросъемки выясняют, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд ровно K неприжившихся саженцев при условии, что справа и слева от них саженцы прижились. В ответе запишите сначала наибольший номер ряда, затем наименьший номер неприжившегося саженца.

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

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

6 3
40 30
40 34
50 125
50 129
50 64
50 68

В примере требуется найти 3 подряд идущих неприжившихся саженца. Ответ: 50 65.

([PRO100 ЕГЭ](https://stepik.org/users/388343822)) Для проведения ЕГЭ требуются наблюдатели. На сайте профи.ру есть список наблюдателей и время, в которое они могут работать. Требуется нанять как можно меньше наблюдателей, чтобы в каждый момент экзамена за учениками присматривал хотя бы один наблюдатель, при этом смена первого наблюдателя произошла как можно позже, с момента старта ЕГЭ.

Входные данные представлены в файле 26-78.txt следующим образом. В первой строке содержится количество наблюдателей N, время начала ЕГЭ -- start и время окончания -- end, то есть время проведения ЕГЭ -- это полуинтервал [start, end). В следующих N строках содержится по два числа a, b, где a -- время начала, b -- время окончания работы наблюдателя, то есть наблюдатель работает в течение полуинтервала [a, b).

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

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

5 2 10
1 4
1 3
3 8
7 10
10 11

Наблюдение полностью обеспечивают наблюдатели, работающие в полуинтервалы [1, 4), [3, 8),  [7, 10). Время работы первого наблюдателя с начала экзамена 4 - 2 = 2. Ответ: 3 2.

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

Входные данные представлены в файле 26-77.txt следующим образом. В первой строке входного файла записано число N -- количество наклеек, которые собрал Иван (натуральное число, не превышающее 10 000). В следующих N строках записано по два числа: сначала номер страницы в альбоме (натуральное число от 1 до 30), затем номер наклейки на странице (натуральное число от 1 до 8). Запишите в ответе два числа: количество наклеек, которых не хватает Ивану для заполнения альбома, и номер страницы, на которой отсутствует наибольшее количество наклеек. Если таких страниц несколько выберите последнюю из них.

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

10
1 1
1 2
1 3
1 4
1 6
1 6
1 8
2 4
3 1
3 3

При таких входных данных будем считать, что Ивана интересуют только страницы с 1 по 3.

На первой странице ему не хватает 2 наклеек; на второй странице не хватает 7 наклеек; на 3 странице не хватает 6 наклеек (всего 15 наклеек, больше всех не хватает на странице 2). Ответ: 15 2.

(А. Кабанов) На производстве станок с ЧПУ обрабатывал некоторый набор деталей. В каждый момент времени станок может обрабатывать только одну деталь. Каждая деталь изготавливалась в определённый промежуток времени с момента начала рабочего дня. Простоем считается временной участок, в течение которого не обрабатывается ни одна деталь. Инженер решил узнать, какова суммарная длительность простоев за день и какова длительность наибольшего простоя. Общая длительность рабочего дня L секунд.

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

Запишите в ответе два числа: суммарную длительность простоев за день и длительность наибольшего простоя.

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

1000 4
600 750
350 450
0 350
950 1000

При таких условиях имеется два простоя: 450--600; 750--950. Их суммарная длительность 350, наибольший имеет длину 200. Ответ: 350 200.

(А. Кабанов) Автомат фиксирует пассажиров некоторого автобуса по ходу рейса. У каждого пассажира фиксируется время входа и выхода с момента начала рейса. Необходимо узнать максимальное количество пассажиров, одновременно находящихся в автобусе, и общее время, когда в автобусе был хотя бы один пассажир. Временем входа и выхода в автобус пренебречь.

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

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

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

7
10 40
50 130
70 130
75 90
120 170
140 170
150 180

В приведённом примере пассажиры были в временных отрезках 10-40 и 50-180. Максимальное количество пассажиров одновременно 3. Ответ: 3 160.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(Е. Джобс) Игра «Заполни поле» заключается в том, чтобы заполнить прямоугольное поле, разбитое на квадраты. Игрок хочет написать программу, которая определила бы сколько есть позиций, в которые можно поместить горизонтальные блоки из четырех квадратов.

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

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

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

7 6 10
1 1
1 5
2 5
2 6
3 1
3 7
5 2
6 3
6 5
6 7

После анализа пар можем прийти к выводу, что имеем дело со следующим полем:

Расположить линию из четырех квадратов можно в 9 позициях (2;1), (3; 2), (3; 3), (4; 1), (4; 2), (4; 3), (4; 4), (5; 3), (5; 4). Максимальное количество позиций (4), в которых можно расположить фигуру, в 4 ряду. Ответ: 9 4.

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

Входные данные представлены в файле 26-71.txt следующим образом. В первой строке входного файла записаны два числа, разделённые пробелом пробел: число N -- количество доступных товаров (натуральное число, не превышающее 10000) и число S -- вес, не более которого можно отправить каждый тип товара (натуральное число, не превышающее 10⁸). В каждой из следующих N строк записаны по два числа, разделённые пробелом: код товара (натуральное число, не превышающее 10⁹) и его вес (натуральное число, не превышающее 10⁵). Известно, что количество различных кодов товаров в файле не превышает тысячи.

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

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

8 13
150 8
237 3
237 6
150 4
237 5
237 6
150 3
150 3

При таких исходных данных имеется всего два вида товаров (с кодами 150 и 237). Товаров с кодом 150 можно погрузить три штуки (3, 3 и 4), останется 1 штука (8). Товаров с кодом 237 можно погрузить две штуки (за 3 и 5), останется 2 штуки (6 и 6). Ответ: 3 237.

(А. Кабанов) На складе хранятся слитки металла различного веса. При отправке из одного или нескольких слитков формируется партия нужного веса, распил слитков не допускается. Складские запасы формируются так, чтобы из слитков можно было можно выдать партию любого веса, не превышающего суммарное количество металла на складе. Для этого должно выполняться следующее правило: вес каждого слитка не должен превышать суммарный вес меньших слитков более чем на 1.

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

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

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

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

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

4
1
4
1
11

При таких исходных данных два слитка не подходят под условие: 4 и 11. Для исправления будут заказаны слитки весом 1 и 4 (2 слитка общим весом 5). Ответ: 2 5.