В нашей системе имеются заказы, временные склады и курьеры.
Заказы состоят из двух точек - pickup и dropoff. На каждой точке установлен интервал времени, в который её можно посетить.
Временные склады - это точки на карте, в которых курьеры могут складывать содержимое заказов. На временный склад любой курьер может выгрузить (dropoff) содержимое любого заказа и любой курьер может забрать любое отправление, имеющееся на складе. Попытка забрать отправление, которого нет на складе приводит к полностью нерабочему решению. Временные склады работают круглые сутки и не имеют ограничений по вместимости.
Курьеры - это идеальные исполнители, чётко выполняющие выданные инструкции (маршрутные листы).
Каждый вечер формируется список заказов на завтра и список курьеров, готовых завтра поработать. Наша задача - сформировать для курьеров маршрутные листы таким образом, чтобы прибыль компании за день была максимальной.
День проходит следующим образом:
Каждый курьер в начале дня получает маршрутный лист с указаниями в какую точку переместиться и какое действие там выполнить. В начале своего рабочего времени (в рамках нашей задачи у всех курьеров это 6 утра) курьеры начинают движение к первой указанной в маршрутном листе точке, в случае необходимости ждут начала интервала и выполняют указанное действие. В случае, если действие выполнить оказывается невозможно (неверная точка, неверное действие, непопадание во временной интервал) курьер ломается и ломает всю систему, то есть наличие хотя бы одного маршрутного листа с ошибкой приводит к полностью нерабочему решению.
В маршрутном листе могут быть как точки заказов, так и точки временных складов.
В конце дня все курьеры получают заработок в размере 2 тугрика за фактически отработанную минуту (т.е. за разницу между временем последнего выполненного действия и временем начала работы курьера. Таким образом, в случае пустого маршрутного листа заработок курьера нулевой).
После прохождения всеми курьерами своих маршрутов заказы получаются разделенными на три множества:
- выполненные - у которых были посещены обе точки;
- невыполненные - у которых не было посещено ни одной точки;
- незаконченные - у которых была посещена только одна точка;
В случае непустого множества незаконченных заказов решение считается нерабочим. В случае, если размер множества выполненных заказов меньше количества курьеров решение считается нерабочим.
Все выполненные заказы приносят доход (сумма оплат всех заказов множества).
Прибыль компании вычисляется как разница между доходом и суммарным заработком курьеров.
Координаты и расстояния задаются в условных единицах.
Время задаётся в минутах от начала суток (т.е. 6:00 - это 360, 11:00 - 660, 12:10 - 730 и так далее).
Время в пути между точками с координатами (x0, y0) - (x1, y1) вычисляется по формуле
travel_munutes = 10 + (abs(x0 - x1) + abs(y0 - y1))
Пример: example/input.json
Схема: example/input_schema.json
Курьеры (сущности courier):
- courier_id, int, идентификатор курьера, диапазон [1-10000]
- location_x, int, координата курьера в 6:00
- location_y, int, координата курьера в 6:00 Рабочие часы всех курьеров одинаковы - с 6:00 до 23:59
Заказы (сущности order):
- order_id, int, идентификатор заказа, он же идентификатор отправления, диапазон [10001-30000]
- pickup_point_id, int, идентификатор точки забора, диапазон [40001-60000]
- pickup_location_x, int, координата точки забора заказа
- pickup_location_y, int, координата точки забора заказа
- pickup_from, int, начало временного окна, в которое курьер должен посетить точку, в минутах
- pickup_to, int, окончание временного окна, в которое курьер должен посетить точку, в минутах
- dropoff_point_id, int, идентификатор точки назначения, диапазон [60001-80000]
- dropoff_location_x, int, координата точки назначения заказа
- dropoff_location_y, int, координата точки назначения заказа
- dropoff_from, int, начало временного окна, в которое курьер должен посетить точку, в минутах
- dropoff_to, окончание временного окна, в которое курьер должен посетить точку, в минутах
- payment, int, оплата клиентом за выполнение заказа, в тугриках
Временные склады (сущности depot)
- point_id, int, идентификатор временного склада забора, диапазон [30001-40000]
- location_x, int, координата точки временного склада
- location_y, int, координата точки временного склада
Все склады работают круглосуточно и не имеют ограничений по вместимости
Пример: sample2/output.json
Схема: sample2/output_schema.json
Event
- courier_id, int, идентификатор курьера
- action, enum, ["pickup", "dropoff"]
- order_id, int, идентификатор заказа/отправления
- point_id, int, идентификатор посещаемой точки
Пример:
{
"courier_id": 1,
"action": "dropoff",
"order_id": 20001,
"point_id": 10001
}Курьер 1 перемещается в точку 10001 и делает dropoff заказа 20001
Решение оформляется в виде репозитория на github, содержащего:
-
исходный кода на языках (на выбор участников) java, python или php;
-
файла README с кратким описанием метода решения;
-
файла SETUP с пошаговой инструкцией по установке дополнительных библиотек под ОС семейства Linux;
-
файлы с решениями примеров simple_solution.json, hard_solution.json и contest_solution.json для входных данных (см. директорию data simple_input.json, hard_input.json, contest_input.json)
Исходные данные:
Курьер:
{
"courier_id": 1,
"location_x": 20,
"location_y": 20
}Заказы:
{
"order_id": 20001,
"pickup_point_id": 40001,
"pickup_location_x": 10,
"pickup_location_y": 40,
"pickup_from": 420,
"pickup_to": 600,
"dropoff_point_id": 60001,
"dropoff_location_x": 10,
"dropoff_location_y": 90,
"dropoff_from": 480,
"dropoff_to": 660,
"payment": 500
},
{
"order_id": 20002,
"pickup_point_id": 40002,
"pickup_location_x": 60,
"pickup_location_y": 100,
"pickup_from": 480,
"pickup_to": 600,
"dropoff_point_id": 60002,
"dropoff_location_x": 100,
"dropoff_location_y": 100,
"dropoff_from": 360,
"dropoff_to": 660,
"payment": 900
}Склады отсутствуют.
{
"courier_id": 1,
"action": "pickup",
"order_id": 20001,
"point_id": 40001
},
{
"courier_id": 1,
"action": "dropoff",
"order_id": 20001,
"point_id": 60001
},
{
"courier_id": 1,
"action": "pickup",
"order_id": 20002,
"point_id": 40002
},
{
"courier_id": 1,
"action": "dropoff",
"order_id": 20002,
"point_id": 60002
}Проследуем с курьером по его маршруту:
Выезд в 360 минут (6 утра). Время в пути до первой точки 10 + (20-10) + (40-20) = 40 минут, прибытие на первую точку в 400 минут. Это меньше, чем открытие окна в 420, следовательно курьер будет ждать 20 минут.
Забрав отправление, курьер поедет на вторую точку этого заказа, время в пути составит 10 + (10-10) + (90-40) = 60 минут, то есть курьер прибудет во вторую точку в 480 и попадёт в указанный интервал.
Сдав отправление, курьер поедет на первую точку второго заказа, время в пути составит 10 + (60 - 10) + (100 - 90) = 70 минут, то есть курьер прибудет на точку в 550 минут, попадая в интервал.
Далее курьер поедет на вторую точку второго заказа, время в пути составит 10 + (100 - 100) + (100 - 60) = 50 минут, т.е прибудет в 600, попав в интервал.
Таким образом, оба заказа будут доставлены, доход составит 900 + 500 = 1400 тугриков, а зарплата курьра будет 2 * (600 - 360) = 480, итоговая прибыль - 920 тугриков.
{
"courier_id": 1,
"action": "pickup",
"order_id": 20001,
"point_id": 40001
},
{
"courier_id": 1,
"action": "pickup",
"order_id": 20002,
"point_id": 40002
},
{
"courier_id": 1,
"action": "dropoff",
"order_id": 20002,
"point_id": 60002
},
{
"courier_id": 1,
"action": "dropoff",
"order_id": 20001,
"point_id": 60001
}Считаем: Выезд все еще в 360. Время в пути до первой точки такое же - 40 минут, 20 минут придется подождать, завершить точку в 420.
Далее курьер поедет на первую точку второго заказа, затратив на это 10 + (60 - 10) + (100 - 40) = 120 минут. В 540 он успешно пройдёт точку и поедет дальше.
Между первой и второй точками второго заказа мы уже считали - 50 минут, то есть курьер завершит ее в 590, уложившись в интервал.
Дорога до оставшейся точки займет 10 + (100 - 10) + (100 - 90) = 110 минут, курьер прибудет на нее в 700, не попав в окно.
Решение полностью нерабочее.