First Round SOI 2023/2024

Overview

Welcome to the first round of the Swiss Olympiad in Informatics! You will find below an overview of what you’ve done so far as well as a few things that you should know before getting started.

This contest is over.

CategoryTaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
Junior onlyharvest‒/100‒/17‒/18‒/19‒/21‒/25
Junior onlyexhibition‒/100‒/7‒/23‒/31‒/39
Junior onlycruisetrip‒/100‒/20‒/25‒/25‒/30
Bothcalendar‒/100‒/16‒/12‒/21‒/18‒/33
Bothlabyrinth‒/100‒/12‒/11‒/19‒/26‒/32
Bothpyramids‒/100‒/14‒/16‒/30‒/40
Regular onlyirrigation‒/100‒/4‒/13‒/21‒/24‒/38
Regular onlycaravan‒/100‒/10‒/10‒/20‒/35‒/25
Regular only1h‒/100‒/25‒/25‒/25‒/25

Harvest Day

In the town of Bloomsville, Mouse Binna runs a community garden where townsfolk can rent a plot to grow their own fruits and vegetables. Each year, Binna hosts a Harvest Day, where everyone brings the fruits and vegetables they’ve grown to share with the community.

This year, Mouse Binna wanted to ensure that every resident of Bloomsville received an equal share of the harvest, so she provided each person with a basket to fill. But right before the townsfolk came to collect their shares, Binna noticed that some baskets had lots of fruits and vegetables, while others had just a few.

Determined to spread the joy of the harvest equally, Mouse Binna decides to redistribute items from their baskets to balance out their hauls.

Mouse Binna’s challenge is to figure out the minimum number of items she has to move from one basket to another to ensure everyone went home with an equal amount of harvest.

Subtask 1: Is it even possible? (17 points)

In this subtask, Mouse Binna is not concerned about the number of items she has to swap and only asks you to find out whether it’s possible to swap the items in the baskets so that everyone has the same amount of items in their baskets or not.

Input

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

The first line of the test case contains a single integer number nn — the total number of baskets.
The second line contains nn integer numbers: aia_i — the number of items in the ii -th basket.

Output

For the ii-th test case, output a line “Case #i: YES” if it’s possible to swap the items in the baskets so that everyone has the same amount of items in their baskets, or “Case #i: NO” otherwise.

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1n10001 \le n \le 1000
  • 0ai10000 \le a_i \le 1000

Example

Input:

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

Output:

Case #0: YES
Case #1: NO
Case #2: YES

Comment:

Case #0: Binna could move 2 items from the 2nd basket to the 1st basket, and 1 item from the 4th basket to the 3rd basket and 2 items from the 4th basket to the 5th basket, so that each basket would contain exactly 3 items.
Case #1: Binna could not make all baskets contain the same number of items.
Case #2: Binna could move 2 items from the 3rd basket to the 1st basket, and 5 items from the 2nd basket to the 4th basket, so that each basket would contain exactly 5 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 2: One large basket (18 points)

In this and all following subtasks, Mouse Binna is interested in the minimum number of items she has to move from one basket to another to ensure everyone went home with an equal amount of harvest. Additionally, in this subtask, Binna heard that all farmers in Bloomsville had an exceptionally bad harvest this year and are only able to bring exactly one item. To make sure to spread some joy, she invited her friend from a neighboring town, in the hope that she has had a better harvest this year.

Input

Same as subtask 1.

Output

For the ii-th test case, output a line “Case #i: x” where xx is the minimum number of items Binna has to move.

In this and all following subtasks, it is guaranteed that Binna can distribute the items to the baskets equally (in particular that means for all the following cases the answer in Subtask 1 would be yes).

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1n10001 \le n \le 1000
  • 0a010000 \le a_{0}\le 1000
  • ai=1a_i = 1 for all i>0i>0

Example

Input:

3
5
6 1 1 1 1
2
15 1
1
4

Output:

Case #0: 4
Case #1: 7
Case #2: 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: Everyone brings almost the same amount (19 points)

Luckily, the times of the bad harvest are over and the fields have been flourishing again this year. Oddly enough, Mouse Binna notices that everyone arrives with a very similar amount of items. Maybe the rain this year was very evenly distributed over Bloomsville and thus everyone harvested almost the same amount of crops? When doing the math Binna notes that the minimum and the maximum number of items brought by the inhabitants of Bloomsville only differs by 22.

Input & Output

Same as subtask 2.

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1n10001 \le n \le 1000
  • 0a010000 \le a_{0}\le 1000
  • aiaj2|a_i - a_j| \le 2 for all i,ji,j

Example

Input:

3
4
1 3 2 2
4
2 4 3 3
9
1 1 3 1 3 3 2 2 2

Output:

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

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: General case (21 points)

For the next festival, Mouse Binna notices a wide variety of brought crops both in type and in number. She deduces that there are no special conditions that hold this year and she has to find the minimum amount of items she has to move without any additional assumptions to ensure she does not do any extra work this year.

Input & Output

Same as subtask 3.

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1n10001 \le n \le 1000
  • 0ai10000 \le a_i \le 1000.

Example

Input:

4
4
3 1 3 1
2
2 2
5
14 8 4 3 6
3
20 3 1

Output:

Case #0: 2
Case #1: 0
Case #2: 8
Case #3: 12

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 5: A lot of harvest (25 points)

This year was a very good year for the farmers of Bloomsville and everyone brings enormous amount of fruits and vegetables (up to one billion each). Mouse Binna deduces that there are no special conditions that hold this year and she has to find the minimum amount of items she has to move without any additional assumptions to ensure she does not do any extra work this year.

Input & Output

Same as subtask 4.

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1n1051 \le n \le 10^{5}
  • 0ai10100 \le a_i \le 10^{10}.

Attention: The numbers in this subtask will get very large. If you use integers (e.g. in C++) then you should switch to a larger datatype (e.g. long long) instead to avoid overflows.

Example

Input:

2
4
3 1 3 1
2
0 10000000000

Output:

Case #0: 2
Case #1: 5000000000

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).

Exhibition

Mouse Stofl wants to make an exhibition of the most expensive paintings that exist, based on his reasoning that the most valuable paintings are also the most beautiful. However, that might be a bit boring, so he additionally has the constraint that, for any painter included in the exhibition, there are at least two paintings of this painter. That way, visitors will be better able to see the individual style of each painter.

Obviously, with all the most expensive paintings in one place, he needs an insurance. For calculating the insurance costs, he needs to know the total value of all the paintings in the exhibition. Since he isn’t yet sure how big the exhibition is going to be, he just wants to calculate it for every possible number of paintings, from 2 up to all the paintings.

Subtask 1: A single painter (7 points)

This might be a nice idea, but who is actually going to borrow Stofl his most expensive paintings for the exhibition? For now, he just has access to the paintings that he has made himself.

Input

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

  • The first line contains two integers KK and NN, the number of painters, and the total number of paintings.
  • Each of the KK following lines contains a number NiN_i, followed by NiN_i numbers vi,0,vi,1,,vi,Ni1v_{i, 0},v_{i, 1},{\dots},v_{i, N_i-1}, the values in Egyptian pounds of all the NiN_i paintings of painter ii.

In this subtask, we always have K=1K=1.

Output

For the tt-th test case print a line “Case #t:” followed by N1N-1 numbers, where the ii-th number (0i<N10 \le i < N-1) is the total value of all paintings of the most expensive exhibition with i+2i+2 paintings, and where no painter has exactly one painting in the exhibition. It is guaranteed that such an exhibition exists for each ii.

Limits

  • T=100T=100
  • K=1K=1
  • 2Ni2 \le N_i for all 0i<N0\le i<N
  • N=iNiN = \sum_i N_i
  • N1000N \le 1000
  • 1vi,j1051 \le v_{i, j} \le 10^{5} for all 0i<N0\le i<N, 0j<Ni0\le j<N_i

Example

Input:

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

Output:

Case #0: 7
Case #1: 15 20
Case #2: 6 9 12

Comment:

Case #0: There are only two paintings of value 4+3=74+3=7 Egyptian pounds, so we have to take both.
Case #1: The two most expensive paintings have value 8+7=158+7=15 EGP. All three paintings are worth 20 EGP.

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 painters (23 points)

Just one painter is clearly not enough. Stofl additionally asked Mouse Binna whether he could borrow her paintings, and luckily she agreed.

Input/Output

Same as in subtask 1.

In this subtask, we always have K=2K=2.

Limits

  • T=100T=100
  • K=2K=2
  • 2Ni2 \le N_i for all 0i<N0\le i<N
  • N=iNiN = \sum_i N_i
  • N5000N \le 5000
  • 1vj1051 \le v_j \le 10^{5} for all 0j<Ni0\le j<N_i

Example

Input:

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

Output:

Case #0: 12 17 15 20
Case #1: 13 16 24 29 31 32

Comment:

Case #0: The paintings of painter 0 are all more expensive than those of painter 1, so we only take these for exhibitions with two or three paintings. However, if we want four paintings, we have to take both paintings of painter 1, and the exhibition ends up worth less than with just three paintings.

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: More painters (31 points)

Mouse Stofl made a lot of phone calls to various galleries, and finally found the Bibliotheca Alexandrina, who was willing to lend some paintings from its collection to Stofl.

Input/Output

Same as in subtask 1.

Limits

  • T=100T=100
  • 1K5001 \le K \le 500
  • 2Ni2 \le N_i for all 0i<N0\le i<N
  • N=iNiN = \sum_i N_i
  • N1000N \le 1000
  • 1vj1051 \le v_j \le 10^{5} for all 0j<Ni0\le j<N_i

Example

Input:

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

Output:

Case #0: 14 17 26 29 36 39 41 42
Case #1: 14 18 28 32 38 42 46 49 52 55 58 60 61 62

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: A lot of painters (39 points)

The previous exhibition was a huge success. Afterwards, many art owners contacted Mouse Stofl and offered to lend their paintings for an even bigger exhibition.

Input/Output

Same as in subtask 1.

Limits

  • T=100T=100
  • 1K400001 \le K \le 40000
  • 2Ni2 \le N_i for all 0i<N0\le i<N
  • N=iNiN = \sum_i N_i
  • N80000N \le 80000
  • 1vj1051 \le v_j \le 10^{5} for all 0j<Ni0\le j<N_i

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).

Cruise Trip

The Nile is a famous river in Egypt and one of the longest in the world. Mouse Stofl, who recently heard about the river, is planning to rent a cruise ship and travel on the Nile to appreciate the magnificent landscape. He wants to be the coolest mouse in his friend group by surprising them with all the photos he’s going to take during the trip. He wants to visit three different cities in Egypt to replenish his supplies and asks for your help to plan the route he’s going to take. On the map he gave you, the Nile is divided into a grid of NN rows and MM columns with islands positioned on some grid cells. Every 1010 minutes, the boat can move to an adjacent grid cell provided no island is occupying the cell. A cell is adjacent to another one if both cells share a common side, diagonals are not permitted.

Because he has high standards, Mouse Stofl wants the cruise to be as long as possible without travelling through the same grid cell twice and without travelling upstream because of his limited supplies. This means for each movement you can travel one cell left, one cell right or one cell down. Fortunately for you Stofl has already made sure there exists a trip which satisfies his constraints but he did not know how to make sure the trip was the longest one possible.

Mouse Stofl has the authorization to start his trip anywhere on the upper row of the grid if there is water there and must travel downstream to any of the cells on the bottom row of the grid.

Input/Output

All subtasks have the same input and output format.

Input

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

  • The first line contains two integers NN and MM, the number of rows and columns of the grid respectively.
  • The next NN lines will contain MM characters either “#” or “.”. “#” indicates the cell contains an island, “.” indicates you can travel freely from and to this cell.

A valid trip from the top row to the bottom one is guaranteed to exist.

Output

For the tt-th test case, output a line “Case #t:”, followed by the number LL, the maximum possible length of a trip.

Subtask 1: A first trip (20 points)

The first destination Stofl wants to reach is Sohag. The width of the Nile until Sohag is very narrow. On the map you have to prepare the trip, the Nile is separated into only two columns.

Limits

  • T=100T=100
  • M=2M=2
  • 1N1061 \le N \le 10^{6}

Example

Input:

2
3 2
..
.#
.#
5 2
#.
#.
..
..
.#

Output:

Case #0: 4
Case #1: 6

Comment:

Case #0: The optimal path starts on the top right cell then goes 11 cell left and 22 cells down. The total length is 44.
Case #1: One of the optimal paths starts on the top right cell then goes 33 cells down, 11 cell left and 11 cell down. The total length is 66.

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: Heading to Asyut (25 points)

After his first stop, the Nile is becoming wider and Mouse Stofl now has more freedom when travelling. The Nile is now represented with at most 2020 columns on the map.

Limits

  • T=100T=100
  • 2M202 \le M \le 20
  • 1N51051 \le N \le 5\cdot 10^{5}

Example

Input:

2
3 5
...#.
.#.#.
...#.
5 6
...#..
..##..
...#..
.#....
.#.#..

Output:

Case #0: 7
Case #1: 13

Comment:

Case #0: One of the optimal paths starts on the top left cell then goes 22 cells to the right, then 22 cells down, then 22 cells left and ends up on the bottom left cell. The total length is 77.
Case #1: One of the optimal paths starts on the 33 left, 11 down, 11 left, 11 down, 22 right, 11 down, 33 right, 11 down and 11 left for a total length of 1313.

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: Problems begin (25 points)

Mouse Stofl left Asyut and is now heading to Cairo on the largest part of the Nile. The map you have doesn’t have a width restriction. However his boat has a technical problem which causes the boat’s steering mechanism to malfunction. Because of that Mouse Stofl is unable to steer enough to make his boat travel in all directions. He can now either go down or to the right. That means for each grid cell the boat can either go to the cell directly to its right or the one directly downwards. Even with the problems he is facing Stofl does not want to cancel his trip so he wants you to create him a trip which never goes left.

Input/Output

Same as in the previous subtasks. Additionally, in this subtask it is guaranteed that there exists a valid trip from the top row to the bottom row which only requires Stofl to move down and to the right. You need to output the longest possible length of such a trip.

Limits

  • T=100T=100
  • 2NM51062 \le N \cdot M \le 5\cdot 10^{6}

Example

Input:

2
5 6
...#..
..##..
...#..
.#..#.
.#.#..
7 8
.##.#.#.
#..#..#.
.#......
...##.##
##.##..#
...#.#.#
.#...#.#

Output:

Case #0: 7
Case #1: 8

Comment:

Case #0: One of the optimal paths starts on the top left cell then goes 11 cell to the right, then 22 cells down, then 11 cell right, then 22 cells down and ends up on the 33-rd bottom cell. The total length is 77.
Case #1: The optimal path starts on the 66-th cell and goes 44 down, 11 right and 22 down for a total length of 88.

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: Getting to Cairo (30 points)

Mouse Stofl managed to fix the problem with his boat’s steering and now only needs to finish his trip. He can again go in all three directions, left, right or down.

Limits

  • T=100T=100
  • 2NM51062 \le N \cdot M \le 5 \cdot 10^{6}

Example

Same as Subtask 22.

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).

Calendar

Mouse Binna had to leave Mouseland for Egypt in order to plan the upcoming IMOI (the International Mouse Olympiad in Informatics). Unfortunately, Egypt is very warm and Binna finds it very hard to get work done. She now has one month to finalize the planning of IMOI which also lasts one month. As it is well known, every month of the mice-calendar contains exactly nn days. She still has mm event to plan before the competition starts. The ii-th event starts on day lil_i and ends on day rir_i. Luckily, Mouse Binna is very good at multitasking and can handle as many events as needed on the same day.

Additionally, Mouse Stofl reminded her that the SOI camp is scheduled to happen the same month as IMOI and should last exactly kk days. However, she can choose when in the month the camp will happen to ease the planning.

To keep her organisation schedule easy to follow, she decides to plan an entire day of events during a single day of preparation and does not work on any other day during this day. That is on the ii-th day of preparation she will do the necessary work to plan the jj-th day of IMOI, where 0i,jn10 \le i,j \le n-1.

As the weather is much warmer than Mouseland’s chill countrylands, her productivity decreases as time goes on. On the first day, she has a productivity score of n1n-1 and every day loses one productivity point up to her last preparation day where she has productivity score of 00.

As Mouse Binna is very dedicated she wants IMOI and the SOI camp to run as smoothly as possible, hence she wants to work on the days that have more events first. In fact, she estimates her work’s worth as the sum of each’s tasks accomplished times the productivity on that day. That is if she had aa tasks on a day with productivity bb, her score for that day is aba \cdot b.

Because of all the work she has to do, she does not have time to choose when she will plan which tasks, so she charged you to choose the order that will maximise her productivity. And who knows, if you do it well, she might even invite you to the camp!

Subtask 1: Tough start (16 points)

In this subtask k=0k=0, which means that Binna doesn’t have to do the camp planning, because Stofl already did it for her.

However, all IMOI events starts on the first day of the competition, i.e. li=0l_i=0 for all 0im10 \le i \le m-1.

Input

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

The first line of the test case contains three integer numbers nn, mm and kk — the number of days, the number of IMOI events and the length of the camp.
The following mm lines contains two integer numbers in each: lil_i rir_i — the ii-th event starts on the lil_i-th day and ends on the rir_i-th day (inclusive).

Output

For the ii-th test case, output a line "Case #i: " followed by single integer number ss — the maximum total productivity score Binna can get for all events.

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1n10001 \le n \le 1000
  • 0m10000 \le m \le 1000
  • k=0k = 0
  • 0=liri<n0 = l_i \le r_i < n for all 0im10 \le i \le m-1.

Example

Input:

3
4 3 0
0 3
0 1
0 0
3 3 0
0 1
0 2
0 2
3 2 0
0 2
0 2

Output:

Case #0: 14
Case #1: 9
Case #2: 6

Comment:

Case #0: The optimal order to plan the days in is [0,1,3,2][0, 1, 3, 2]. That way Binna will get 66 points for the first event (3+2+1)(3 + 2 + 1), 55 points for the second event (3+23+2) and 33 points for the third event. So the total number of points is 1414.
Case #1: The optimal order to plan the days in is [0,1,2][0,1, 2]. That way Binna will get 3 points for the first event, 33 points for the second event and 33 points for the third event. So the total number of points is 99.
Case #2: The optimal order to plan the days in is [0,1,2][0, 1, 2]. That way Binna will get 33 points for the first event and 33 points for the second event. So the total number of points is 66.

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: Hard Times (12 points)

Stofl still did the camp planning for Binna (k=0k = 0), but now the IMOI events can start on any day, i.e. 0liri<n0 \le l_i \le r_i < n for all 0im10 \le i \le m-1.

Input & Output

Same as subtask 1.

Limits

Same as subtask 1, except that for lil_i we have 0li<n0 \le l_i < n.

Example

Input:

3
4 3 0
3 3
0 1
0 0
3 3 0
0 1
1 2
0 2
3 2 0
0 2
1 2

Output:

Case #0: 9
Case #1: 8
Case #2: 6

Comment:

Case #0: The optimal order to plan the days in is [0,3,1,2][0, 3, 1, 2]. That way Binna will get 22 points for the first event, 44 points for the second event and 33 points for the third event. So the total number of points is 99.
Case #1: The optimal order to plan the days in is [1,2,0][1, 2, 0]. That way Binna will get 22 points for the first event, 33 points for the second event and 33 points for the third event. So the total number of points is 88.
Case #2: The optimal order to plan the days in is [2,1,0][2, 1, 0]. That way Binna will get 33 points for the first event and 33 points for the second event. So the total number of points is 66.

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: Overwhelmed (21 points)

In this subtask Mouse Binna is still getting help from Mouse Stofl with the Camp planning but a month in Mouseland can be very long and there are a lot of events to be planned for IMOI.

Input & Output

Same as subtask 2.

Limits

Same as subtask 2, but n105n \le 10^{5} and m105m \le 10^{5}.

Example

Input:

3
4 3 0
3 3
0 1
0 0
3 3 0
0 1
1 2
0 2
3 2 0
0 2
1 2

Output:

Case #0: 9
Case #1: 8
Case #2: 6

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: No help (18 points)

In this and the next subtasks Mouse Binna has to do the camp planning as well. Note that in this subtask the length of a month is shorter and there are less events to plan than in Subtask 3.

Input & Output

Same as subtask 2.

Limits

Same as subtask 2, but 0kn0 \le k \le n.

Example

Input:

3
4 3 2
3 3
0 1
0 0
3 3 3
0 1
1 2
0 2
3 2 1
0 2
1 2

Output:

Case #0: 14
Case #1: 11
Case #2: 8

Comment:

Case #0: The optimal camp start date is the 0th day. The optimal order to plan the days in is [0,1,3,2][0, 1, 3, 2]. That way Binna will get 55 points for the camp planning, 11 points for the first event, 55 points for the second event and 33 points for the third event. So the total number of points is 1414.
Case #1: The optimal camp start date is the 0th day. The optimal order to plan the days in is [1,2,0][1, 2, 0]. That way Binna will get 33 points for the camp planning, 22 points for the first event, 33 points for the second event and 33 points for the third event. So the total number of points is 1111.
Case #2: The optimal camp start date is the 2nd day. The optimal order to plan the days in is [2,1,0][2, 1, 0]. That way Binna will get 22 points for the camp planning, 33 points for the first event and 33 points for the second event. So the total number of points is 88.

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 5: Lot’s of work (33 points)

In this subtask the months in Mouseland can be very long again and there are a lot of events to plan for IMOI.

Input & Output

Same as subtask 4.

Limits

Same as subtask 4, but n105n \le 10^{5} and m105m \le 10^{5}.

Example

Input:

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

Output:

Case #0: 47
Case #1: 1
Case #2: 0
Case #3: 56

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).

Labyrinth

The famous explorer Mouse Binna is undergoing an expedition in the ancient tomb of the Great Mouse Pharaoh Stofl. While wandering through the labyrinth of the Pharaoh, she unexpectedly steps on an unsuspicious stone activating one of the many grave traps. Fortunately, as a famous explorer would, she came prepared with a plan for deactivating such a trap. For this she needs to rearrange torches in the labyrinth in a specific way:

The labyrinth consists of NN chambers. There are N1N-1 corridors, each connecting two chambers. It is possible to walk from any chamber to any other chamber using one or more of the corridors. Furthermore, there are no cycles in the labyrinth.

Each of the chambers has either a torch or no torch in it. Mouse Binna has a map of the labyrinth showing in which chambers a torch should be and in which not, to deactivate the trap. Unfortunately, the current distributions of the torches might not be according to her map, so she needs to move some torches.

She can take a torch from one chamber and move it to another chamber which is directly connected via a corridor and where there is no torch already. (Two torches in one chamber destabilized the labyrinth endangering Binna’s life further). As carrying a torch through a corridor might also destabilize the labyrinth, she wants to minimize the amount of time a torch moves through a corridor. (As an experienced and modern explorer she does not care how long she walks, or if she needs to walk without a torch, as she has her trusty headlamp).

Can you help her find the minimal amount of times a torch moves through a corridor?

For all Subtasks

Input

The first line contains the number of test cases TT. This is followed by TT test cases in the following format: The first line of the test case contains NN, the number of chambers in the labyrinth.

NN lines follow, each line has two characters mim_i tit_i, either “0” or “1”, separated by a space. The first character represents the number of torches that should be present in the chamber at the end. The second character represents the number of torches in the chamber at the beginning. The total number of torches that should be in the end is the same as the number of torches in the beginning.

Then N1N-1 more lines follow, describing the structure of the labyrinth. Each line with two integers viv_i uiu_i, separated by a space, representing a corridor between the chamber viv_i and uiu_i.

Output

For the ii-th test case, output single line “Case #i:”, followed by a single integer, the minimal amount of time a torch moves through a corridor.

For every input, it is guaranteed that there is a sequence of torch moves that places a torch in each chamber according to the map.

Note for Recursion and Python

You might hit recursion limit, memory limit, stack limit or similar, if you are using recursive functions in python. See this wiki article on possible solutions for these problems.

Subtask 1: Mukhtar Tomb (12 points)

The Mukhtar Tomb is of a very special shape. There is a central chamber with the mummy of the Pharaoh, with index 00. Every other chamber is connected to the central chamber.

Limits

There are T=100T=100 test cases. In every test case:

  • 1N1000001 \le N \le 100\,000
  • ui=0u_i = 0

Example

Input:

2
4
0 0
0 1
1 1
1 0
1 0
3 0
2 0
1
0 0

Output:

Case #0: 2
Case #1: 0

Comment:

Case #0:
In this example, the tomb has four chambers, chamber 00 centered in the middle and three chambers connected to it.
We need to move the torch away from chamber 11, and move a torch into chamber 33. Unfortunately, we cannot directly do this.
Instead, we first move the torch from chamber 11 to chamber 00 getting chamber 11 correct, but chamber 00 wrong.
Then move the torch from chamber 00 to chamber 33.
Chamber 00 has no torch anymore, but chamber 33 has, as desired by the map.
So the solution is 2 as we moved a torch through corridor 101-0 and through 030-3.
Case #1:
In this case there is only one chamber without any torch, so there is nothing to do.

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: Dark Tomb (11 points)

In the dark tomb there exists only one torch in the whole labyrinth.

Limits

There are T=100T=100 test cases. In every test case:

  • 1N1000001 \le N \le 100\,000
  • ci=1c_i = 1 for one ii and ci=0c_i = 0 for all else
  • ti=1t_i = 1 for one ii and ti=0t_i = 0 for all else

Example

Input:

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

Output:

Case #0: 3
Case #1: 2

Comment:

Case #0:
The labyrinth is ordered on a line like this: 01230-1-2-3.
We need to move the torch from chamber 33 all the way to chamber 00, to match the pattern on her map.
Case #1:
Similar as Case #0 in subtask 1.

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: Marathon Tomb (19 points)

All the chambers are ordered in a line. Can you make use of this to reorder the torches?

Limits

There are T=100T=100 test cases. In every test case:

  • 1N10000001 \le N \le 1\,000\,000
  • ui=vi1u_i = v_i - 1 for 1uiN11 \le u_i \le N-1

Example

Input:

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

Output:

Case #0: 3
Case #1: 6

Comment:

Case #0:
Similar as Case #0 in subtask 2.
Case #1:
Move the torch from chamber 22 to chamber 44, passing through 22 corridors.
Then move the torch from chamber 11 to chamber 44, passing through 22 corridors again.
Finally, move the torch from chamber 00 to chamber 33, passing through 22 corridors again.
Since the corridors 121-2 and 232-3 are passed through twice, they are also counted twice in the solution.

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: Tomb of Mouse Tutankhamun (26 points)

Tomb of Mouse Tutankhamun does not contain many chambers, as they died at a young age.

As Tutankhamun did not get a pyramid like other pharaohs, the layout of his tomb is modeled after a pyramid. This means that there are hh chambers ordered on a line, representing the left side of the ‘pyramid’. Starting from the first chamber of this ‘left line’, there is another line, with h1h-1 chambers. Starting from the second chamber of this ‘left line’, there is another line, with h2h-2 chambers. Continue like this until the last chamber of this ‘left line’ (here there is no further line, as it would contain 00 chambers). In total there will be n=h(h+1)2n = \frac{h \cdot (h + 1)}{2} chambers in such a tomb.

Here are two pictures, visualizing the labyrinth of such tombs:

    0
   / \
  1   2
 / \   \
3   4   5


        0
       / \
      1   2
     / \   \
    3   4   5
   / \   \   \
  6   7   8   9
 / \    \   \   \
10  11  12  13  14

Limits

There are T=100T=100 test cases. In every test case:

  • 1N10001 \le N \le 1\,000

Example

Input:

2
15
0 0
1 1
1 0
0 0
1 1
1 0
0 1
0 0
1 1
1 0
0 0
0 0
0 1
0 1
0 0
0 1
0 2
1 3
1 4
2 5
3 6
3 7
4 8
5 9
6 10
6 11
7 12
8 13
9 14
6
0 0
0 0
0 1
0 1
1 0
1 0
0 1
0 2
1 3
1 4
2 5

Output:

Case #0: 17
Case #1: 3

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 5: Tomb of Great Pharaoh Stofl (32 points)

Now that you have mastered all the previous tombs it is time for the challenge. The Tomb of Great Pharaoh Stofl is the largest tomb known to mousekind. In this tomb, there are no additional restrictions on the structure of the labyrinth. Recall that in any labyrinth it is possible to walk from any chamber to any other chamber using one or more of the corridors. Furthermore, there are no cycles in any labyrinth. Can you help Binna escape the Great Pharaoh Stofl’s trap?

Limits

There are T=100T=100 test cases. In every test case:

  • 1N10000001 \le N \le 1\,000\,000

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).

Pyramids

Mouse Stofl is in charge of organizing the excursions for IMOI 2024 in Egypt. Of course, a trip to see the famous Pyramids cannot be missing from the program. When Stofl arrives in the desert, he is very disappointed to not actually see pyramids but what seems to be an arbitrary pile of stones with NN stones.

After taking a closer look, Stofl realizes that these stones can actually form a pyramid and is determined to reconstruct it. The pieces are of different sizes (denoted by 0,1,2,,N10,1,2,{\dots},N-1) and Stofl notices that there is exactly one stone of every size (in particular that means that there are exactly NN stones).

Next to the pile of stones there are K1K-1 stable patches where Stofl can place the stones. When Stofl tries to place a stone anywhere else in the desert it starts to sink into the sand. The spot below the pile of stone is also stable (so there is a total of KK stable patches).

In his class “Pyramid building 1x1” Stofl learned that pyramids need to be built with the largest stone at the bottom and then adding the other stones in decreasing size (that is, the stone with size N1N-1 goes on the bottom, the stone with size N2N-2 on top of it, then the stone with size N3N-3 and so on). The stones are all very heavy and Stofl can only carry one at a time. For every pile of stones, he can pick up the top stone and place it on any other pile or any empty stable patch.

Stofl asks you for help on how to build the pyramid in the place where the pile of stones is currently located.

Subtask 1: Being the apprentice (14 points)

In this subtask you do not have to plan how to move the stones but only execute Stofl’s instructions. Stofl has already started building the pyramid before you arrived, so in this subtask the stones are arbitrarily distributed as piles on the KK stable patches.

Input

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

The first line of each test case contains three numbers N,K,MN,K,M which represent the number of stones, the number of stable patches (including the ones the stones are currently lying on) and the number of instructions Stofl gives you.

The next KK lines will describe the piles of stone. Each of these lines starts with a number rr with 0rN0\le r\le N, the number of stones on this pile, followed by rr numbers s0,s1,sr1s_{0},s_{1},{\dots}s_{r-1} where 0siN10 \le s_i\le N-1 indicating the size of the ii-th stone on this pile from the bottom to the top (that is, s0s_{0} is the size of the bottom most stone and sr1s_{r-1} is the size of the stone on top of the pile).

The next MM lines will each contain two numbers, aa and bb with 0a,bK10\le a,b\le K-1, that represent that we moved the top element from stack aa to stack bb. It is guaranteed that this is a legal move (this is, that stack aa is not empty).

It is guaranteed that every stone size from 00 to N1N-1 appears exactly once.

Output

For the tt-th test case, on the first line print “Case #t:”. This should be followed by KK lines, where the ii-th line first contains a number rir_i indicating the number of stones on the ii-th pile after you executed all of Stofl instruction, followed by rir_i numbers s0,s1,,sri1s_{0},s_{1},{\dots},s_{r_i-1} separated by spaces, describing the size of the stones on the ii-th pile starting with the lowest stone.

Limits

There are T=100T=100 test cases. In each testcase we have:

  • 1N10001 \le N \le 1000,
  • 2K102\le K\le 10,
  • 1M100001\le M\le 10000.

Example

Input:

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

Output:

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

Comment:

Case #0: We have two piles of stones and three stones. In the beginning, the first pile only has the stone of size 22 and the second pile has two stones, the stone of size 00 on the bottom and the stone of size 11 on top of it. We get three instructions from Stofl. With the first instruction, we move the stone of size 22 from pile 00 to pile 11, then we move the same stone back to pile 00 (as we put it on the top of pile 11 when we moved it there). With the third instruction, we move stone 11 from pile 11 to pile 00. Thus we end up with pile 00 having two stones, the stone of size 22 on the bottom and the stone of size 11 on top, and pile 11 having only the stone of size 00.
Case #1: Here we have three piles of stones, the first one having three stones, the stone of size 00 at the bottom, the stone of size 33 on top of it and the stone of size 11 at the top of the pile. The second pile is empty at the start, and the third pile has two stones, the stone of size 44 on the bottom and the stone of size 22 on top of it. We now get five instructions from Stofl. With the first instruction, we move the stone of size 11 to the empty pile 11. Then we move the stone of size 33 to pile 22 and the stone of size 11 back from pile 11 to pile 00 (now sitting on top of the stone of size 00). Then we move the stone of size 33 from pile 22 to the (again empty) pile 11 and do the same with the stone of size 22 (placing it on top of the stone of size 33). Thus we are left with the stones of size 00 and 11 on pile 00, the stones of size 33 and 22 on pile 11 and the stone of size 44 on pile 22.

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: Pyramid of Ahmose (16 points)

The Pyramid of Ahmose is a small pyramid located near Abydos. Mouse Stofl decided this is the perfect location to train you how to build a pyramid.

From now on, all the stones will be on pile 00 initially and you have to decide how to move the stones to end up with a pyramid at the end.

Input

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

The first line of each test case contains two numbers N,KN,K which represent the number of stones and the number of stable patches (including the one the stones are currently lying on). The next line describes the order of stones on the first pile. There are NN numbers, separated by spaces, s0,s1,,sN1s_{0},s_{1},{\dots},s_{N-1} where 0siN10 \le s_i\le N-1 indicating the size of the ii-th stone on the first pile from the bottom to the top (that is, s0s_{0} is the size of the bottom most stone and sN1s_{N-1} is the size of the stone on top of the pile).

It is guaranteed that every stone size from 00 to N1N-1 appears exactly once, in particular, the stones on pile 00 form a permutation of the numbers from 00 to N1N-1.

Output

For the tt-th test case, on the first line print “Case #t: M” where MM is the number of moves you make to build the pyramid on pile 00. This should be followed by MM lines, each containing two numbers aa and bb such that 0a,bN10\le a,b \le N-1 indicating you move the top stone from pile aa to pile bb.

The moves you output must result in a pyramid on pile 00 for your program to get points on this subtask.

Limits

There are T=100T=100 test cases. In each testcase we have:

  • 1N101 \le N \le 10,
  • K=3K=3.
  • M27000M\le 27\,000: Your solution must use at most 27000 moves.

Example

Input:

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

Output:

Case #0: 6
0 1
0 2
0 2
1 0
2 0
2 0
Case #1: 9
0 1
0 1
0 2
0 1
2 0
1 2
1 0
2 0
1 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: Pyramid of Menkaure (30 points)

As you have proven in the last subtask that you do indeed know how to build a pyramid, Stofl leads to the site of the Pyramid of Menkaure, this is a large pyramid close to the city of Giza.

As Stofl wants the reconstructed pyramid to be ready for the start of IMOI 2024, he asks you to try to keep the number of moves you make as low as possible. In particular, to get full points on this subtask you should not use more than 45004500 moves.

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

There are T=100T=100 test cases. In each testcase we have:

  • 1N5001\le N \le 500,
  • K=3K=3.
  • M27000M\le 27\,000: Your solution must use at most 27000 moves.

Scoring

If you need 45004500 or less moves you get 30 points. If you use more than 45004500 moves, the number of points you get will be

4500/moves30\lfloor 4500/moves\cdot 30 \rfloor

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: The pyramid complex of Dahshur (40 points)

As the final project, Stofl leads you to the pyramid complex of Dashur. As this is a huge pyramid complex, you have more stable patches available than before. That should make it easier right? But Stofl is getting more impatient as IMOI 2024 is approaching soon, so to get full points on this subtask, you should not use more than 25002500 moves.

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

There are T=100T=100 test cases. In each testcase we have:

  • 1N5001 \le N \le 500,
  • K=5K=5.
  • M27000M\le 27\,000: Your solution must use at most 27000 moves.

Scoring

If you need 25002500 or less moves you get 40 points. If you use more than 25002500 moves, the number of points you get will be

2500/moves40\lfloor 2500/moves\cdot 40 \rfloor

Example

Input:

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

Output:

Case #0: 10
0 1
0 2
0 2
0 3
0 3
1 0
3 0
3 0
2 0
2 0
Case #1: 12
0 1
0 2
0 3
0 4
0 1
0 3
4 0
3 0
3 0
1 0
1 0
2 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.


            

        

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

Irrigation

Irrigation canals are a key innovation that allowed the Egyptian agriculture to flourish since the ancient times. In this problem, we will represent the set of irrigation canals in Egypt as an undirected graph, with nodes of the graph corresponding to the junctions and edges of the graph corresponding to the actual canals.

To avoid difficulties with controlling the water flow, there must be no cycles in this graph. In other words, this graph is a forest. Note that it is not necessarily a tree, or in other words it is not necessarily connected. Some junctions might even have no canals connected to them, in other words the graph may have isolated vertices.

Some nodes in this graph correspond to the water sources (typically a junction with a river, or a spring). You need to redesign the existing canal system to maximize the number of junctions that are connected to at least one water source through the canals. In other words, you need to maximize the total size of the connected components containing at least one water source node.

The canal construction is hard work, so you need to do the redesign one improvement at a time. In one improvement, you can choose one junction as the pivot junction, destroy one of the canals connected to the pivot junction, and build a new canal connecting the pivot junction to any other junction. Since we destroy one canal and build one canal, the total number of canals stays the same. You may not introduce cycles when building the new canals, in other words the graph must still be a forest after each improvement. In particular, you may not have more than one canal between the same pair of junctions, or connect a junction to itself. You may not choose a junction with no connected canals as the pivot junction, since there would be no canal to destroy.

You can do multiple improvements, but to avoid concentrating too much construction work in one place, each junction may be touched by improvements at most once. Note that each improvement touches three junctions: the pivot junction, the one it is being disconnected from, and the one it is being connected to.

Your goal is to find such a sequence of improvements that touches each junction at most once, and after all improvements are made the number of junctions that are connected to at least one water source is as high as possible. Note that the number of improvements that you do does not matter, only the end result.

Input/Output

All subtasks have the same input and output format.

Input

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

  • The first line contains three integers NN — the number of junctions, MM — the number of canals, and KK — the number of junctions that are water sources.
  • The next MM lines contain two junction numbers each, denoting two junctions connected by a canal. The junctions are numbered from 00 to N1N-1.
  • The next line contains KK distinct junction numbers that are water sources.

Output

For the tt-th test case, output a line containing “Case #t:”, followed by two integers SS and PP: the number of junctions that you have managed to connect to at least one water source through the canals (directly or indirectly), and the number of improvements that you have made to do so. In the ii-th of the following PP lines, print three integers aia_i, bib_i, and cic_i: the number of the pivot junction, the number of the junction that the canal being destroyed connects the pivot junction to, and the number of the junction that the canal being built connects the pivot junction to.

In case there are multiple solutions that lead to the maximum amount of junctions connected to at least one water source, you may output any such solution.

Subtask 1: Wadi Feiran (4 Points)

In this subtask there are at most three junctions and exactly one water source.

Limits

  • T=100T=100.
  • 1N31 \le N \le 3.
  • 0MN10 \le M \le N-1.
  • K=1K=1.

Example

Input:

1
3 1 1
0 2
1

Output:

Case #0: 2 1
0 2 1

Comment:

After the improvement, junctions 00 and 11 are connected. Since junction 11 is the water source, two out of three junctions are connected to a water source. It is impossible to connect all three.

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: Wadi Abbad (13 Points)

In this subtask there are at most seven junctions and exactly one water source.

Limits

  • T=100T=100.
  • 1N71 \le N \le 7.
  • 0MN10 \le M \le N-1.
  • K=1K=1.

Example

Input:

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

Output:

Case #0: 2 1
0 2 1
Case #1: 4 2
2 1 5
4 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: Wadi El-Kharit (21 Points)

In this subtask there are at most 100100 junctions and exactly one water source.

Limits

  • T=100T=100.
  • 1N1001 \le N \le 100.
  • 0MN10 \le M \le N-1.
  • K=1K=1.

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: Mendesian (24 Points)

In this subtask there are at most 100100 junctions and the water sources are not connected to each other, directly or indirectly.

Limits

  • T=100T=100.
  • 1N1001 \le N \le 100.
  • 0MN10 \le M \le N-1.
  • 1KN1 \le K \le N.
  • There is no sequence of canals connecting one water source to another.

Example

Input:

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

Output:

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

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 5: Nile (38 Points)

In this subtask there are at most 100100 junctions.

Limits

  • T=100T=100.
  • 1N1001 \le N \le 100.
  • 0MN10 \le M \le N-1.
  • 1KN1 \le K \le N.

Example

Input:

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

Output:

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

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).

Donkey Caravan

“Four-leg drive rural power source”: The many advantages of the domesticated donkey as summarised by Fielding & Krause (1998: 109, fig. 7.1).

Scientific depiction of a donkey, taken from “Donkey caravans in Pharaonic Egypt and beyond”.

Caravans played an important role in long-distance desert travel and trade in ancient Egypt. Not on camels though! The camel, originating from North America, has not been domesticated until the 3rd millennium BC. Instead, ancient trade has been served on donkey caravans.

Mouse Binna, the vizier of pharaoh Binothris (ca. 2850 BC to 2760 BC), has been tasked to establish new trade routes for her pharao’s empire.

Trade is centered around an oasis that houses some donkeys and the task is to give instructions to those donkeys. There is a route from trade post A to trade post B with an oasis O in the middle. The distance between A and O is aa, the distance between O and B is bb.

Wares have to be transported between trade post A (aa kilometers left of oasis O) and trade post B (bb kilometers right of oasis O), and in subtasks 3-5 also back from B to A.

A     a      O       b      B
|<==========>|<============>|
|            |              |
Trade      Oasis        Trade
post A   (donkeys)     post B

The transportation needs to happen within one day and that is what the donkeys are for. The NN donkeys (0,1,,N10,1,{\dots},N-1) are initially stationed at the oasis. The ii-th donkey can travel at most did_i kilometers in one day. You are given the d0,d1,dN1d_{0},d_{1}{\dots},d_{N-1} in the input.

You can control the donkeys individually by letting them move left (towards A) or right (towards B) by any possibly non-integer amount, and you may switch directions arbitrarily. Note that after donkey ii travelled his did_i kilometers, it will not be able to move until the end of the day.

Sahara trade routes
  • If a donkey reaches A you can tell it to pick up the wares from the trade post.
  • If two donkeys ii and jj are at the same position and one of the donkeys has the wares, you may switch the wares over from one donkey to the other.
  • If a donkey with the wares reaches B you can drop them off. In subtasks 1 and 2 you are done, in subtasks 3 to 5 you have to go back; after you reached B with the first batch of wares from A, you will then get new wares which you have to transport back to A.

Subtask 1: Bahariya Oasis (10 points)

In this subtask b=0b=0, therefore the oasis and the second trade post are at the same position.

Is it possible to bring wares from A to O with the available donkeys?

  A     a      O
  |<==========>|
  |            |
Trade       Oasis &
post A    Trade post B

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 three numbers NN, aa and bb.
A second line follows with NN integers, distances d0,d1,,dN1d_{0},d_{1},{\dots},d_{N-1} the ii-th donkey can travel.

Output

For the ii-th test case, output a line “Case #i: YES” if it’s possible to send the donkeys from AA to BB or “Case #i: NO” if not.

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1N1001 \le N \le 100
  • 0a1000 \le a \le 100
  • b=0b = 0
  • 0di1000 \le d_i \le 100 for all 0iN10 \le i \le N-1.

Example

Input:

3
1 3 0
5
1 3 0
6
3 4 0
4 5 4

Output:

Case #0: NO
Case #1: YES
Case #2: YES

Comment:

Case #0: The distance is 33 km and the donkey can travel at most 55 km. This is enough to reach A, but it is not enough to go back to O. Therefore this is impossible and the output is NO.
Case #1: Same as before, but the donkey with 66 km can go all the way to A (33 km) and back (another 33 km), therefore this is possible and the output is YES.
Case #2: Take the donkey 11 and move 44 km left, take the wares and move 1km1km to the right, which uses up all the available d1=5d_{1}=5 km. Take donkey 22 and move left by 33 km, pick up the wares, and move right by 11 km. Finally, take donkey 00, move left by 22 km, pick up the wares and move right by 22 km. We end up at trade post B where we can deliver the wares.
A           O
W-----------+-----------
v<= <= <= <=| donkey 1
|=>v        | d_1=5
|--W--------|-----------
|  v<= <= <=| donkey 2
|   =>v     | d_2=4
|-----W-----|-----------
|     v<= <=| donkey 2
|      => =>v d_0=4
+-----------W-----------

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: Dakhla Oasis (10 points)

This time trading post B might be at a different location than the oasis. Can we to transport the wares from A to B?

A     a      O       b      B
|<==========>|<============>|
|            |              |
Trade      Oasis        Trade
post A   (donkeys)     post B

Input & Output

Same as subtask 1.

Limits

Same as subtask 1, except that for bb we have 0b1000 \le b \le 100.

Example

Input:

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

Output:

Case #0: YES
Case #1: NO
Case #2: YES
Case #3: YES

Comment:

Case #0:

5  4  3  2  1  0 ... 9
+--------------|         d0=6
+-->           |
   +-----------|         d1=5
   +-->        |
      +--------|         d3=4
      +-->     |
         +-----|         d2=4
         +---->|
               |--...->  d4=9

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: Karga Oasis (20 points)

In this and the next subtasks Mouse Binna has to bring the wares from A to B and back.

Additionally, aa and bb are not always given, instead you have to find the maximal values for which it is possible to plan a successul trade route.

In this subtask in particular we have a=0a=0 so we are dealing with the following situation:

      O       b       B
      |==============>| first go A->B,
      |<==============| then B->A.
      |               |
   Oasis &          Trade
Trade post A       post B

Input

The first line of the test case contains the single integer NN.
A second line follows with NN integers, distances d0,d1,,dN1d_{0},d_{1},{\dots},d_{N-1} the ii-th donkey can travel.

Output

For the ii-th test case, output a line “Case #i: b”, where bb is the largest possible distance such that it there exists a trade route from A to B and back.

Your answer is accepted if the absolute error is below 10610^{-6}. In other words, if your output is xx and the correct solution is yy, your output is correct if and only if xy106|x-y| \le 10^{-6}.

Limits

There are T=100T=100 test cases. In each test case we have:

  • 1N1001 \le N \le 100
  • 0di1000 \le d_i \le 100 for all 0iN10 \le i \le N-1.

Example

Input:

3
1
5
2
3 3
16
7 6 6 5 1 4 3 1 1 1 1 1 1 1 1 4

Output:

Case #0: 2.5
Case #1: 2.25
Case #2: 6.2812347

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: Karga Oasis (35 points)

Same as subtask 3, but in this subtask we have b=0b=0 so we are dealing with the following situation:

   A       a       O
   |==============>| first go A->B,
   |<==============| then B->A.
   |               |
Trade           Oasis &
post A       Trade post B

Input

Same as subtask 3.

Output

For the ii-th test case, output a line “Case #i: a”, where aa is the largest possible distance such that it there exists a trade route from A to B and back.

Your answer is accepted if the absolute error is below 10610^{-6}.

Limits

Same as subtask 3.

Example

Input:

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

Output:

Case #0: 7
Case #1: 5.02222222
Case #2: 5.05882353
Case #3: 3.14141414
Case #4: 2.77777778
Case #5: 3
Case #6: 3.09803922

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 5: El Fashir Oasis (25 points)

This time we are dealing with the general case:

A     a      O       b      B
|============|=============>| first go A->B,
|<===========|==============| then B->A.
|            |              |
Trade      Oasis        Trade
post A   (donkeys)     post B

Distance bb is fixed and given in the input. Help Binna to find the maximum distance aa such that trade is possible.

Input

The first line of the test case contains two integers NN and bb.
A second line follows with NN integers, distances d0,d1,,dN1d_{0},d_{1},{\dots},d_{N-1} the ii-th donkey can travel.

Output

For the ii-th test case, output a line “Case #i: a” where aa is the largest possible distance such that it there exists a trade route from A to B and back. If it is not possible to make a trade route, print -1 instead.

Your answer is accepted if the absolute error is below 10610^{-6}.

Input:

4
3 3
9 11 5
5 1
5 3 3 5 5
4 1
8 6 3 2
5 5
5 3 3 5 5

Output:

Case #0: 5.8
Case #1: 4.21568627
Case #2: 4.88888889
Case #3: -1

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).

1H

The homework part of round1 (1H) consists of 4 tasks, each of which is worth 25 points. You can gain a maximum of 100 points counting towards your score of the regular round.



This helps you get familiar with our grading system which we will use in all our events after round1, including workshops, camp, round2 and the finals.

You can submit in C++ (recommended), Java or Python.

C++:If you don’t have a setup already, we recommend installing VSCode.
Java:Read Java on the SOI Grader.
Python:Read Python on the SOI Grader.

For 1H you can discuss solutions with friends or publicly on Discord, as long as you don’t share source code. We are also happy to help you! If you need help with the grading system or have questions regarding the theory or tasks, don’t hesitate to ask here or in Discord.

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

Junior Ranking

RankUsernameTotal (600)harvest (100)exhibition (100)cruisetrip (100)calendar (100)labyrinth (100)pyramids (100)
loading ...

Regular Ranking

RankUsernameTotal (600)calendar (100)labyrinth (100)pyramids (100)irrigation (100)caravan (100)1h (100)
loading ...