A. Beutsche Dahn
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an optimization problem. The optimal solution for each test is not known to the jury, and your score for each test will be determined as described below.

The Beutsche Dahn (BD) railway network has always been praised for its... unique approach to punctuality. Specifically, every passenger who has ever managed to board a train has eventually reached their destination. But now the future is upon us — the year is $$$1879$$$, and Beutsche Dahn has just been acquired by White Tree Capital (WTC). They intend to use the railroads to relocate their tradesmen to strike urgent deals, so efficiency is extremely important.

As the newly appointed Efficiency Manager for BD at WTC, your job is to manage the entire train fleet according to exact demand. Since you have the complete list of tradesmen and their appearance times at stations in advance, you can precompute a master routing plan to get every tradesman to their destination as fast as humanly possible, while avoiding train collisions (see below).

Formally, you must minimize:

Where:

  • $$$N$$$ is the total number of tradesmen;
  • $$$T_{\text{appearance}, i}$$$ is the time tick at which the $$$i$$$-th tradesman appears on the platform (provided in the input);
  • $$$T_{\text{arrival}, i}$$$ is the time tick at which the $$$i$$$-th tradesman is dropped off at their destination city $$$v_i$$$;
  • $$$P_i$$$ is the penalty for additional train rides (see below).

Now, we will explain how the entire process is emulated and how arrival times are calculated.

The time is split into ticks, starting with tick $$$1$$$. Each tick is processed in the following sequence:

  1. Tradesmen Appearance: At tick $$$t$$$, all tradesmen with $$$t_i = t$$$ appear at their starting city $$$u_i$$$.
  2. Loading/Unloading: The trains perform pick and drop actions in the order provided in the output. A train and a tradesman must be in the same city for an action to be valid. Each train cannot exceed its maximum capacity $$$C$$$. If the tradesman arrives at their destination city, they disappear.
  3. Movement: Each train $$$j$$$ moves from its current city $$$\text{pos}_j$$$ to the destination city $$$\text{dest}_j$$$ specified in the output. This is only valid if a rail track $$$(\text{pos}_j, \text{dest}_j)$$$ exists. At the beginning of the next tick, the train is considered to be in $$$\text{dest}_j$$$. To avoid train collisions, two trains cannot use the same rail track during the same movement phase, regardless of whether they are moving in the same or in different directions.

Note on transfers: a tradesman does not have to reach their destination in a single ride. They may be dropped off at an intermediate city and picked up by another train. This can even happen within the same tick, provided that the commands are ordered correctly: the drop action must appear before the corresponding pick action in your output. However, due to travel fatigue, a penalty is incurred when multiple train rides are involved. More specifically:

  • If a tradesman reaches their destination in one train ride, $$$P_i = 1$$$.
  • If a tradesman reaches their destination in two train rides, $$$P_i = 1.05$$$.
  • If a tradesman reaches their destination in three train rides, $$$P_i = 1.2$$$.
  • If a tradesman reaches their destination in four train rides, $$$P_i = 1.5$$$.
  • No tradesman will accept a plan involving more than four train rides.
Input

You are given a zip archive "problem-a-inputs.zip" with $$$8$$$ tests: 01, 02, $$$\ldots$$$, 08.

Each test describes the rail network, the train fleet, and the information about tradesmen. All indices are $$$1$$$-based.

The first line contains two integers $$$V$$$ and $$$E$$$ — the number of cities and undirected rail tracks. Each of the next $$$E$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \leq V, u \neq v$$$) — an undirected rail track between cities numbered $$$u$$$ and $$$v$$$. It is guaranteed that all rail tracks are unique; there is no rail track that goes from a city to itself, and any city is reachable from any other city by following a sequence of rail tracks.

The next line contains an integer $$$T$$$ — the number of trains at your disposal.

The next line contains $$$T$$$ integers between $$$1$$$ and $$$V$$$ — the initial city of each train.

The next line contains an integer $$$C$$$ — the maximum capacity of each train.

The next line contains an integer $$$N$$$ — the total number of tradesmen for the scenario.

Each of the next $$$N$$$ lines contains three integers $$$u_i, v_i, t_i$$$ ($$$1 \le u_i, v_i \leq V$$$, $$$u_i \ne v_i$$$, $$$1 \le t_i \le 10^5$$$) — the starting city, the destination city, and appearance time for the $$$i$$$-th tradesman. Additionally, the tradesmen are ordered by their appearance times: for every $$$i \lt N$$$, it is guaranteed that $$$t_{i} \leq t_{i+1}$$$.

Output

Submit a zip archive with files 01.out, 02.out, $$$\ldots$$$, 08.out. Some of the files may be missing.

Each file should be formatted as follows.

The first line should contain an integer $$$S$$$ — the total number of ticks in your plan. This number should not exceed $$$10^6$$$.

For each tick $$$s = 1, 2, \ldots, S$$$, output should contain the following:

  1. An integer $$$K_s$$$ — the number of pick-up and drop-off actions performed at the start of this tick.
  2. $$$K_s$$$ lines, each containing one of the following commands:
    • pick <train_id> <tradesman_id>
    • drop <train_id> <tradesman_id>
  3. An integer $$$M_s$$$ — the number of trains performing a move action at the end of this tick.
  4. $$$M_s$$$ lines, each containing two integers train_id and city_id — the moving train and its next city. All identifiers of the moving trains during one tick must be distinct, and for each of them, the city it is going to must be reachable via a single rail track.

All indices are $$$1$$$-based: $$$1 \le \mathtt{train\_id} \le T$$$, $$$1 \le \mathtt{tradesman\_id} \le N$$$, $$$1 \le \mathtt{city\_id} \le V$$$.

Additionally, to maintain manageable output sizes, the total number of move operations performed, $$$\sum\limits_{s=1}^{S} M_s$$$, must not exceed $$$2 \cdot 10^6$$$. We expect that most solutions would satisfy this restriction without additional optimization.

Scoring

Your number of points is calculated using the formula

where $$$T_{\text{arrival}, i}$$$ and $$$P_i$$$ are calculated using the process described in the statement.

Your final score for the test is calculated as follows:

  • If the output is not properly formatted or is inconsistent, e.g.:
    • a tradesman does not reach their target destination,
    • a train tries to pick up a tradesman who has already reached their destination, or is not present in that city,
    • a train uses a rail track that is already in use during the current tick,
    • a train moves to a city that is not accessible from its current city,
    your score for the test is $$$0$$$, and a comment describing the problematic tick and the reason will be provided.
  • Otherwise, it will be $$$100$$$ times the ratio of the lowest number of points among all participants for this test to the number of points for your output: $$$100 \cdot \frac{\mathtt{best\_points}}{\mathtt{your\_points}}$$$.

Note that the scoreboard will consider your best score for each test among all your submissions.

Example
Input
3 2
1 2
2 3
2
1 1
2
3
1 2 1
1 3 1
1 2 1
Output
3
3
pick 1 1
pick 1 2
pick 2 3
1
1 2
1
drop 1 1
2
1 3
2 2
2
drop 1 2
drop 2 3
0
Note

The sample test illustrates the input and output formats. This test is not part of the graded test set.

In this sample, three cities are connected by two rail tracks in a line. There are two trains in city $$$1$$$, each capable of holding $$$2$$$ tradesmen. Three tradesmen appear in city $$$1$$$ at tick $$$1$$$: tradesmen $$$1$$$ and $$$3$$$ need to get to city $$$2$$$, while tradesman $$$2$$$ needs to get to city $$$3$$$.

In the sample output:

  1. During tick $$$1$$$, tradesmen $$$1$$$ and $$$2$$$ board train $$$1$$$, and tradesman $$$3$$$ boards train $$$2$$$. Then, train $$$1$$$ moves to city $$$2$$$, while train $$$2$$$ cannot move since the track is already in use.
  2. During tick $$$2$$$, tradesman $$$1$$$ gets off the train and arrives. Then, train $$$1$$$ moves to city $$$3$$$, while train $$$2$$$ moves to city $$$2$$$.
  3. During tick $$$3$$$, tradesmen $$$2$$$ and $$$3$$$ both get off their respective trains and arrive.

Thus, the three tradesmen contribute $$$1$$$, $$$2$$$, and $$$2$$$ to the sum under the square root. Hence, the number of points is

Problem by Alber Blanc