images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 22:04:12

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1176. Роботы на марше

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

`N` роботов-охранников необходимо переместить на новые позиции. Роботы могут выполнять только 4 команды – перемещение на расстояние в одну единицу в направлении юг, север, запад или восток. На выполнение команды тратится одна единица энергии. Роботы абсолютно одинаковы, поэтому неважно какой конкретно робот приедет на новое место дислокации. Также роботы такие маленькие (нанороботы), что несколько роботов могут находиться в одной точке. Требуется найти план перемещения с минимальными затратами энергии.
В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество роботов. Далее следует `N` строк, содержащих по 2 целых чисел – начальные координаты каждого робота. Далее следует `N` строк, содержащих по 2 целых чисел – конечные координаты, в которых должны оказаться роботы. Все координаты в диапазоне от 0 до 1000.
Вывести в первой строке минимальные затраты энергии. Во второй строке вывести `N` чисел – `i`-е число указывает номер конечной позиции, куда должен переместиться `i`-й робот. Если существует несколько решений с минимальными затратами, то вывести любое из них.

Пример ввода

3
0 0
2 0
4 3
2 3
2 4
1 0

Пример вывода

7
3 2 1
loading