В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».
Компания, в которой работает Вася, переехала в новый опенспейс, представляющий собой квадрат размером и состоящий из ячеек. В каждой из ячеек может расположиться рабочее место сотрудника (сотрудники занумерованы числами от 1 до ) или какое-либо развлечение, например, аэрохоккей или стол с печеньками (развлечений , они занумерованы отрицательными числами от до ), .
HR-специалисты компании выяснили важность каждого из развлечений для каждого из сотрудников: кому-то нравится аэрохоккей, а кто-то предпочитает сидеть поближе к печенькам. Некоторым сотрудникам, наоборот, может не нравиться близость к некоторым развлечениям — тогда важность развлечения будет отрицательной. В результате опроса для каждого сотрудника определили параметров , , …, — важность развлечений с номерами , , …, соответственно.
Пусть рабочее место сотрудника расположено в строке и столбце , а развлечение в строке и столбце . Определим близость , которая будет определяться как (Манхэттенское расстояние).
Неудовлетворенность сотрудника определяется как сумма произведений близости сотрудника к развлечению на важность этого развлечения для сотрудника, т.е. , где — близость сотрудника к развлечению с номером , а — важность этого развлечения.
Помогите HR-специалистам определить расположение рабочих мест сотрудников и развлечений так, чтобы минимизировать суммарную неудовлетворенность всех сотрудников.
В первой строке задается количество наборов входных данных . В этой задаче .
Затем следует описаний наборов, разделенных пустой строкой.
В первой описания набора строке задается три числа ( , , , ) — количество сотрудников, развлечений и размер опенспейса соответственно.
В следующих строках описания набора записано по чисел , , …, — важность развлечений для очередного сотрудника.
Для каждого набора выведите таблицу размером на , состоящую из чисел от до и чисел от до — расположение рабочих мест сотрудников и развлечений в опенспейсе. Если вы не можете составить решение для какого-либо набора — выведите для него единственное число 0 и этот набор будет пропущен при проверке.
Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).
Каждый тестовый набор оценивается максимум в 5 баллов. Оценка за набор вычисляется по формуле , где — минимальная неудовлетворенность среди решений всех участников и жюри, а — неудовлетворенность в решении участников.