Информатика

(Л. Евич) В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько -- к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.

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

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

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

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

2 5
1 8
6 12
8 4
8 14
8 9

Пусть максимальное время обслуживания равно 15 минутам. При таких исходных данных клиенты обслуживаются следующим образом. 1-й банкомат: клиенты со временем обслуживания 8, 4, 14; 2-й банкомат: клиент со временем обслуживания 12. Клиента со временем 9 обслужить за 15 минут не удаётся. Последний обслуженный клиент (со временем 14) начинает работу с 1-м банкоматом на 13-й минуте. Ответ: 4 1.

(Досрочный ЕГЭ-2023) Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.

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

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

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

2
5
30 60
40 1000
59 60
61 1000
1010 1440

При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры. Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны. Ответ: 4 1.

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

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

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

6
2 12
1 4
2 30
2 10
4 15
2 5

При этих данных линия максимальной длины находится в ряду 2, она включает светлые точки с позициями 5, 10 и 12, а также все тёмные точки между ними. Общая длина линии равна 8. Ответ: 8 2.

(PRO100 ЕГЭ) В супермаркете проводится акция «каждый шестой товар в чеке за полцены». У покупателя есть 100 000 рублей. Какое максимальное количество товаров может купить покупатель, если он сам выберет расположение товаров в чеке?

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

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

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

5
4
80
30
50
40

Пусть и покупателя есть 140 рублей и идёт акция «каждый второй товар в чеке за полцены». При таких исходных данных ответом на первый вопрос будет число 5 (расположение товаров в чеке: 40 50 4 80 30, сумма покупки: 40 + 50/2 + 4 + 80/2 + 30 = 139), на второй вопрос -- число 1 (140 - 139 = 1).

(А. Богданов) В некотором вузе на некое направление на М бюджетных мест поступает N абитуриентов, которые сдали ЕГЭ по русскому языку, профильной математике, физики и/или информатике. В зачет идет 3 экзамена. Если сданы и физика, и информатика, то в зачет идёт максимальный балл из двух предметов. В первую очередь зачисляются те, кто подал оригиналы документов. Необходимо определить гарантированно проходной балл. В ответе не нужно указывать полупроходные баллы, с которыми можно и не пройти.

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

Входные данные представлены в файле 26-108.txt следующим образом. В первой строке записаны два числа, разделённые пробелом: N -- количество абитуриентов (1 ≤ N ≤ 10000), M -- количество бюджетных мест на направление (1 ≤ М ≤ 10000). В следующих N строках первое число -- 0 или 1 (отсутствие/наличие оригиналов документов), далее 3 или 4 отметки: баллы по русскому языку, профильной математике, физике и/или информатике.

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

6 2
0 60 80 90 80
1 61 80 90 80
0 62 80 90 80
1 63 80 90
0 64 80 90
1 65 80 90

С учетом наличия оригиналов документов будут зачислены абитуриенты с баллами 235 и 233, так что проходной бал равен 233. Без учета наличия оригиналов документов зачисляются абитуриенты, набравшие 235 и 234 баллов, в этом случае проходной балл 234. Ответ: 233 234.

(Д. Статный) Аэропорту необходимо оптимизировать расписание вылетов аэропланов. Для этого они получили список всех полетов с указанием времени вылета и времени прилета. Известно, что в небе одновременно может находиться только один аэроплан, поэтому необходимо составить расписание так, чтобы обеспечить максимальное количество вылетов. Если время прибытия одного рейса совпадает со временем вылета другого, то вылет может быть осуществлен без задержек по времени.

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

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

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

1000 7
100 200
0 300
200 430
500 550
550 700
700 800
750 900

При таких условиях можно обеспечить 5 полётов: 100-200; 200-430; 500-550; 550-700; 700-800. Ответ: 5 700.

\*(PRO100-ЕГЭ) В супермаркете проводится акция «каждый шестой товар в чеке за полцены». У покупателя есть S рублей. Какое максимальное количество товаров может купить покупатель, если он сам выберет расположение товаров в чеке? Запишите в ответе два целых числа: максимальное количество товаров, которое мог купить покупатель и максимальное количество денег, которое могло у него остаться после покупки максимального количества товаров.

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

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

5 140
4
80
30
50
40

Пример входного файла для акции «каждый второй товар в чеке за полцены». При таких исходных данных ответом на первый вопрос будет число 5. Пример расположения товаров в чеке: 40 50 4 80 30, сумма покупки: 40 + 50/2 + 4 + 80/2 + 30 = 139. Ответ на второй вопрос -- 1 (140 - 139 = 1). Ответ: 5 1.

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

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

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

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

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

7 3
2 1
1 7
1 8
2 3
1 9
2 4
2 2

В данном случае существует две строки с номерами 1 и 2, которые содержат по одной линии длины 3 и 4 соответственно. Ответ: 1 2.

На складе требуется разместить 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-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.