Задание 26. Информатика. ЕГЭ. Шастин. 1.6.2025

(Д. Бахтиев) Во время матча в расширенной версии игры «Морской бой» велась автоматическая фиксация попаданий по игровому полю. Каждое попадание фиксируется по координатам клетки игрового поля (целые положительные числа \(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.\)

fd = open('26.txt')
N = int(fd.readline())

cells = {}

for line in fd:
    x, y, t = map(int, line.split())
    if cells.get((x, y)):
        cells[(x, y)].append(t)
    else:
        cells[(x, y)] = [t]
arr = []
for c in cells:
    if len(cells[c]) > 1:
        tmp = sorted(cells[c])
        m = min(y - x for x, y in zip(tmp, tmp[1:]))
        arr.append((m, c[0], c[1]))
arr.sort()
print(arr[0][1] + arr[0][2], arr[0][0])