Все задачи

Город 4е сильно вырос и было решено разделить его на 4 района. Город имеет форму квадрата размером `N\ times\ N` кварталов. Каждый квартал либо застроен зданием, либо является пустым. Для разделения на районы нужно провести две прямые линии между кварталами – по вертикали и горизонтали – таким образом, чтобы количества зданий в каждом районе не слишком сильно отличались.

Напишите программу, которая по плану города вычислит способ разделения города на 4 района, минимизирующий значение выражения `∑(K_i-K/4)^2`, где `K` – количество зданий в городе, `K_i` – количество зданий в `i`-м районе. Если существует несколько вариантов с минимальным значением, то вывести из них тот вариант, в котором минимально значение выражения `∑(S_i-S/4)^2`, где `S\ =\ N^2` – общая площадь города, `S_i` – площадь `i`-го района. При одинаковых значениях обоих выражений выбрать минимальное значение для положения горизонтальной границы, затем – вертикальной.

Во входном файле несколько тестовых случаев. Каждый тест начинается со строки, содержащей одно целое число `N` (`2\ ≤\ N\ ≤\ 500`) – размер города. Далее следует `N` строк, содержащих по `N` символов – план города. Символ '#' означает квартал со зданием, символ '.' – пустырь. Набор тестов заканчивается строкой, содержащей число 0.

Для каждого тестового случая вывести строку, содержащую два целых числа, разделенных пробелом – положение вертикальной, затем горизонтальной линий разделения города на районы. Верхний левый угол имеет координаты (0,0), правый нижний – `(N,N)`.

4
####
#...
.#..
..#.
3
#.#
.#.
#.#
0

2 1
1 1

Город 4е имеет форму квадрата размером `N\ times\ N` кварталов. Каждый квартал либо застроен зданием, либо является пустым. Необходимо построить широкое шоссе из левого верхнего угла города в правый нижний угол. Шоссе должно проходить через кварталы города, являющие соседними по горизонтали или вертикали. Шоссе не должно выходить за пределы города и проходить более чем через `2*N+1` кварталов. Часть зданий при строительстве придется снести.

Напишите программу, которая по плану города определит минимальное количество зданий, которое потребуется снести при строительстве шоссе.

Во входном файле несколько тестовых случаев. Каждый тест начинается со строки, содержащей одно целое число `N` (`2\ ≤\ N\ ≤\ 500`) – размер города. Далее следует `N` строк, содержащих по `N` символов – план города. Символ '#' означает квартал со зданием, символ '.' – пустырь. Набор тестов заканчивается строкой, содержащей число 0.

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

4
####
#...
.#..
..#.
5
..#..
#.#..
..#..
.##..
.....
0

2
0

Город 4е имеет форму квадрата размером `N\ times\ N` кварталов. Каждый квартал либо застроен зданием, либо является пустым. Необходимо построить кольцевую автодорогу в форме прямоугольника, проходящую только через пустые кварталы.

Напишите программу, которая по плану города находит вариант, максимизирующий площадь прямоугольника, по крайним кварталам которого проходит автодорога.

Во входном файле несколько тестовых случаев. Каждый тест начинается со строки, содержащей одно целое число `N` (`2\ ≤\ N\ ≤\ 200`) – размер города. Далее следует `N` строк, содержащих по `N` символов – план города. Символ '#' означает квартал со зданием, символ '.' – пустырь. Набор тестов заканчивается строкой, содержащей число 0.

Для каждого тестового случая вывести строку, содержащую четыре целых числа `x_1,\ y_1,\ x_2,\ y_2` (`1\ ≤\ x_1\ <\ x_2\ ≤\ N`, `1\ ≤\ y_1\ <\ y_2\ ≤\ N`) – координаты прямоугольника с наибольшей площадью, крайние пустые кварталы которого могут быть использованы для строительства кольцевой автодороги. `x_1,\ x_2` – номера столбцов, `y_1,\ y_2` – номера строк. Квартал в верхнем левом углу имеет координаты (1,1), в правом нижнем – `(N,N)`. Если существует несколько вариантов, вывести любой (один) из них. Если не существует ни одного варианта, вывести сообщение "IMPOSSIBLE".

4
.#..
....
.#.#
...#
3
..#
#.#
..#
0

1 2 3 4
IMPOSSIBLE