Problem E
Express Recipes
Languages
en
sv
You have just subscribed to the EGOI (Express recipes - Good and Overtly Inspiring) service, which regularly sends out recipes to inspire your cooking. This means you will receive $N$ recipes by mail in the coming year.
You have realized that having $N$ recipes lying in an unordered pile often makes it difficult to find a suitable recipe when you’re stressed.
To avoid this problem in the future, you’ve acquired a binder with $2N$ plastic sleeves where you can insert your recipes.
You want to insert the recipes sorted by their cooking time, as it makes it easier to find a suitable dish depending on your level of stress. Since it’s not possible to move the sleeves themselves, you may need to move older recipes to different sleeves when inserting a new recipe. For example, if you’ve previously placed a recipe that takes $7$ minutes to cook immediately after one that takes $5$ minutes, and then you receive a recipe that takes $6$ minutes, you must move at least one of the old recipes to insert the new one.
Even while moving recipes around, they must always remain in the correct order; otherwise, you might get confused and end up with them incorrectly ordered even after inserting the new recipe.
Your goal is now to minimize the total number of recipe movements by strategically placing them in the binder from the beginning.
It is guaranteed that all recipes have distinct cooking times, and it is acceptable if there are empty sleeves between recipes once finished.
Interaction
On the first line, you will read an integer $N$ ($2 \leq N \leq 1000$), the number of recipes you’ll receive this year. The binder always contains $2N$ sleeves.
After this, you will get $N$ recipes. For each recipe you’ll start off by reading an integer $t$ ($1 \leq t \leq 10^9$), the cooking time of the recipe in minutes, and then you must respond with the movements you want to make.
Movements should be provided in the format “$a$ $b$”, meaning you want to move the recipe that takes $a$ minutes to sleeve $b$. The value $a$ must either be the time $t$ or the cooking time of a previously received recipe. The value $b$ must be a number between $0$ and $2N-1$, note that the binder is $0$-indexed. As soon as you specify a movement describing where the recipe that takes $t$ minutes to cook should go, it will be inserted into the binder, after which you should read the cooking time for the next recipe.
Ensure to flush your output after each query, otherwise you may get Time Limit Exceeded. In C++, this can be done using cout << flush; or fflush(stdout);, in Python with sys.stdout.flush(), and in Java with System.out.flush();. The code used to generate the cooking times is deterministic, which means that if you submit the same code several times the cooking times will remain the same. Additionally, the judge may be adaptive, meaning that it can change strategy based on your submission.
To simplify testing your solution, we provide a tool that you can download under “attachments” at the bottom of this problem’s Kattis page. See the comment at the top of the file for instructions on its use.
Scoring
Your solution will be tested on several groups of test cases. To receive points for a group, you must pass all test cases in that group.
Let $Q$ be the maximum number of movements you’re allowed to make.
|
Group |
Points |
Limits |
|
$1$ |
$10$ |
$N = 2, Q = 5$ |
|
$2$ |
$10$ |
$N \leq 10, Q = 1000$ |
|
$3$ |
$20$ |
$N \leq 1000, Q = 1000000$ |
|
$4$ |
$25$ |
$N \leq 1000, Q = 100000$ |
|
$5$ |
$10$ to $35$ |
$N \leq 1000, Q = 50000$ |
Group $5$ uses adaptive scoring. If you use at most $25000$ movements, you get $35$ points. Otherwise, you receive $60 - \lfloor \frac{q}{1000}\rfloor $ points, where $q$ is the number of movements you used.
Explanation of Sample
First, the recipe taking $7$ minutes is placed in sleeve $0$. Then a recipe taking $2$ minutes arrives. Because it must be inserted before the $7$-minute recipe, we move the $7$-minute recipe to sleeve $1$ and place the $2$-minute recipe in sleeve $0$. Next, a recipe taking $12$ minutes arrives, and we place it in sleeve $2$. When a recipe taking $9$ minutes arrives, we must move the $12$-minute recipe to sleeve $3$ and insert the $9$-minute recipe into sleeve $2$. Finally, we receive a recipe taking $18$ minutes, which we can place anywhere at the back of the binder.
| Read | Sample Interaction 1 | Write |
|---|
5 7
7 0
2
7 1 2 0
12
12 2
9
12 3 9 2
18
18 5