07/04/2025 00:35:18

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1044. Разделение на районы

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Город 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

01/09/2008	Заочный тур личного первенства (A)
19/09/2013	Занятие 3 для продолжающих (A)