(Д. Бахтиев) Во время погрузки корабля все грузы последовательно подаются к причалу. Каждый груз имеет массу (в килограммах) — целое положительное число.

Для равномерной загрузки и обеспечения безопасности все грузы нужно распределить по трюмам корабля по следующим правилам: в один трюм можно поместить любое количество грузов, но при этом разница между самым лёгким и самым тяжёлым грузом в трюме не должна превышать \(T\) кг, а общая масса грузов в трюме не должна превышать \(M\) кг. Также известно, что грузы помещаются в трюмы в порядке неубывания их масс. Если груз по массе не может быть добавлен ни в один из уже созданных трюмов, для него открывается новый трюм

Входные данные:

В первой строке заданы три целых числа \(N\) — количество грузов \((1 \leqslant N \leqslant 100000),\) \(T\) — максимальная разница между массами грузов одного трюма \((1 \leqslant T \leqslant 1000),\) \(M\) — максимальная общая масса грузов одного трюма \((1 \leqslant M \leqslant 10^9).\) Каждая из следующих \(N\) строк содержит одно целое число — массу груза в килограммах (от \(1\) до \(10^6),\) в произвольном порядке.

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

Типовой пример организации данных во входном файле

\(8 \,\, 50 \,\, 300\)
\(30\)
\(20\)
\(70\)
\(10\)
\(250\)
\(200\)
\(150\)
\(80\)

При таких исходных данных в первый трюм можно поместить грузы, с массами: \(30,\) \(20\) и \(10,\) во второй \(70\) и \(80,\) в третий, четвёртый и пятый будут складированы по одному грузу — \(150,\) \(200\) и \(250\) (из-за общего ограничения по массе в одном трюме). Ответ: \(5 \,\, 3.\)

(Л. Шастин) При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить три билета на такие соседние места в одном ряду, чтобы перед каждым из них хотя бы \(V\) кресел (необязательно подряд идущих) с такими же номерами были заняты, а ряд находился как можно ближе к сцене. Если в этом ряду таких троек мест несколько, найдите тройку с наибольшими номерами. В ответе запишите два целых числа: искомый номер ряда и сумму номеров мест в найденной тройке. Нумерация рядов и мест ведётся с \(1.\) Гарантируется, что хотя бы одна такая тройка в зале есть.

Входные данные

В первой строке входного файла находятся четыре числа: \(N\) — количество занятых мест в зале (целое положительное число, не превышающее \(1~000~000),\) \(M\) — количество рядов (целое положительное число, не превышающее \(1~000),\) \(K\) — количество, мест в каждом ряду (целое положительное число, не превышающее \(1~000)\) и \(V\) — минимальное количество занятых кресел перед выбранными местами с теми же номерами (целое положительное число, не превышающее \(1~000).\) В следующих \(N\) строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения \(M,\) а второе — \(K).\)

Выходные данные

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

Типовой пример организации данных во входном файле

При таких исходных данных ответом является пара чисел \(3\) и \(12\) (места №3, 4 и 5 в ряду №3).

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

(Л. Шастин) Исследователь отправляется в экспедицию через пустыню, чтобы добраться до древнего храма, расположенного на расстоянии \(R\) километров от стартовой точки (которая определена первым километром). В начале пути его верблюд полностью отдохнувший и может пройти \(V\) километров без остановки. По пути расположены оазисы, в которых можно напоить верблюда и позволить ему восстановить силы, чтобы снова пройти до \(V\) километров. Известны координаты \(N\) оазисов — километры от начала пути, на которых они расположены, а также запас воды в каждом из них (в у. е). Каждая \(1\) у.е. воды эквивалентна \(1\) километру пути, который может преодолеть верблюд. Определите, какое минимальное количество оазисов придется посетить, чтобы достигнуть древнего храма, а также минимально возможный номер километра расположения оазиса, который получится посетить последний раз.

Входные данные

В первой строке входного файла находится три натуральных числа: \(N\) \((N < 100~000)\) — количество оазисов на пути, \(R\) \((R < 10~000~000)\) — расстояние от стартовой точки до храма, и \(V\) \((V < R)\) — максимальное количество километров, которые может пройти полностью отдохнувший верблюд. В следующих \(N\) строках находятся по два числа: расстояние (в километрах) между стартовой точкой и очередным оазисом, и запас воды в каждом из них (в у. е.). Каждое из чисел целое, не превосходящее \(10~000~000.\)

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

Типовой пример организации данных во входном файле

\(7 \,\, 50 \,\, 20\)
\(10 \,\, 20\)
\(19 \,\, 9\)
\(15 \,\, 11\)
\(40 \,\, 20\)
\(31 \,\, 5\)
\(41 \,\, 10\)
\(30 \,\, 10\)

При таких исходных данных можно сделать \(3\) остановки: \(\{15, \, 30, \, 41\}\) или \(\{15, \, 30, \, 40 \}\) или \(\{10, \, 30, \, 40 \}.\) Ответ: \(3 \,\, 40.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

(Д. Бахтиев) Во время матча в расширенной версии игры «Морской бой» велась автоматическая фиксация попаданий по игровому полю. Каждое попадание фиксируется по координатам клетки игрового поля (целые положительные числа \(x\) и \(y)\) и времени попадания — целому числу \(t\) (в секундах от начала матча).

Игровое поле — прямоугольное. Координаты попаданий \((x, \, y)\) указываются в формате: \(x\) — номер строки (считая сверху вниз, от \(1\) с шагом \(1),\) \(y\) — номер столбца (слева направо, от \(1\) с шагом \(1).\) Некоторые клетки могли быть поражены несколько раз.

Требуется определить такую клетку, в которую было произведено не менее двух попаданий, и среди них — найти ту, в которой минимальный интервал времени между любыми двумя её попаданиями — наименьший. В ответе нужно вывести сумму координаты этой клетки \((x + y),\) а также этот минимальный интервал в секундах. Если таких клеток несколько, выберите среди них клетку с наименьшим номером строки, а если таких тоже несколько — с наименьшим номером столбца.

Входные данные:

В первой строке записано одно целое число \(N\) — количество попаданий \((1 \leqslant N \leqslant 1000000).\) В следующих \(N\) строках заданы тройки целых чисел \(x \, y \, t\) — координаты клетки и время попадания \((1 \leqslant x \leqslant 10000, \,\,1 \leqslant y \leqslant 10000, \, 0 \leqslant t \leqslant 10^6).\)

Выходные данные.

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

Типовой пример организации входных данных:
\(7\)
\(2 \,\, 3 \,\, 10\)
\(1 \,\, 1 \,\, 3\)
\(2 \,\, 3 \,\, 15\)
\(3 \,\, 2 \,\, 20\)
\(1 \,\, 1 \,\, 10\)
\(2 \,\, 3 \,\, 17\)
\(1 \,\,1 \,\, 6\)

Для приведённого примера более одного попаданий было в клетки с координатами \((2, \, 3)\) и \((1, \, 1).\) Минимальный интервал между попаданиями, равный двум секундам, был у клетки с координатами \((2, \, 3).\) Ответ: \(5 \,\, 2.\)

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

Входные данные

Первая строка входного файла содержит целое число \(N\) – общее количество деталей. Каждая из следующих \(N\) строк содержит три числа и букву A или B. Первое число – время поступления в мастерскую, второе число – длительность обработки на станке А, третье число – длительность обработки на станке B, буква показывает какая операция должна выполняться первой.

В ответе запишите два целых числа: сначала количество деталей, которые не сразу попали на обработку на станке A и были поставлены в очередь, затем время окончания обработки всех деталей на станке A (в минутах от 00ч. 00 мин. понедельника).

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

\(4\)
\(4 \, 3 \, 5 \, A\)
\(7 \, 4 \, 4 \, B\)
\(17 \, 2 \, 3 \, B\)
\(18 \, 6 \, 7 \, A\)

По этим данным детали будут обрабатываться в следующем порядке.
Первая деталь, станок А. 4 – 7 мин.
Первая деталь, станок B. 7 – 12 мин.
Вторая деталь, станок B. 12 – 16 мин. После ожидания.
Вторая деталь, станок A. 16 – 20 мин.
Третья деталь, станок B. 17 – 20 мин.
Четвёртая деталь, станок А. 20 – 26 мин. После ожидания.
Третья деталь, станок A. 26 – 28 мин. После ожидания.
Четвёртая деталь, станок B. 26 – 33 мин.
Станок А ожидали две детали. Обработка на станке А завершена в 28 мин.

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

Входные данные

В первой строке входного файла находятся три числа: \(N\) – количество занятых кают на палубе (целое положительное число, не превышающее \(100~000),\) \(M\) – количество рядов (целое положительное число, не превышающее \(10~000)\) и \(K\) – количество кают в каждом ряду (целое положительное число, не превышающее \(1~000~000).\) В следующих \(N\) строках находятся пары натуральных чисел: номер ряда и номер занятой каюты соответственно (первое число не превышает значения \(M,\) а второе – \(K).\)

Выходные данные

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

Типовой пример организации данных во входном файле

\(7 7 8\)
\(1 \,\, 1\)
\(6 \,\, 6\)
\(5 \,\, 5\)
\(6 \,\, 7\)
\(4 \,\, 4\)
\(2 \,\, 2\)
\(3 \,\, 3\)

При таких исходных данных и отсутствии ограничений на количество забронированных в ряду кают ответом является пара чисел \(6\) и \(1.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.