Это интерактивная оптимизационная задача. В отличие от задач, где нужно получить точный ответ, здесь каждое решение получает баллы в зависимости от эффективности. Интерактивность означает, что при в ходе проверки программа жюри и решение участника обмениваются сообщениями через стандартные потоки ввода и вывода. После вывода очередного сообщения обязательно очистите буфер вывода, чтобы часть вашего вывода не осталась в этом буфере. Например, на С++ можно использовать функцию 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$$$.

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