Оптимальный опенспейс - 2

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».

Компания, в которой работает Вася, переехала в новый опенспейс, представляющий собой квадрат размером S × S S \times S и состоящий из ячеек. В каждой из ячеек может расположиться рабочее место сотрудника (сотрудники занумерованы числами от 1 до N N ) или какое-либо развлечение, например, аэрохоккей или стол с печеньками (развлечений K K , они занумерованы отрицательными числами от 1 -1 до K -K ), N + K = S × S N + K = S \times S .

HR-специалисты компании выяснили важность каждого из развлечений для каждого из сотрудников: кому-то нравится аэрохоккей, а кто-то предпочитает сидеть поближе к печенькам. Некоторым сотрудникам, наоборот, может не нравиться близость к некоторым развлечениям — тогда важность развлечения будет отрицательной. В результате опроса для каждого сотрудника определили K K параметров P 1 P_1 , P 2 P_2 , …, P K P_K  — важность развлечений с номерами 1 -1 , 2 -2 , …, K -K соответственно.

Пусть рабочее место сотрудника e m p emp расположено в строке I e m p I_{emp} и столбце J e m p J_{emp} , а развлечение f u n fun в строке I f u n I_{fun} и столбце J f u n J_{fun} . Определим близость d i s t dist , которая будет определяться как I e m p I f u n + J e m p J f u n |I_{emp} - I_{fun}| + |J_{emp} - J_{fun}| (Манхэттенское расстояние).

Неудовлетворенность сотрудника определяется как сумма произведений близости сотрудника к развлечению на важность этого развлечения для сотрудника, т.е. u n f u n = i = 1 K d i s t i × P i unfun = \sum\limits_{i=1}^{K} dist_i \times P_i , где d i s t i dist_i  — близость сотрудника к развлечению с номером i -i , а P i P_i  — важность этого развлечения.

Помогите HR-специалистам определить расположение рабочих мест сотрудников и развлечений так, чтобы минимизировать суммарную неудовлетворенность всех сотрудников.

Формат ввода

В первой строке задается количество наборов входных данных T T . В этой задаче T = 10 T = 10 .

Затем следует T T описаний наборов, разделенных пустой строкой.

В первой описания набора строке задается три числа N , K , S N, K, S ( 1 N 99 1 \le N \le 99 , 1 K 10 1 \le K \le 10 , 1 S 10 1 \le S \le 10 , N + K = S × S N + K = S \times S ) — количество сотрудников, развлечений и размер опенспейса соответственно.

В следующих N N строках описания набора записано по K K чисел P 1 P_1 , P 2 P_2 , …, P K P_K  — важность развлечений для очередного сотрудника.

Формат вывода

Для каждого набора выведите таблицу размером S S на S S , состоящую из чисел от 1 -1 до K -K и чисел от 1 1 до N N  — расположение рабочих мест сотрудников и развлечений в опенспейсе. Если вы не можете составить решение для какого-либо набора — выведите для него единственное число 0 и этот набор будет пропущен при проверке.

Система оценивания

Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).

Каждый тестовый набор оценивается максимум в 5 баллов. Оценка за набор вычисляется по формуле 5 × ( B e s t A n s U s e r A n s ) 5 5\times (\frac{BestAns}{UserAns})^5 , где B e s t A n s BestAns  — минимальная неудовлетворенность среди решений всех участников и жюри, а U s e r A n s UserAns  — неудовлетворенность в решении участников.