54
правки
Изменения
→Решение за O(n + m)
=== Доказательство корректности ===
Докажем, что каждый ход в соседнюю ячейку отсекает только те столбцы или строки, которые точно не содержат искомый элемент. Назовем ход корректным, если он отсекает только те строки или колонки, в которых точно нет искомого элемента. Пусть первый ход (в правую верхнюю ячейку) корректный (он не отсек ни одной строки или столбца). Пусть предыдущий ход был корректным. Докажем, что следующий ход, выполненный по правилам, будет корректным: если текущий элемент меньше необходимого,
=== Код ===
