Задание 26 ЕГЭ по информатике

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

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

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

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

В первой строке записано одно целое число $N$ — количество попаданий ($1 \leq N \leqslant 1 000 000$). В следующих $N$ строках заданы тройки целых чисел $(x, y, t)$ — координаты клетки и время попадания ($1 \leq x \leqslant 10 000$, $1 \leq y \leqslant 10 000$, $0 \leq t \leq 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.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/22605_26.txt