Ограничение времени | 5 секунд |
Ограничение памяти | 64 Мб |
Ввод | стандартный ввод или input.txt |
Вывод | стандартный вывод или output.txt |
В этой задаче на проверку необходимо сдать исходный код программы.
Компания, в которой работает Вася, переехала в новый опенспейс, представляющий собой квадрат размером и состоящий из ячеек. В каждой из ячеек может расположиться рабочее место сотрудника (сотрудники занумерованы числами от 1 до ) или какое-либо развлечение, например, аэрохоккей или стол с печеньками (развлечений , они занумерованы отрицательными числами от до ), .
HR-специалисты компании выяснили важность каждого из развлечений для каждого из сотрудников: кому-то нравится аэрохоккей, а кто-то предпочитает сидеть поближе к печенькам. Некоторым сотрудникам, наоборот, может не нравиться близость к некоторым развлечениям — тогда важность развлечения будет отрицательной. В результате опроса для каждого сотрудника определили параметров , , …, — важность развлечений с номерами , , …, соответственно.
Пусть рабочее место сотрудника расположено в строке и столбце , а развлечение в строке и столбце . Определим близость , которая будет определяться как (Манхэттенское расстояние).
Неудовлетворенность сотрудника определяется как сумма произведений близости сотрудника к развлечению на важность этого развлечения для сотрудника, т.е. , где — близость сотрудника к развлечению с номером , а — важность этого развлечения.
Помогите HR-специалистам определить расположение рабочих мест сотрудников и развлечений так, чтобы минимизировать суммарную неудовлетворенность всех сотрудников.
В первой строке задается количество наборов входных данных . В этой задаче всегда равно 1.
Затем следует описаний наборов, разделенных пустой строкой.
В первой описания набора строке задается три числа ( , , , ) — количество сотрудников, развлечений и размер опенспейса соответственно.
В следующих строках описания набора записано по чисел , , …, — важность развлечений для очередного сотрудника.
Для каждого набора выведите таблицу размером на , состоящую из чисел от до и чисел от до — расположение рабочих мест сотрудников и развлечений в опенспейсе.
Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
Каждый тестовый набор оценивается максимум в 5 баллов. Оценка за набор вычисляется по формуле , где — минимальная неудовлетворенность среди решений всех участников и жюри, а — неудовлетворенность в решении участников.
Ввод | Вывод |
---|---|
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 |