First Round SOI 2018 - Swiss Olympiad in Informatics

Overview

Here you can see, which tasks you have already solved. Don’t let anything stop you from picking a task at the top and getting on it!

We’d happily give you an introduction during one of the workshops.

This contest is over.

Task	Total	Subtask 1	Subtask 2	Subtask 3	Subtask 4
sushi	‒/100	‒/10	‒/30	‒/10	‒/50
wagashi	‒/100	‒/20	‒/30	‒/25	‒/25
cheesepatrol	‒/100	‒/10	‒/20	‒/20	‒/50
hanabi	‒/100	‒/15	‒/15	‒/30	‒/40
mahjong	‒/100	‒/25	‒/25	‒/20	‒/30
samurai	‒/100	‒/100

Sushi

Mouse Stofl was invited to a sushi-restaurant in Tsukuba, Japan, where the IOI takes place this time. To surprise and welcome the Swiss Delegation, he wants to order sushi for all of them. He has already noted the exact amounts he wants to order for each kind of sushi.

But today there is a special offer! If you order a bottle of sake (traditional Japanese rice wine) in combination with a sushi, you get a second sushi for free. Mouse Stofl and his friends are all abstinent. However, they would order sake if they profit from it.

In total, Mouse Stofl orders $N$ pieces of sushi. The price for the $i$ -th piece is $p_i$ Yen. A bottle of sake costs $S$ Yen. The special offer charges the more expensive sushi (and the bottle of sake).

Subtask 1: Happy hour (10 points)

The happy hour has just started. All bottles of sake are free of charge ( $S = 0$ ). Mouse Stofl didn’t hesitate and has already placed a (small) order of exactly two sushi ( $N = 2$ ). Now he wants to know if he has reached the optimal total price or if he could have ordered all the sushi and paid less.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each consisting of two lines. The first line contains the number of pieces of sushi $N$ (always $2$ in this subtas) ordered by Stofl and the price for the bottle of sake $S$ (always $0$ in this subtas). The second line contains $N$ numbers $p_i$ , each representing the price for the $i$ -th piece of sushi.

Output

For the $i$ -th test case, print out a single line “Case #i: P”, where $P$ denotes the smallest possible total price for the respective order.

Limits

The number of test cases: $1 \le T \le 100$
The number of ordered sushi pieces: $N = 2$
The price for a bottle of sake: $S = 0$
The price of the $i$ -th sushi piece: $1 \le p_i \le 10^{3}$

Sample

Input:

Output:

Case #0: 42
Case #1: 100

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2: More Sushi (30 points)

Because of the excellent and unique taste, Stofl wants to make a second order. First he wants to determine the optimal price for his order, but he has to act fast — the happy hour is soon over…

Input/output

Same as in subtask 1.

Limits

The number of test cases: $1 \le T \le 100$
The number of ordered sushi pieces: $1 \le N \le 10^{3}$
The price for a bottle of sake: $S = 0$
The price for the $i$ -th sushi piece: $1 \le p_i \le 10^{3}$

Sample

Input:

1
6 0
16 42 42 42 16 42

Output:

Case #0: 100

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 3: The happy hour is over (10 points)

Unfortunately, the happy hour is now over and mouse Stofl wants to order some more sushi ( $N=2$ ).

Input/output

Same as in subtask 1.

Limits

The number of test cases: $1 \le T \le 100$
The number of ordered sushi pieces: $N = 2$
The price for a bottle of sake: $0 \le S \le 10^{3}$
The price for the $i$ -th piece of sushi: $1 \le p_i \le 10^{3}$

Sample

Input:

1
2 32
16 42

Output:

Case #0: 58

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4: Multiple delegations (50 points)

Some more IOI-delegations have just arrived at the restaurant. Mouse Stofl would therefore like to place a (large) order for everyone. Can you help him to determine the price again?

Input/output

Same as in subtask 1.

Limits

The number of test cases: $1 \le T \le 100$
The number of ordered sushi pieces: $1 \le N \le 10^{4}$
The price for a bottle of sake: $0 \le S \le 10^{5}$
The price for the $i$ -th piece of sushi: $1 \le p_i \le 10^{5}$

Sample

Input:

1
6 32
16 42 42 42 16 42

Output:

Case #0: 180

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Wagashi

To additionally motivate the participants for their preparation for the IOI Stofl promises a wagashi (traditional Japanese candy) for each solved task. Every participant who solved the $i$ -th task gets a wagashi of type $i$ as reward.

The participants want to earn as many wagashi as possible and unexpectedly solve many tasks. Stofl is now worried that the SOI budget cannot cover all the expenses for the wagashi.

Stofl would therefore like to know how much the wagashi cost in total. Because Stofl likes the wagashi, it does not bother him buying too many wagashi if he can reduce the overall cost.

Subtask 1: Order single wagashi (20 points)

Stofl knows for each task how many participants have solved it. So he visits the local wagashi store to inspect their prices. He asks himself if he can order the wagashi there without exceeding the budget. Calculate the lowest amount $C$ , such that Stofl can buy sufficiently many wagashi for $C$ Yen.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow in the following format: The first line contains $N$ , the number of solved tasks. On the second line follow $N$ numbers $a_i$ – representing the number of mice who have solved the $i$ -th task. The third line contains $N$ numbers $c_i$ – the price for the $i$ -th wagashi in Yen.

Output

For the $i$ -th test case print a single line “Case #i: C”, where $C$ are the total costs in Yen.

Limits

$T \le 100$
$1 \le N \le 1\,000$
$1 \le a_i \le 1\,000$
$1 \le c_i \le 1\,000$

Sample

Input:

Output:

Case #0: 23
Case #1: 117
Case #2: 1

Comment:

First test case: Stofl pays

7

Yen for the

3

first wagashi, and for the single second wagashi

2

Yen. This adds up to a total of

23

Yen.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2: The wagashi package (30 points)

Because the wagashi expenses exceed the SOI budget by far, Stofl asked for a price reduction and got offered the wagashi package. The package costs $K$ Yen and contains $p_i$ wagashi of the $i$ -th type. The package can also be bought more than once. Calculate the lowest amount $C$ , such that Stofl can buy sufficiently many wagashi for $C$ Yen.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow in the following format: The first line contains $N$ , the number of solved tasks and $K$ the price for the wagashi package. On the second line follow $N$ integers $a_i$ – representing the number of mice who have solved the $i$ -th task. The third line contains $N$ numbers $c_i$ – the $i$ -th wagashi costs $c_i$ Yen, followed by the fourth line which contains $N$ numbers $p_i$ – the wagashi package contains $p_i$ wagashi of the $i$ -th type.

Output

Same as in subtask 1.

Limits

$T \le 100$
$1 \le N \le 1\,000$
$1 \le K \le 10^{9}$
$1 \le a_i \le 1\,000$
$1 \le c_i \le 10^{9}$
$1 \le p_i \le 1\,000$

Sample

Input:

Output:

Case #0: 11
Case #1: 16

Comment:

First test case: Stofl orders

2

wagashi packages for

5

Yen each. Additionally he buys a single wagashi of the first type. The fourth wagashi that isn’t needed, Stofl can eat himself. Second test case: The wagashi package is overpriced, so Stofl buys the wagashi as single items.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 3: Ordering wagashi from relatives (25 points)

Because the participants are extremely pleased with the wagashi rewards, Stofl plans to hand out wagashi for each solved task at an even bigger trainings event. To reduce costs he orders wagashi from his Japanese relatives. This way he only has to pay the fees for transport, which is independent of the wagashi type. The possibility to buy wagashi packages remains. Stofl wants to know how much money he needs for the wagashi. Calculate the lowest amount $C$ , such that Stofl can buy sufficiently many wagashi for $C$ Yen.

Input

Same as in subtask 2.

Output

Same as in subtask 1 and 2.

Limits

$T \le 100$
$1 \le N \le 5\cdot 10^{5}$
$1 \le K \le 10^{9}$
$1 \le a_i \le 10^{7}$
$1 \le c_i \le 10^{5}$
All $c_i$ are equal.
$1 \le p_i \le 10^{7}$

Sample

Input:

Output:

Case #0: 50

Comment:

Stofl orders

2

wagashi packages,

3

wagashi of the first type and

5

wagashi of the fourth type.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4: Many wagashi with different prices (25 points)

Stofl’s relatives weren’t as excited by the Idea to produce this many wagashis as Stofl was. Therefore he is back to buying wagashi at the store for different prices. There isn’t much time left till the meeting (at which the budget will be determined) takes place. Calculate the lowest amount $C$ , such that Stofl can buy sufficiently many wagashi for $C$ Yen.

Input

Same as in subtasks 2 and 3.

Output

Same as in subtasks 1, 2 and 3.

Limits

$T \le 100$
$1 \le N \le 5 \cdot 10^{5}$
$1 \le K \le 10^{9}$
$1 \le a_i \le 10^{7}$
$1 \le c_i \le 10^{5}$
$1 \le p_i \le 10^{7}$

Sample

Input:

Output:

Case #0: 74
Case #1: 189

Comment:

First test case: Stofl orders

2

wagashi packages. Second test case: Stofl orders

4

wagashi packages.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Cheese Patrol

Mouse Stofl exports cheese to Japan, where he can sell it for profit. However, recently his revenue in Tōkyo has decreased. Stofl thinks that someone is trading cheese in the streets. To solve this problem, he wants to hire private investigators.

Tōkyo consists of $m$ streets and $n$ intersections. The $i$ -th street connects intersections $a_i$ and $b_i$ . Two intersections are never connected by two streets and every street connects two different intersections. A private investigator can either stand along a street and oversee it, or he can stand at an intersection and look at two streets at that intersection, one with each eye.

Mouse Stofl now wants that each street is under surveillance from at least one private investigator, and wants to hire as few investigators as possible. Help Stofl to determine the minimal number of investigators and how to place them!

In Subtasks 1-3:

Input

The first line contains the number of test cases $T$ .

$T$ test cases follow, each in the following format: The first line of each test case contains two numbers $n$ , the number of intersections, and $m$ , the number of streets. $m$ lines follow, each containing two numbers $a_i$ and $b_i$ , the intersections connected by the $i$ -th street.

Output

For each test case, output a line “Case #t: p” where $p$ is the number of investigators Stofl needs to hire. $p$ lines follow, each containing one or two numbers, the number(s) of the street(s) the $i$ -th investigator should guard.

Limits

For all test cases: $T=100$ , $0 \le m \le (n)(n-1)/2$ and $0 \le a_i, b_i < n$ ( $0 \le i < m$ )
In subtasks 1 and 2: $0 \le n \le 10^{3}$
In subtask 3: $0 \le n \le 10^{2}$

Subtask 1 (10 Points)

At first, Stofl only wants to have the streets of Shibuya, a part of Tōkyo, guarded. Shibuya consists of one big intersection in front of the train station and some streets leading away from that intersection. Shibuya is called a star in graph theory.

Write a program, that determines an optimal placement of investigators.

Input:

Output:

Case #0: 2
0 1
2

Comment:

The intersection

0

is the center of the star and each other intersection is connected exactly to it.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2 (20 Points)

Now Stofl wants to investigate the Edogawa district. The municipality of Tōkyo has decided to measure traffic in Edogawa. For this, some streets were blocked, such that there is exactly one possible path between any two points in Edogawa.

Write a program, that places the investigators in Edogawa. Take note that blocked streets don’t show up in the input.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 3 (20 Points)

After nothing was found in Shibuya and Edogawa, Stofl wants to have the entirety of Tōkyo under surveillance. Tōkyo is large and complicated, additionally, the government decided to make artificial islands that are only accessible by boat or subway, namely the graph describing Tōkyo needs no longer be in one piece.

Once again write a program placing the detectives.

Input:

Output:

Case #0: 4
6 4
2 5
1 3
0
Case #1: 3
0
1
2

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4 (50 Points)

Describe the idea of you solution and argue why your solutions of subtasks 1-3 are correct. For each subtask, the reasoning gives as many points as the original subtask. Since a solution of a subtasks also solves the previous subtasks, it suffices to argue about the solution of the most difficult subtask, i.e. if you prove correctness of your solution for subtask 3, you get 50 points.

The contest is over, you can no longer submit.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Hanabi

For the summer Mouse Stofl is planning a holiday trip to Japan. Stofl is very fond of fireworks (called “hanabi” in Japanese). In Japan, there are frequent, and truly magnificent, displays of fireworks. Stofl would like to plan his trip so that he can see as many of them as possible!

For purposes of this task Japan consists of $n$ cities that are numbered from $0$ to $n-1$ . The cities are connected by $m$ bidirectional roads. For each road you are given the time it takes to travel between the two cities it connects (in either direction). You may assume that the road network is connected – i.e., one can travel between any pair of cities by using a suitable sequence of roads.

Furthermore you are given a list of all $k$ fireworks displays that will take place in Japan. For each of them you are given the city where it takes place, the timestamp of its start and its duration. The fireworks are numbered from $0$ to $k-1$ .

In order to see a fireworks display, Stofl has to be in the city during its entire duration. He cannot arrive later than the start and he cannot leave before the end of the fireworks. (He may arrive and leave at the exact moment when the fireworks start/end.)

Your task is to find a travel plan for Stofl that maximizes the number of fireworks he will see. The travel plan may start and end anywhere in Japan at any time.

Subtask 1: Two cities (15 points)

In this subtask you may assume that $n = 2$ and $k \le 100$ .

Input

All subtasks use the same input format.

The first line of the input contains a single integer $t$ ( $1 \le t \le 100$ ) – the number of test cases which follow.

Each test case starts with a line containing the three integers $n$ , $m$ , and $k$ ( $n \ge 2$ , $m \ge n-1$ , $k \ge 1$ ).

The second line of each test case contains a single integer $g$ that is either $0$ or $1$ : the level of detail required in the output.

Then $m$ lines describing the roads in Japan follow. The $i$ -th of these $m$ lines contains a triple of integers $a_i$ , $b_i$ and $t_i$ ( $0 \le a_i, b_i \le n-1$ , $t_i > 0$ ) – the two cities that the $i$ -th road connects and the time one needs to travel between the two cities.

You may assume that for each road we have $a_i \neq b_i$ , and that all unordered pairs $(a_i,b_i)$ are distinct. In words: each road connects two distinct cities, and each pair of cities is connected by at most one direct road.

In the following $k$ lines the description of the fireworks follows. The line $j$ of these $k$ lines contains a triple of integers $c_j$ , $s_j$ and $d_j$ – the city in which the firework takes place ( $0 \le c_j \le n-1$ ), the timestamp of the moment when the fireworks start ( $s_j \ge 0$ ) and their duration ( $d_j > 0$ ).

If there are multiple fireworks in the same city, they never overlap: one of them will always begin strictly after the other one ends.

The descriptions of fireworks are not given in any particular order.

You may assume that all input numbers fit into 32-bit signed integer.

Output

For each test case there should be one line of output if $g = 0$ or two lines of output if $g = 1$ .

The first line of output should contain the string “Case #i: h” where $i$ is the number of the test case (0-based in increasing order) and $h$ is the maximum number of fireworks Stofl can see.

If the input has $g = 1$ , the second line of output should contain one optimal travel plan. More precisely, you should output $h$ space-separated integers $f_{1}, {\dots}, f_h$ : one possible list of $h$ fireworks displays such that Stofl can see all of them, in the given order.

Input:

Output:

Case #0: 4
0 1 4 3

Comment:

Note that in the output we list the numbers of the fireworks Stofl will see.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2: Two fireworks (15 points)

In this subtask you may assume that $n \le 100$ , $k = 2$ , and $g = 1$ . Additionally, you may assume that the two fireworks take place in two different cities.

Input

Same as in subtask 1.

Output

As we always have $g = 1$ , in this subtask you should produce exactly two lines of output for each test case. However, the output format is not the same as in Subtask 1.

As in all subtasks, your task is to maximize the number of fireworks Stofl gets to see. However, this time we want you to tell him how he should travel to do so.

The first line of output should always contain the string “Case #i: l” where $i$ is the number of the test case (0-based in increasing order) and $l \le 100$ is the number of cities Stofl should visit in order to see as many fireworks as possible. The second line of output should contain one optimal travel plan: $l$ space-separated integers $c_{1}, {\dots}, c_l$ – one possible sequence of cities Stofl should visit, in order.

There are two possibilities:

If Stofl can only see one fireworks display, your output should have $l = 1$ and $c_{1}$ should be one of the two cities that have fireworks.
If Stofl can see both fireworks displays, $c_{1}$ should be the city with the earlier and $c_l$ the city with the later fireworks display. Additionally, the sequence of cities should be such that if Stofl watches the first fireworks and then travels through the given cities in the given order, he will arrive to $c_l$ in time for the second fireworks.

Note that if Stofl can see both fireworks, you do not have to optimize the value $l$ . You also do not have to optimize the total time Stofl spends on the road. If there are multiple solutions, you may output any of them.

Input:

Output:

Case #0: 4
0 1 3 4

Comment:

Note that in the output we list the cities Stofl should visit.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 3: Sparse fireworks (30 points)

In this subtask you may assume that $n \le 500$ and that in each city there is at most one fireworks display.

Input

Same as in subtask 1 and 2.

Output

The same as in Subtask 1.

Note: Generating the input file and verifying your answer takes around 10 seconds.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4: Many fireworks (40 points)

This is a theoretical task. Assume that in each city there can be multiple fireworks which don’t overlap but their number can be significantly higher than the number of cities (e.g., $k \le 100\,000$ ).

Try to find as fast as possible algorithm solving such instances. Describe the idea of your solution and argue why it is correct and what would be its time and space complexity. To score many points it is expected that your solution will be detailed enough to allow a straightforward implementation or it will contain a (pseudo) code solving it. Attach explanation what the (pseudo) code does is necessary, too.

Input

You can assume that input would be given in the same format as in Subtask 1, 2 and 3.

Output

You can assume that the output is in the same format as in Subtask 1 and 3.

The contest is over, you can no longer submit.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Mahjong

One of the most popular parlor games in Japan is Japanese mahjong, a tile-based game.

This task is about a single-player game, which can be played with Mahjong tiles.

Specifically, there are $N$ tiles, for convenience numbered $0$ to $N-1$ , as well as three piles. Each pile consists of an arbitrary amount of tiles lying one on another (possibly, the pile is empty, then it consists of 0 tiles). Initially, all tiles are distributed among the piles.

The following is a possible arrangement for $N=6$ :

|0| | |
|5| |4|
|2|1|3|
+-+-+-+

On the first pile lie 3 tiles; $0$ at the top, $5$ in the middle and $2$ at the bottom. The second pile consists of one single tile, the $1$ , and the last pile has $4$ at the top and $3$ at the bottom.

Another possibility for $N=3$ is displayed here:

| | | |
|2| | |
|0| |1|
+-+-+-+

Here, the second pile would be empty.

There is only one type of allowed moves: You can put the topmost tile of a non-empty pile on top of an arbitrary different pile.

This is an allowed move, which removes the 1 and puts it on top of the first pile:

| | | |      |1| | |
|2| | |  =>  |2| | |
|0| |1|      |0| | |
+-+-+-+      +-+-+-+

But this isn’t, because the 2 was inserted at the bottom of the third pile, instead of laying it on top:

| | | |      | | | |
|2| | |  =>  | | |1|
|0| |1|      |0| |2|
+-+-+-+      +-+-+-+

The goal is to have all tiles lying sorted on one of the piles, by repeatedly doing these moves. For $N=4$ , this is precisely achieved in any of the following arrangements:

|0| | |      | |0| |     | | |0|
|1| | |      | |1| |     | | |1|
|2| | |      | |2| |     | | |2|
|3| | |      | |3| |     | | |3|
+-+-+-+      +-+-+-+     +-+-+-+

These are also all possible arrangements for $N=4$ . Here, sorted means that the $0$ must be at the top and the biggest tile at the bottom.

Subtask 1 (25 points)

Given an arrangement of the $n$ tiles, output one possible sequence of moves, to change it into one of the three end positions.

Note, that the sequence of moves calculated by you doesn’t have to be the shortest possible. However, we allow at most $100,000$ moves, so that the output doesn’t get too big, and guarantee that it is always possible with less than $100,000$ moves.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow in the following format:

The first line of the test case contains $N$ , the number of tiles. A second line follows with $A$ , the number of tiles on the first pile, followed by $A$ number values $a_{0},{\dots},a_{A-1}$ , the values on the first pile. The third line works the same way, $B$ is first, then $B$ number values $b_{0},{\dots},b_{B-1}$ with the values of the second pile. The fourth line contains $C$ , followed by $C$ number values $c_{0},{\dots},c_{C-1}$ .

The tiles $a_{0}$ , $b_{0}$ and $c_{0}$ are the topmost tiles respectively, the tiles $a_{A-1}$ , $b_{B-1}$ and $c_{C-1}$ the bottommost.

Note that $A$ , $B$ and/or $C$ can also be $0$ , which means the pile is empty. In this case the pile does not have a lowest and topmost tile.

It is guaranteed that $A+B+C=N$ , and that all $0\le a_i,b_i,c_i<N$ are different.

Output

For the $i$ -th test case, output a line “Case #i: M”, where $M$ is the number of moves, which you need for your solution. $M$ lines should follow, each with the two numbers $s$ and $t$ , which means, that the topmost tile from pile number $s$ is laid on top of pile number $t$ .

Limits

There are $T=100$ test cases. In every test case, $3 \le N \le 100$ .

For the output, $M\le 100\,000$ .

Example

Input:

Output:

Case #0: 3
0 1
0 1
0 1
Case #1: 10
1 0
1 0
1 2
0 2
0 2
0 1
0 1
0 2
1 2
1 2

Comment:

Case #0: All tiles lie on pile number 0 in reverse order (2 at the top, 1 in the middle and 0 at the bottom). To reverse the order, we put them one by one on pile 1. The piles change like this:

start: |2 1 0| || || →\to→
0->1:  |1 0|  |2| ||  →\to→
0->1:  |0|  |1 2| ||  →\to→
0->1:  || |0 1 2| ||.

Case #1: Here, 9 tiles are distributed on the piles. The algorithm of the output changes them as follows:

start: |0 1 2|  |3 4 5|  |6 7 8| →\to→
1->0:  |3 0 1 2|  |4 5|  |6 7 8| →\to→
1->0:  |4 3 0 1 2|  |5|  |6 7 8| →\to→
1->2:  |4 3 0 1 2| ||  |5 6 7 8| →\to→
0->2:  |3 0 1 2| ||  |4 5 6 7 8| →\to→
0->2:  |0 1 2| ||  |3 4 5 6 7 8| →\to→
0->1:  |1 2|  |0|  |3 4 5 6 7 8| →\to→
0->1:  |2|  |1 0|  |3 4 5 6 7 8| →\to→
0->2:  ||  |1 0| |2 3 4 5 6 7 8| →\to→
1->2:  ||  |0| |1 2 3 4 5 6 7 8| →\to→
1->2:  || || |0 1 2 3 4 5 6 7 8|.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2 (25 points)

Because the game is always too complicated for some, you want to create instructions for solving it. The instructions are a table, which recommends a move for each possible arrangement (apart from the end position).

It should be possible with your instructions to transform every arrangement into the end position, by applying your recommended move, arriving at a new arrangement and looking up a new move for it. This step is repeated until an end position is reached.

In your instructions it should be guaranteed that an end position is reached after a finite number of steps. In other words, one should not get stuck in an infinite loop.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow with just the single number $N$ .

The input, which you can download here, is always the same: $T=6$ and $1 \le N \le 6$ . In the input, every $N$ from $1$ up to and including $6$ appear sorted increasingly.

Output

Multiple lines in this format:

$a_{0}$ $a_{1}$ $\dots$ $a_{i-1}$ | $a_i$ $\dots$ $a_{j-1}$ | $a_j$ $\dots$ $a_{n-1}$ : $b$ -> $c$ , if in this case you would like to put the topmost tile from pile $b$ on top of pile $c$ , or
$a_{0}$ $a_{1}$ $\dots$ $a_{i-1}$ | $a_i$ $\dots$ $a_{j-1}$ | $a_j$ $\dots$ $a_{n-1}$ : done, if the game is already finished (i.e. exactly when all tiles lie on one pile which is sorted).

All arrangements must be different, and all possible arrangements must appear. There are $(N+2)!/2$ different arrangements (The exclamation mark means factorial, in short $(N+2)! =1\cdot 2\cdot 3\cdot 4\cdot \ldots \cdot (N-1)\cdot N\cdot (N+1)\cdot (N+2)$ ).

Limits

$T=6$ and $1 \le N \le 6$ . In the input, every $N$ from $1$ up to and including $6$ appear sorted increasingly.

Example

Input:

2
1
2

Output:

Case #0:
0 | |: done
| 0 |: done
| | 0: done
Case #1:
0 1 | |: done
| 0 1 |: done
| | 0 1: done
1 0 | |: 0 -> 1
| 1 0 |: 1 -> 2
| | 1 0: 2 -> 0
0 | 1 |: 0 -> 1
| 0 | 1: 1 -> 2
1 | | 0: 2 -> 0
1 | 0 |: 1 -> 0
| 1 | 0: 2 -> 1
0 | | 1: 0 -> 2

Comment:

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 3 (20 points)

There is an even harder variant of the game: You don’t know the complete arrangement of a pile, but just the value of the topmost tile. (If the pile is empty, then you know that it is empty.) Also, you don’t know how high the pile is.

Again, create instructions like in the previous subtask.

Because you cannot know when the game is finished with this information, the game is ended automatically, as soon as all tiles are on one pile and this pile is sorted.

If e.g. at $N=3$ only one pile is non-empty, and it has a $0$ at the top, then you know that the pile is in the order “0 2 1”, because with the order “0 1 2” the game would have ended already.

In this subtask you can also score partial points: If you only solve 3 testcases, you get 5 points. Any additional testcase gives you 5 more points, until a maximum of 15 points. For 20 points, you need to solve all test cases correctly.

Input

Same as in subtask 2, only with $T=8$ instead of $T=6$ . In particular, here too you know the input in advance.

Output

Same as in subtask 2, except that you describe the pile differently: An arrangement consists of only 3 “numbers”, where in case of an empty pile the “number” can also be “-“. (Instead of “-”, the grader also accepts “-1”.)

Some arrangements now fall together, there remain exactly $3N+3N\cdot(N-1)+N\cdot(N-1)\cdot(N-2)$ different arrangements.

Example

Input:

2
1
2

Output:

Case #0:
0 - -: 0 -> 1
- 0 -: 0 -> 1
- - 0: 0 -> 1
Case #1:
0 - -: 0 -> 1
- 0 -: 0 -> 1
- - 0: 0 -> 1
1 - -: 0 -> 1
- 1 -: 1 -> 2
- - 1: 2 -> 0
0 1 -: 0 -> 1
- 0 1: 1 -> 2
1 - 0: 2 -> 0
1 0 -: 1 -> 0
- 1 0: 2 -> 1
0 - 1: 0 -> 2

Comment:

Note, that in the first test case the game is always finished anyway. The move is therefore never applied.

In the second test case too, the game has already ended, when only a $0$ is visible.

These are special cases for $N\le 2$ . For $N>2$ however this special case does not appear anymore; then there would be a valid arrangement like e.g. 0 3 1 4 2.

Limits

$T=8$ and $1 \le N \le 8$ .

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

Download input again

You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

Problem with newlines?

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4 (30 points)

Same as subtask 3, except that this is a theoretical task.

Write a function $f(n,a,b,c)$ , which for $n$ tiles takes the three topmost numbers $a$ , $b$ , $c$ of the piles (empty piles are encoded as $-1$ ) and returns either 01, 10, 12, 21, 02 or 20 (for $0\to 1$ , $1\to 0$ , $1\to 2$ , etc.).

Because the output isn’t that big anymore this time, and not all inputs are calculated anymore, the limits are much bigger this time in contrast to subtask 4. Thus, you should optimize the asymptotic time complexity of $f$ in dependence on $n$ .

Because this is a theoretical task, you should reason why your solution is correct and what asymptotic time complexity your solution has. You can write this function in an arbitrary programming language or in pseudo code.

The contest is over, you can no longer submit.

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Samurai

Stofl is fascinated by Japan’s culture and history. He is especially interested in samurais. He and his friends decided to learn some skills the samurais had. To make it even more fun they came up with a game which helps them learn the skills faster.

There are $n$ mice playing the game and $m$ skills to learn. The skills have different difficulties: the $i$ -th skill takes $s_i$ days of practice to master.

At the start of the game one player chooses a target skill $t$ . Each day every mouse chooses one of the $m$ skills they want to practice that day. As soon as the first mouse completed the target skill, it gets one point and can choose a new target skill. This goes on until the last skill is mastered by someone. The mouse with the most points wins the game.

Should several mice complete the skill on the same day, the point will be split equally between them and the winning mouse with the next higher index than the mouse that previously chose the target can choose the new skill (wrapped around at zero).

A mouse can practice any skill, not just the target skill (otherwise there wouldn’t be much of a game and every one would get the same number of points). But it is not allowed to finish mastering a skill if it is not the target skill (i.e. there has to be at least one day of practice left). Note that always going for the target skill might not be the optimal strategy.

There will be several runs of the game without restarting your program. This allows you to analyze the other programs and develop a counter strategy (if you want to. You can also treat each game separately).

Protocol

The communication between program and server is handled using Stdin / Stdout.

At the start the program receives general information about the game:

One line with $n m$ , the number of mice $n$ and the number of skills $m$ . Your player is always the mouse with index 0. On the next line there are $m$ space separated integers $s_i$ , the difficulty of the $i$ -th skill.

Now the game starts. For each round (or day) you first get the moves of all players and then you should output your next move:

On the first line there is one integer $t$ , the current target skill. If $t$ is below zero there is a special meaning (see below). On the next line there are $n$ space separated integers $p_i$ , the skill the $i$ -th player chose to practice. $p_{0}$ will be the skill you chose in the last round. Then you have to print one line with $r$ , the skill you want to practice.

Please note that in the first round of the game there is no previous round and thence no skills the other players chose. All $p_i$ will be $-1$ .

There are some special values for $t$ and the protocol changes accordingly.

$t = -1$ means that you can choose the next target skill. The next line is the same as for a normal round. You then have to print two lines, the first with $t$ , the new target skill, and the second with the skill you want to practice this round.

$t = -2$ means that the game has been reset and a new game will start. All the game parameters are the same (i.e. $n$ , $m$ , $s_i$ ) but the skill levels of all players are set to zero for all skills. The next line is the same as for a normal round (so that you know what the others did) but you don’t have to print anything. The next input will be a new game starting again with the game parameters $n m$ and $s_i$ .

$t = -3$ means that the evaluation is over. Your program should exit.

Limits

$2 \le n \le 100$

$2 \le m \le 1000$

$1 \le s_i \le 1000$

$0 \le p_i < m$

$-3 \le t < m$

Sample

> : 3 10
> : 5 8 10 2 6 4 1 9 7 3
> : -1
> : -1 -1 -1
< : 8
< : 0
> : 8
> : 0 3 8
< : 0
[...]
> : 8
> : 5 5 8
< : 2
> : -1
> : 2 0 8
< : 3
< : 4
> : 1
> : 4 3 3
< : 5
[...]
> : 4
> : 7 9 9
< : 7
> : -2
> : 4 7 4
> : 3 10
> : 5 8 10 2 6 4 1 9 7 3
> : 9
> : -1 -1 -1
< : 5
> : 9
> : 5 3 9
< : 0
[...]
> : 7
> : 7 7 7
< : 2
> : -3

Subtask 1: play by the rules (25 points)

Write a bot that follows the rules and can beat the example bot.

Subtask 2: creativity tournament (75 points)

You play against the other participants of the SOI. At SOI-Day the programs will compete in a tournament to determine the best one. You are allowed to submit up to three programs. Your best program will be used for the ranking. Bundle them in a zip archive when submitting.

The contest is over, you can no longer submit.

Hints

It is important for interactive tasks to flush the output buffer after every turn to make sure the server can see your output.

Use the following commands:

C/C++: fflush(stdout);
C++: cout << flush; (not necessary if you read afterwards)
Pascal: flush(output);
There are similar commands in other languages.

Furthermore it is important that you don’t wait for more characters than the server gives you as an input. For example spaces or line endings in C format strings are a common source for errors. For example if you read the last variable in the input with “scanf("%d ", &x);” it will wait for the next character that is not a space or a line break. You will receive such a character only after you printed your next turn. To solve this use “scanf("%d", &x);” instead (no non-printable characters after the “%d”).

Sample bots, server and visualization

During the first round we provide the following material:

Sample bots in different programming languages.

A server program you can use to test your program against your own or other programs.

A visualization to display simulated games.

Some closed source players. Use samurai://soi.ch:9929/name as player command, where name is one of b1, b2, b3, b4, b5.

You can download them here.

Quick start

To run the server you need Java (version 7 or higher). The server program is located in the file samurai.jar and the remaining files are configuration files and sample bots.

If you double click on samurai.jar the game specified in samurai.txt will be simulated with the players specified in players.txt. You can start the server using a console (Windows: cmd, Mac: terminal, Linux: Shell) to be able to pass arguments (java -jar samurai.jar arguments). You can find the available arguments and many more information in the file usage.md.

You can adjust the skill levels in the file samurai.jar. To specify which bots you want to run you enter them in the file players.txt and adjust the number of players at the top of the file.

Use the following commands, depending on the language you used:

Python: python path/to/file

Java: java -jar program.jar or java package.MainClass

Compiled program (e.g. C++): ./path/to/program

Don’t hesitate to ask us any question about this task, programming or the website via email (info@soi.ch).

Ranking

Rank	Username	Total (600)	sushi (100)	wagashi (100)	cheesep… (100) cheesepatrol	hanabi (100)	mahjong (100)	samurai (100)
	loading ...