A. Оптимизация такси BuberPool
ограничение по времени на тест
15 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная оптимизационная задача. В отличие от задач, где нужно получить точный ответ, здесь каждое решение получает баллы в зависимости от эффективности. Интерактивность означает, что при в ходе проверки программа жюри и решение участника обмениваются сообщениями через стандартные потоки ввода и вывода. После вывода очередного сообщения обязательно очистите буфер вывода, чтобы часть вашего вывода не осталась в этом буфере. Например, на С++ можно использовать функцию fflush(stdout), на Java вызывать System.out.flush(), на Pascal — flush(output), а на Python — stdout.flush().

Задача состоит в автоматизации диспетчерской службы такси нового поколения BuberPool. Каждое такси может вместить до четырёх пассажиров. В ходе работы такси машины приезжают по заказам, забирают пассажиров и отвозят их по требуемым адресам. Кроме того, в отличие от традиционных такси, машины Buber могут выполнять до четырёх различных заказов одновременно. Например, выполняя заказ и везя пассажира, машина может заехать за дополнительным пассажиром или сделать крюк, чтобы высадить другого пассажира.

Следующая дискретная модель является упрощённой формулировкой описанной выше жизненной задачи.

Рассмотрим город — прямоугольную сетку из $$$w$$$ улиц и $$$h$$$ авеню, на которой отмечены $$$w \times h$$$ перекрёстков. Улицы пронумерованы от $$$1$$$ до $$$w$$$, а авеню — от $$$1$$$ до $$$h$$$. Будем рассматривать целые неотрицательные моменты времени. Действия происходят по тикам — промежуткам между соседними моментами. В любой момент времени каждая машина находится на каком-то перекрёстке $$$(x, y)$$$, где $$$1 \le x \le w$$$ и $$$1 \le y \le h$$$. На одном и том же перекрёстке одновременно может находиться любое число машин. За один тик каждая машина может либо остаться на месте, либо поменять ровно одну из своих координат — номер улицы или номер авеню — на единицу.

В момент времени $$$0$$$ вам заданы начальные позиции $$$k$$$ машин: $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$\ldots$$$, $$$(x_k, y_k)$$$. Количество машин такси равно $$$k$$$ и не меняется во время рассматриваемого промежутка моделирования системы.

Кроме того, на вход вашей программе будут подаваться заказы клиентов. Следует считать, что каждый заказ соответствует ровно одному пассажиру, то есть машина может выполнять до четырёх заказов одновременно. Для упрощения все заказы совершаются в разные моменты времени. Заказы заданы в порядке их совершения. Таким образом, каждый заказ $$$j$$$ характеризуется пятью целыми числами: моментом совершения заказа $$$t_j$$$, местом посадки пассажира $$$(sx_j, sy_j)$$$ и местом высадки пассажира $$$(tx_j, ty_j)$$$.

В момент времени $$$0$$$, а также сразу после получения каждого из заказов, вы можете выдавать инструкции водителям о плане перемещения по городу. Каждый раз вы можете передать набор инструкций любому числу машин (читайте о некоторых ограничениях ниже). Набор инструкций для каждой машины задаётся отдельно. Набор инструкций — это последовательность троек: $$$(cx_1, cy_1, a_1)$$$, $$$(cx_2, cy_2, a_2)$$$, $$$\ldots$$$, $$$(cx_m, cy_m, a_m)$$$, где $$$m$$$ — длина набора. Значение чисел в тройках таково:

  • Машина сначала должна приехать на перекрёсток $$$(cx_1, cy_1)$$$, затем на $$$(cx_2, cy_2)$$$, $$$\ldots$$$, и наконец на $$$(cx_m, cy_m)$$$. Перекрёстки $$$(cx_i, cy_i)$$$ могут быть произвольными перекрёстками города и не обязательно являются местами посадки или высадки пассажиров. При перемещении с одного перекрёстка на другой машина всегда сначала едет, изменяя первую координату, пока она не сравняется с первой координатой точки назначения, а затем вторую. Таким образом, при перемещении из $$$(p_1, q_1)$$$ в $$$(p_2, q_2)$$$ машина сначала проделает путь $$$(p_1, q_1) \rightarrow (p_2, q_1)$$$, а затем $$$(p_2, q_1) \rightarrow (p_2, q_2)$$$. Во время пути машина за один тик меняет ровно одну из своих координат на единицу.
  • Значения $$$a_i$$$ имеют следующий смысл. Если $$$a_i = 0$$$, то машина просто доезжает до перекрёстка $$$(cx_i, cy_i)$$$ и не делает там никаких действий. Если $$$a_i > 0$$$, то машина доезжает до перекрёстка $$$(cx_i, cy_i)$$$ и подбирает там пассажира номер $$$a_i$$$ (его место посадки обязательно должно совпасть с $$$(cx_i, cy_i)$$$, и пассажир должен ещё там находиться). Если $$$a_i < 0$$$, то машина доезжает до перекрёстка $$$(cx_i, cy_i)$$$ и высаживает там пассажира номер $$$-a_i$$$ (его место высадки обязательно должно совпасть с $$$(cx_i, cy_i)$$$, и пассажир должен находиться в этой машине). На посадку и высадку пассажира время не тратится.

При передаче набора инструкций машине предыдущий набор инструкций для неё заменяется новым. Таким образом, каждая машина выполняет не более одного набора инструкций одновременно. Если инструкций нет или все они выполнены, то машина стоит. Инструкции в наборе выполняются последовательно.

При обработке каждого заказа сначала все машины действуют по своим инструкциям до момента этого заказа, затем вашей программе подаётся информация о новом заказе, а после этого вы выводите новые наборы инструкций для некоторых машин. Те машины, которым не пришли новые наборы инструкций, действуют дальше по старым инструкциям.

Таким образом, общая стратегия тестирования вашего решения будет выглядеть следующим образом:

  1. Решение читает размер города, количество машин, их начальные координаты.
  2. Решение отсылает набор инструкций для машин, и этот набор инструкций сразу начинает выполняться.
  3. Решение читает значение $$$t_j$$$ — момент совершения очередного заказа (если $$$t_j = -1$$$, то программа должна отправить финальный набор инструкций и завершить свою работу штатным образом).
  4. Решение читает значения $$$sx_j$$$, $$$sy_j$$$, $$$tx_j$$$, $$$ty_j$$$ — координаты посадки и высадки для $$$j$$$-го заказа.
  5. Решение отсылает очередной набор инструкций для машин.
  6. Переходим к шагу 3.

После завершения работы вашей программы на шаге 3 сначала все инструкции для всех машин будут полностью выполнены, и только после этого симуляция будет завершена.

Количество баллов, которое получит ваше решение за тест — это средний балл по всем заказам, округлённый к ближайшему целому числу. Балл за заказ равен $$$\alpha \cdot (100 + w_0)$$$, где $$$w_0$$$ — это время, требуемое на выполнение заказа в идеальном случае, то есть просто время поездки из $$$(sx_j, sy_j)$$$ в $$$(tx_j, ty_j)$$$ (следовательно, $$$w_0 = |sx_j - tx_j| + |sy_j - ty_j|$$$), а $$$\alpha$$$ — вещественный коэффициент от $$$0$$$ до $$$1$$$, который характеризует удовлетворённость клиента поездкой. Коэффициент $$$\alpha$$$ вычисляется по формуле:

$$$$$$\alpha = \frac{10^7 - min(d_1^2 + d_2^2, 10^7)}{10^7}\text{,}$$$$$$

где $$$d_1$$$ — время ожидания посадки (то есть количество тиков между временем заказа и посадкой), а $$$d_2$$$ — разность между фактической длительностью поездки и идеальной длительностью (идеальная длительность равна $$$w_0$$$). Если заказ не выполнен, то $$$\alpha = 0$$$.

Количество баллов, которое суммарно получит ваше решение — это просто сумма баллов за все тесты.

Входные данные

В первой строке входных данных содержатся целые числа $$$w$$$ и $$$h$$$ ($$$300 \le w, h \le 3000$$$) — размеры прямоугольного города. Вторая строка содержит целое число $$$k$$$ ($$$1 \le k \le 40$$$) — количество машин такси. В следующих $$$k$$$ строках содержатся целые числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le w$$$, $$$1 \le y_i \le h$$$) — начальные координаты машин. Помните, что на одном и том же перекрёстке одновременно может находиться любое число машин.

После прочтения этих данных ваша программа должна вывести набор инструкций для машин (смотрите формат вывода) и после этого обрабатывать заказы.

Каждый заказ записан в отдельной строке в виде пятёрки целых чисел $$$t_j$$$, $$$sx_j$$$, $$$sy_j$$$, $$$tx_j$$$, $$$ty_j$$$ ($$$1 \le t_j \le 86\,400$$$, $$$1 \le sx_j, tx_j \le w$$$, $$$1 \le sy_j, ty_j \le h$$$), где $$$t_j$$$ — момент совершения заказа, $$$(sx_j, sy_j)$$$ — место посадки пассажира, а $$$(tx_j, ty_j)$$$ — место высадки пассажира. Заказы заданы в порядке строгого возрастания $$$t_j$$$. В каждом заказе место посадки и место высадки различаются.

После всех заказов следует строка, содержащая пять чисел, равных $$$-1$$$. Иными словами, если после чтения очередного заказа $$$t_j = -1$$$, то заказы закончены. Гарантируется, что входные данные содержат от $$$1$$$ до $$$500$$$ заказов.

После чтения каждого заказа выведите набор инструкций для машин. Кроме этого, необходимо вывести набор инструкций после чтения строки из пяти чисел $$$-1$$$. Таким образом, если всего данные содержат $$$q$$$ заказов, то суммарно программа должна вывести набор инструкций для машин ровно $$$q + 2$$$ раза (начальный, после каждого заказа, заключительный).

Помните, что симуляция устроена таким образом, что при обработке заказа сначала выполняются инструкции до момента этого заказа, затем вашей программе подаётся информация о новом заказе, а после этого вы выводите новые наборы инструкций для некоторых машин. Если у машины был набор инструкций, то выведенный новый набор полностью заменяет старый. Те машины, которым не пришли новые наборы инструкций, действуют дальше по старым инструкциям.

Во время основной части раунда ваше решение будет тестироваться на предварительном наборе из 40 тестов. Половина этих тестов (тесты с нечётными номерами) доступна для скачивания и анализа по ссылке https://assets.codeforces.com/rounds/927/tests.zip. Среди опубликованных тестов есть примеры работы всех способов жюри генерации тестов.

После раунда для каждого участника или команды будет выбрано последнее решение, которое набрало положительный балл на предварительных тестах. Все остальные решения будут проигнорированы. Все выбранные решения будут перетестированы на секретном наборе тестов, который гарантированно получен тем же способом (набором генераторов), что и предварительный. Жюри постарается сохранить типаж тестов и сильно не менять типовые статистические характеристики.

Выходные данные

В качестве выходных данных программа должна выводить наборы инструкций для машин. Внимательно прочтите описание задачи и формат входных данных для понимания процесса симуляции. Каждый из $$$q + 2$$$ наборов инструкций следует выводить в отдельной строке в виде последовательности целых чисел.

Набор инструкций начинается с целого числа $$$f$$$ ($$$0 \le f \le k$$$) — количества машин, для которых передаются инструкции. Далее следуют $$$f$$$ блоков, разделённых пробелами.

Каждый блок соответствует набору инструкций для одной машины. Блок начинается с пары целых чисел $$$c$$$ и $$$m$$$ ($$$1 \le c \le k$$$) — номера машины для набора инструкций и длины этого набора. Далее следует $$$m$$$ инструкций — троек целых чисел вида $$$cx, cy, a$$$ ($$$1 \le cx \le w$$$, $$$1 \le cy \le h$$$, $$$-q \le a \le q$$$), которая означает, что машина должна доехать до перекрёстка $$$(cx, cy)$$$ и совершить действие $$$a$$$ (читайте основную часть условия задачи). Здесь $$$q$$$ обозначает количество заказов, полученных к этому моменту.

Суммарное количество инструкций по всем машинам суммарно во всех наборах не должно превышать $$$10^6$$$.

После вывода очередного сообщения обязательно очистите буфер вывода, чтобы часть вашего вывода не осталась в этом буфере. Например, на С++ можно использовать функцию fflush(stdout), на Java вызывать System.out.flush(), на Pascal — flush(output), а на Python — stdout.flush().