| Автор: | И. Туфанов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
Модель Изинга используется в физике для описания твердого тела. Она использует представление кристаллической решетки, в узлах которой находятся атомы.
Рассмотрим плоскую прямоугольную решетку с N узлами по вертикали и M узлами по горизонтали (всего NM узлов). Каждый узел характеризуется своим спином, который может принимать значения + 1 или − 1.
Соседними считаются узлы решётки, смежные по горизонтали или вертикали. Назовём энергией решетки количество пар соседних узлов с различными спинами.
Дана решётка с известными спинами в каждом узле. Требуется поменять спины ровно двух различных узлов на противоположные таким образом, чтобы энергия полученной решетки была максимальна. Если существует несколько решений, вывести любое из них.
Энергия решетки, приведенной в примере, равна 13. После изменения спина левого верхнего узла и третьего узла во второй строке получим решетку с энергией 15.
В выходной файл выведите четыре числа: r1 c1 r2 c2 — координаты двух узлов, изменение спина в которых максимально увеличит энергию. ri — номер строки узла, ci — номер узла в его строке. Нумерация начинается с 1.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|