First Round SOI 2018

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.

TaskTotalSubtask 1Subtask 2Subtask 3Subtask 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 NN pieces of sushi. The price for the ii-th piece is pip_i Yen. A bottle of sake costs SS 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=0S = 0). Mouse Stofl didn’t hesitate and has already placed a (small) order of exactly two sushi (N=2N = 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 TT. TT test cases follow, each consisting of two lines. The first line contains the number of pieces of sushi NN (always 22 in this subtas) ordered by Stofl and the price for the bottle of sake SS (always 00 in this subtas). The second line contains NN numbers pip_i, each representing the price for the ii-th piece of sushi.

Output

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

Limits

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

Sample

Input:

2
2 0
16 42
2 0
100 64

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.

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.


            

        

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: 1T1001 \le T \le 100
  • The number of ordered sushi pieces: 1N1031 \le N \le 10^{3}
  • The price for a bottle of sake: S=0S = 0
  • The price for the ii-th sushi piece: 1pi1031 \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.

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.


            

        

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=2N=2).

Input/output

Same as in subtask 1.

Limits

  • The number of test cases: 1T1001 \le T \le 100
  • The number of ordered sushi pieces: N=2N = 2
  • The price for a bottle of sake: 0S1030 \le S \le 10^{3}
  • The price for the ii-th piece of sushi: 1pi1031 \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.

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.


            

        

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: 1T1001 \le T \le 100
  • The number of ordered sushi pieces: 1N1041 \le N \le 10^{4}
  • The price for a bottle of sake: 0S1050 \le S \le 10^{5}
  • The price for the ii-th piece of sushi: 1pi1051 \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.

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.


            

        

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 ii-th task gets a wagashi of type ii 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 CC, such that Stofl can buy sufficiently many wagashi for CC Yen.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format: The first line contains NN, the number of solved tasks. On the second line follow NN numbers aia_i – representing the number of mice who have solved the ii-th task. The third line contains NN numbers cic_i – the price for the ii-th wagashi in Yen.

Output

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

Limits

  • T100T \le 100
  • 1N10001 \le N \le 1\,000
  • 1ai10001 \le a_i \le 1\,000
  • 1ci10001 \le c_i \le 1\,000

Sample

Input:

3
2
3 1
7 2
5
1 2 4 8 7
3 3 2 2 12
1
1
1

Output:

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

Comment:

First test case: Stofl pays 77 Yen for the 33 first wagashi, and for the single second wagashi 22 Yen. This adds up to a total of 2323 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.

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.


            

        

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 KK Yen and contains pip_i wagashi of the ii-th type. The package can also be bought more than once. Calculate the lowest amount CC, such that Stofl can buy sufficiently many wagashi for CC Yen.

Input

The first line contains the number of test cases TT. TT test cases follow in the following format: The first line contains NN, the number of solved tasks and KK the price for the wagashi package. On the second line follow NN integers aia_i – representing the number of mice who have solved the ii-th task. The third line contains NN numbers cic_i – the ii-th wagashi costs cic_i Yen, followed by the fourth line which contains NN numbers pip_i – the wagashi package contains pip_i wagashi of the ii-th type.

Output

Same as in subtask 1.

Limits

  • T100T \le 100
  • 1N10001 \le N \le 1\,000
  • 1K1091 \le K \le 10^{9}
  • 1ai10001 \le a_i \le 1\,000
  • 1ci1091 \le c_i \le 10^{9}
  • 1pi10001 \le p_i \le 1\,000

Sample

Input:

2
3 5
7 3 2
1 4 1
3 2 1
1 5
8
2
2

Output:

Case #0: 11
Case #1: 16

Comment:

First test case: Stofl orders 22 wagashi packages for 55 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.

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.


            

        

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 CC, such that Stofl can buy sufficiently many wagashi for CC Yen.

Input

Same as in subtask 2.

Output

Same as in subtask 1 and 2.

Limits

  • T100T \le 100
  • 1N51051 \le N \le 5\cdot 10^{5}
  • 1K1091 \le K \le 10^{9}
  • 1ai1071 \le a_i \le 10^{7}
  • 1ci1051 \le c_i \le 10^{5}
  • All cic_i are equal.
  • 1pi1071 \le p_i \le 10^{7}

Sample

Input:

1
4 13
9 3 4 7
3 3 3 3
3 5 2 1

Output:

Case #0: 50

Comment:

Stofl orders 22 wagashi packages, 33 wagashi of the first type and 55 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.

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.


            

        

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 CC, such that Stofl can buy sufficiently many wagashi for CC Yen.

Input

Same as in subtasks 2 and 3.

Output

Same as in subtasks 1, 2 and 3.

Limits

  • T100T \le 100
  • 1N51051 \le N \le 5 \cdot 10^{5}
  • 1K1091 \le K \le 10^{9}
  • 1ai1071 \le a_i \le 10^{7}
  • 1ci1051 \le c_i \le 10^{5}
  • 1pi1071 \le p_i \le 10^{7}

Sample

Input:

2
3 22
8 1 12
7 31 2
3 4 2
4 41
13 9 2 19
5 2 3 6
3 2 1 4

Output:

Case #0: 74
Case #1: 189

Comment:

First test case: Stofl orders 22 wagashi packages. Second test case: Stofl orders 44 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.

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.


            

        

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 mm streets and nn intersections. The ii-th street connects intersections aia_i and bib_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 TT.

TT test cases follow, each in the following format: The first line of each test case contains two numbers nn, the number of intersections, and mm, the number of streets. mm lines follow, each containing two numbers aia_i and bib_i, the intersections connected by the ii-th street.

Output

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

Limits

  • For all test cases: T=100T=100, 0m(n)(n1)/20 \le m \le (n)(n-1)/2 and 0ai,bi<n0 \le a_i, b_i < n (0i<m0 \le i < m)
  • In subtasks 1 and 2: 0n1030 \le n \le 10^{3}
  • In subtask 3: 0n1020 \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:

1
4 3
0 1
0 2
0 3

Output:

Case #0: 2
0 1
2

Comment:

The intersection 00 is the center of the star and each other intersection is connected exactly to it.
image/svg+xml 1 2 3 2 1 0 0

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.

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.


            

        

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.

image/svg+xml 7 5 4 4 2 5 6 1 2 3 1 0 6 3 0

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.

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.


            

        

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:

2
5 7
0 1
0 2
0 3
1 2
1 3
2 3
3 4
6 3
0 1
2 3
4 5

Output:

Case #0: 4
6 4
2 5
1 3
0
Case #1: 3
0
1
2
image/svg+xml 1 2 3 2 1 0 0

image/svg+xml 7 5 4 4 2 5 6 1 2 3 1 0 6 3 0

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.

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.


            

        

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 nn cities that are numbered from 00 to n1n-1. The cities are connected by mm 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 kk 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 00 to k1k-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=2n = 2 and k100k \le 100.

Input

All subtasks use the same input format.

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

Each test case starts with a line containing the three integers nn, mm, and kk (n2n \ge 2, mn1m \ge n-1, k1k \ge 1).

The second line of each test case contains a single integer gg that is either 00 or 11: the level of detail required in the output.

Then mm lines describing the roads in Japan follow. The ii-th of these mm lines contains a triple of integers aia_i, bib_i and tit_i (0ai,bin10 \le a_i, b_i \le n-1, ti>0t_i > 0) – the two cities that the ii-th road connects and the time one needs to travel between the two cities.

You may assume that for each road we have aibia_i \neq b_i, and that all unordered pairs (ai,bi)(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 kk lines the description of the fireworks follows. The line jj of these kk lines contains a triple of integers cjc_j, sjs_j and djd_j – the city in which the firework takes place (0cjn10 \le c_j \le n-1), the timestamp of the moment when the fireworks start (sj0s_j \ge 0) and their duration (dj>0d_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=0g = 0 or two lines of output if g=1g = 1.

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

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

Input:

1
2 1 5
1
0 1 1
0 1 1
0 2 1
1 2 2
1 9 1
1 4 2

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.

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.


            

        

Subtask 2: Two fireworks (15 points)

In this subtask you may assume that n100n \le 100, k=2k = 2, and g=1g = 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=1g = 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 ii is the number of the test case (0-based in increasing order) and l100l \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: ll space-separated integers c1,,clc_{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=1l = 1 and c1c_{1} should be one of the two cities that have fireworks.
  • If Stofl can see both fireworks displays, c1c_{1} should be the city with the earlier and clc_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 clc_l in time for the second fireworks.

Note that if Stofl can see both fireworks, you do not have to optimize the value ll. 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:

1
5 5 2
1
0 1 1
0 2 2
1 3 3
2 3 1
3 4 1
0 1 1
4 8 2

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.

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.


            

        

Subtask 3: Sparse fireworks (30 points)

In this subtask you may assume that n500n \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.

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.


            

        

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., k100000k \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 NN tiles, for convenience numbered 00 to N1N-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=6N=6:

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

On the first pile lie 3 tiles; 00 at the top, 55 in the middle and 22 at the bottom. The second pile consists of one single tile, the 11, and the last pile has 44 at the top and 33 at the bottom.

Another possibility for N=3N=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=4N=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=4N=4. Here, sorted means that the 00 must be at the top and the biggest tile at the bottom.

Subtask 1 (25 points)

Given an arrangement of the nn 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,000100,000 moves, so that the output doesn’t get too big, and guarantee that it is always possible with less than 100,000100,000 moves.

Input

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

The first line of the test case contains NN, the number of tiles. A second line follows with AA, the number of tiles on the first pile, followed by AA number values a0,,aA1a_{0},{\dots},a_{A-1}, the values on the first pile. The third line works the same way, BB is first, then BB number values b0,,bB1b_{0},{\dots},b_{B-1} with the values of the second pile. The fourth line contains CC, followed by CC number values c0,,cC1c_{0},{\dots},c_{C-1}.

The tiles a0a_{0}, b0b_{0} and c0c_{0} are the topmost tiles respectively, the tiles aA1a_{A-1}, bB1b_{B-1} and cC1c_{C-1} the bottommost.

Note that AA, BB and/or CC can also be 00, 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=NA+B+C=N, and that all 0ai,bi,ci<N0\le a_i,b_i,c_i<N are different.

Output

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

Limits

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

For the output, M100000M\le 100\,000.

Example

Input:

2
3
3 2 1 0
0
0
9
3 0 1 2
3 3 4 5
3 6 7 8

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.

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.


            

        

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 TT. TT test cases follow with just the single number NN.

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

Output

Multiple lines in this format:

  • a0a_{0} a1a_{1} \dots ai1a_{i-1} | aia_i \dots aj1a_{j-1} | aja_j \dots an1a_{n-1}: bb -> cc, if in this case you would like to put the topmost tile from pile bb on top of pile cc, or
  • a0a_{0} a1a_{1} \dots ai1a_{i-1} | aia_i \dots aj1a_{j-1} | aja_j \dots an1a_{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(N+2)!/2 different arrangements (The exclamation mark means factorial, in short (N+2)!=1234(N1)N(N+1)(N+2)(N+2)! =1\cdot 2\cdot 3\cdot 4\cdot \ldots \cdot (N-1)\cdot N\cdot (N+1)\cdot (N+2)).

Limits

T=6T=6 and 1N61 \le N \le 6. In the input, every NN from 11 up to and including 66 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:

For the arrangement “1 0 | |”, first the 1 is moved to the right (4th rule) which results in “0 | 1 |”. Then the 0 is moved to the right (7th rule) which results in “| 0 1 |” and it is finished.

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.

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.


            

        

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=3N=3 only one pile is non-empty, and it has a 00 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=8T=8 instead of T=6T=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(N1)+N(N1)(N2)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 00 is visible.

These are special cases for N2N\le 2. For N>2N>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=8T=8 and 1N81 \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.

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.


            

        

Subtask 4 (30 points)

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

Write a function f(n,a,b,c)f(n,a,b,c), which for nn tiles takes the three topmost numbers aa, bb, cc of the piles (empty piles are encoded as 1-1) and returns either 01, 10, 12, 21, 02 or 20 (for 010\to 1, 101\to 0, 121\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 ff in dependence on nn.

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 nn mice playing the game and mm skills to learn. The skills have different difficulties: the ii-th skill takes sis_i days of practice to master.

At the start of the game one player chooses a target skill tt. Each day every mouse chooses one of the mm 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 nmn m, the number of mice nn and the number of skills mm. Your player is always the mouse with index 0. On the next line there are mm space separated integers sis_i, the difficulty of the ii-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 tt, the current target skill. If tt is below zero there is a special meaning (see below). On the next line there are nn space separated integers pip_i, the skill the ii-th player chose to practice. p0p_{0} will be the skill you chose in the last round. Then you have to print one line with rr, 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 pip_i will be 1-1.

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

t=1t = -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 tt, the new target skill, and the second with the skill you want to practice this round.

t=2t = -2 means that the game has been reset and a new game will start. All the game parameters are the same (i.e. nn, mm, sis_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 nmn m and sis_i.

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

Limits

  • 2n1002 \le n \le 100
  • 2m10002 \le m \le 1000
  • 1si10001 \le s_i \le 1000
  • 0pi<m0 \le p_i < m
  • 3t<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

RankUsernameTotal (600)sushi (100)wagashi (100)cheesep… (100)
cheesepatrol
hanabi (100)mahjong (100)samurai (100)
loading ...