BuberPool Taxi Optimization

This is an interactive optimization problem. Instead of having to find the best answer, each solution will get score according to its efficiency. As the problem is interactive, during the testing process, the jury program and your solution will exchange messages via standard input and output streams. After printing a message, remember to flush the output buffer to ensure that the message is fully sent. For example, you can use fflush(stdout) in C++, System.out.flush() in Java, flush(output) in Pascal, and stdout.flush() in Python.

Your task is to automate the next generation taxi service, BuberPool. Each Buber car may transport up to four passengers at a time. The cars have to drive to passengers' locations, pick them up and drive them to their destinations. Additionally, unlike a traditional taxi, each car can process up to four orders simultaneously. For example, when driving a passenger to the destination, a car can pick up an additional passenger, or make a detour to drop off another passenger.

We will use the following simplified discrete model for this real-life problem.

Consider a city as a rectangular grid of $$$w$$$ streets and $$$h$$$ avenues with $$$w \times h$$$ crossroads. The streets are numbered from $$$1$$$ to $$$w$$$, and the avenues from $$$1$$$ to $$$h$$$. We will consider non-negative integer moments of time. Actions are performed in ticks: intervals of time between consecutive moments. At any moment, each car is located at some crossroads $$$(x, y)$$$, where $$$1 \le x \le w$$$ and $$$1 \le y \le h$$$. Any number of cars can be at the same crossroads simultaneously. During one tick, each car can either remain on the same crossroads or change exactly one of its coordinates, the street or the avenue, by one.

At moment $$$0$$$, you are given starting locations of $$$k$$$ cars: $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$\ldots$$$, $$$(x_k, y_k)$$$. The number of cars is equal to $$$k$$$ and does not change during the simulation.

Additionally, your solution will be given the clients' orders. In this problem, each order is made by a single passenger, so a car can process up to four orders at the same time. To further simplify the problem, the moments of orders are all distinct, and the orders are given in chronological order. So, each $$$j$$$-th order is described by five integers: the moment $$$t_j$$$, the pick up location $$$(sx_j, sy_j)$$$, and the drop-off location $$$(tx_j, ty_j)$$$.

On tick $$$0$$$, and also right after receiving each order, you can give instruction sets to the car drivers. Each time you can give instruction sets to any number of cars (more on restrictions later). Instruction sets for different cars are given separately. An instruction set is a sequence of triples $$$(cx_1, cy_1, a_1)$$$, $$$(cx_2, cy_2, a_2)$$$, $$$\ldots$$$, $$$(cx_m, cy_m, a_m)$$$, where $$$m$$$ is number of instructions in the set. The meaning of these numbers is as follows:

• A car should first drive to $$$(cx_1, cy_1)$$$, then to $$$(cx_2, cy_2)$$$, $$$\ldots$$$, and at last to $$$(cx_m, cy_m)$$$. Each location $$$(cx_i, cy_i)$$$ may be any crossroads in the city, not necessarily a pickup or drop-off location. While driving from one location to another, a car always first changes its first coordinate until it is equal to the first coordinate of the destination, and only then the second coordinate. This way, while driving from $$$(p_1, q_1)$$$ to $$$(p_2, q_2)$$$, a car will first move $$$(p_1, q_1) \rightarrow (p_2, q_1)$$$, and then $$$(p_2, q_1) \rightarrow (p_2, q_2)$$$. In each tick while moving, a car changes exactly one of its coordinates by one.
• Values $$$a_i$$$ encode actions. If $$$a_i = 0$$$, the car just drives to $$$(cx_i, cy_i)$$$ and doesn't do anything special. If $$$a_i > 0$$$, the car drives to $$$(cx_i, cy_i)$$$ and picks up passenger number $$$a_i$$$ there (the passenger's pickup location should be equal to $$$(cx_i, cy_i)$$$, and the passenger should still be waiting there). If $$$a_i < 0$$$, the car moves to $$$(cx_i, cy_i)$$$ and drops off passenger number $$$-a_i$$$ (the passenger's drop-off location should be equal to $$$(cx_i, cy_i)$$$, and the passenger should be in this car). Picking up and dropping off passengers are instant.

When you give instruction set to a car, its previous instruction set is replaced with the new one. This way, a car only performs at most one instruction set at a time. If there are no instructions, or all of them are completed, the car is waiting at its last location. Instructions are performed in the given order.

For each order, first, all the cars perform their current instruction sets until the moment of the order comes, then the order is given to your program, and after that, your program prints new instruction sets for some of the cars. The cars which don't get new instruction sets continue performing their old ones.

So, the overall testing strategy looks like this:

1. Your solution reads the city dimensions, the number of cars, and their initial coordinates.
2. The solution prints instruction sets for some cars, and the cars start performing the instructions.
3. The solution reads an integer $$$t_j$$$, the moment of the next order (if $$$t_j = -1$$$, your program should print the final instruction sets and exit normally).
4. The solution reads integers $$$sx_j$$$, $$$sy_j$$$, $$$tx_j$$$, $$$ty_j$$$, the pickup and drop-off locations for $$$j$$$-th order.
5. The solution prints the next instruction sets for the cars.
6. Go to step 3.

After your program exits in step 3, first, all instructions will be completely performed, and only after that the simulation will end.

The score your solution gets for a test is the average score for all orders, rounded to the nearest integer. The score for an order equals $$$\alpha \cdot (100 + w_0)$$$, where $$$w_0$$$ is time the order takes in the ideal case, which is just the time to get from $$$(sx_j, sy_j)$$$ to $$$(tx_j, ty_j)$$$ (so, $$$w_0 = |sx_j - tx_j| + |sy_j - ty_j|$$$), and $$$\alpha$$$ is a real value between $$$0$$$ and $$$1$$$ which characterizes the passenger's satisfaction with the ride. The value $$$\alpha$$$ is calculated by the formula:

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

where $$$d_1$$$ is the waiting time before pickup (the number of ticks between the time of the order and pickup time), and $$$d_2$$$ is the difference between actual and ideal travel time (the ideal travel time is $$$w_0$$$). If the order was not completed, $$$\alpha = 0$$$.

The score your solution gets is just the sum of scores for each test.