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

Ограничение времени5 секунд
Ограничение памяти64 Мб
Вводстандартный ввод или input.txt
Выводстандартный вывод или output.txt

В этой задаче на проверку необходимо сдать исходный код программы.

Компания, в которой работает Вася, переехала в новый опенспейс, представляющий собой квадрат размером 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 T всегда равно 1.

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

В первой описания набора строке задается три числа N , K , S N, K, S ( 1 N 8 1 \le N \le 8 , 1 K 3 1 \le K \le 3 , 1 S 3 1 \le S \le 3 , 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  — расположение рабочих мест сотрудников и развлечений в опенспейсе.

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

Оценка за эту задачу — 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  — неудовлетворенность в решении участников.

Пример

ВводВывод
1
6 3 3
1 1 1
1 0 0
1 1 0
2 3 5
0 0 0
7 4 1
6 -2 1
-1 4 -3
2 3 5