Московская олимпиада школьников 10-11 2025
6 апр 2025, 11:52:00
старт:
6 апр 2025, 10:30:22
финиш:
6 апр 2025, 14:30:22
до финиша:
02:38:20
начало:
6 апр 2025, 10:33:22
конец:
6 апр 2025, 11:00:00
длительность:
04:00:00
...

###### Оценка посылки и тестов

Вердикт ОК как при онлайн проверке теста, так и при оффлайн означает только, что формат выходных данных верный. При этом за тест может быть выставлено и 0 баллов. При онлайн проверке вы видите правильный общий балл. В зачет пойдет последний из них. При оффлаайн проверке будет проверена последняя посылка.

###### Зачет решений

Обратите внимание, что в зачет пойдет результат ПОСЛЕДНЕЙ посылки по любой задаче, даже с онлайн-проверкой. Будьте внимательны, особенно в конце тура.

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

##

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

Компания, в которой работает Вася, переехала в новый опенспейс, представляющий собой квадрат размером S×S
S×S и состоящий из ячеек. В каждой из ячеек может расположиться рабочее место сотрудника (сотрудники занумерованы числами от 1 до N
N) или какое-либо развлечение, например, аэрохоккей или стол с печеньками (развлечений K
K, они занумерованы отрицательными числами от −1
−1 до −K
−K), N+K=S×S
N+K=S×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
e m p расположено в строке I e m p
I e m p​ и столбце J e m p
J e m p​, а развлечение f u n
f u n в строке I f u n
I f u n​ и столбце J f u n
J f u n​. Определим близость d i s t
d i s t, которая будет определяться как ∣I e m p−I f u n∣+∣J e m p−J f u n∣
∣I e m p​−I f u n​∣+∣J e m p​−J f u n​∣ (Манхэттенское расстояние).

Неудовлетворенность сотрудника определяется как сумма произведений близости сотрудника к развлечению на важность этого развлечения для сотрудника, т.е. u n f u n=∑K i=1 d i s t i×P i
u n f u n=i=1∑K​d i s t i​×P i​, где d i s t i
d i s t 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≤N≤99, 1≤K≤10
1≤K≤10, 1≤S≤10
1≤S≤10, N+K=S×S
N+K=S×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×(U ser A n s B es t A n s​)5, где B e s t A n s
B es t A n s — минимальная неудовлетворенность среди решений всех участников и жюри, а U s e r A n s
U ser A n s — неудовлетворенность в решении участников.

Набрать здесь Отправить файл
1

    ​

Выбрать Файл не выбран
осталось 100 попыток
Посылок нет