First Round SOI 2023/2024 - Swiss Olympiad in Informatics

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.

Category	Task	Total	Subtask 1	Subtask 2	Subtask 3	Subtask 4	Subtask 5
Junior only	harvest	‒/100	‒/17	‒/18	‒/19	‒/21	‒/25
Junior only	exhibition	‒/100	‒/7	‒/23	‒/31	‒/39
Junior only	cruisetrip	‒/100	‒/20	‒/25	‒/25	‒/30
Both	calendar	‒/100	‒/16	‒/12	‒/21	‒/18	‒/33
Both	labyrinth	‒/100	‒/12	‒/11	‒/19	‒/26	‒/32
Both	pyramids	‒/100	‒/14	‒/16	‒/30	‒/40
Regular only	irrigation	‒/100	‒/4	‒/13	‒/21	‒/24	‒/38
Regular only	caravan	‒/100	‒/10	‒/10	‒/20	‒/35	‒/25
Regular only	1h	‒/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 $T$ . The $T$ test cases follow in the following format:

The first line of the test case contains a single integer number

n

— the total number of baskets.

The second line contains

n

integer numbers:

a_i

— the number of items in the

i

-th basket.

Output

For the $i$ -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=100$ test cases. In each test case we have:

$1 \le n \le 1000$
$0 \le a_i \le 1000$

Example

Input:

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.

Output

Source Code

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 $i$ -th test case, output a line “Case #i: x” where $x$ 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=100$ test cases. In each test case we have:

$1 \le n \le 1000$
$0 \le a_{0}\le 1000$
$a_i = 1$ for all $i>0$

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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 $2$ .

Input & Output

Same as subtask 2.

Limits

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

$1 \le n \le 1000$
$0 \le a_{0}\le 1000$
$|a_i - a_j| \le 2$ for all $i,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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$ test cases. In each test case we have:

$1 \le n \le 1000$
$0 \le a_i \le 1000$ .

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$ test cases. In each test case we have:

$1 \le n \le 10^{5}$
$0 \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.

Do not navigate away while your solution is running.

Output

Source Code

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

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 $T$ . $T$ test cases follow of the following format:

The first line contains two integers $K$ and $N$ , the number of painters, and the total number of paintings.
Each of the $K$ following lines contains a number $N_i$ , followed by $N_i$ numbers $v_{i, 0},v_{i, 1},{\dots},v_{i, N_i-1}$ , the values in Egyptian pounds of all the $N_i$ paintings of painter $i$ .

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

Output

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

Limits

$T=100$
$K=1$
$2 \le N_i$ for all $0\le i<N$
$N = \sum_i N_i$
$N \le 1000$
$1 \le v_{i, j} \le 10^{5}$ for all $0\le i<N$ , $0\le j<N_i$

Example

Input:

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=7

Egyptian pounds, so we have to take both.

Case #1: The two most expensive paintings have value

8+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.

Do not navigate away while your solution is running.

Output

Source Code

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=2$ .

Limits

$T=100$
$K=2$
$2 \le N_i$ for all $0\le i<N$
$N = \sum_i N_i$
$N \le 5000$
$1 \le v_j \le 10^{5}$ for all $0\le j<N_i$

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$
$1 \le K \le 500$
$2 \le N_i$ for all $0\le i<N$
$N = \sum_i N_i$
$N \le 1000$
$1 \le v_j \le 10^{5}$ for all $0\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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$
$1 \le K \le 40000$
$2 \le N_i$ for all $0\le i<N$
$N = \sum_i N_i$
$N \le 80000$
$1 \le v_j \le 10^{5}$ for all $0\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.

Do not navigate away while your solution is running.

Output

Source Code

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

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 $N$ rows and $M$ columns with islands positioned on some grid cells. Every $10$ 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 $T$ . The $T$ test cases follow in the following format:

The first line contains two integers $N$ and $M$ , the number of rows and columns of the grid respectively.
The next $N$ lines will contain $M$ 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 $t$ -th test case, output a line “Case #t:”, followed by the number $L$ , 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=100$
$M=2$
$1 \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

1

cell left and

2

cells down. The total length is

4

Case #1: One of the optimal paths starts on the top right cell then goes

3

cells down,

1

cell left and

1

cell down. The total length is

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.

Do not navigate away while your solution is running.

Output

Source Code

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 $20$ columns on the map.

Limits

$T=100$
$2 \le M \le 20$
$1 \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

2

cells to the right, then

2

cells down, then

2

cells left and ends up on the bottom left cell. The total length is

7

Case #1: One of the optimal paths starts on the

3

left,

1

down,

1

left,

1

down,

2

right,

1

down,

3

right,

1

down and

1

left for a total length of

13

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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$
$2 \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

1

cell to the right, then

2

cells down, then

1

cell right, then

2

cells down and ends up on the

3

-rd bottom cell. The total length is

7

Case #1: The optimal path starts on the

6

-th cell and goes

4

down,

1

right and

2

down for a total length of

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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$
$2 \le N \cdot M \le 5 \cdot 10^{6}$

Example

Same as Subtask $2$ .

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

Download input again

You have 5 minutes and 0 seconds left.

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

Do not navigate away while your solution is running.

Output

Source Code

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

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 $n$ days. She still has $m$ event to plan before the competition starts. The $i$ -th event starts on day $l_i$ and ends on day $r_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 $k$ 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 $i$ -th day of preparation she will do the necessary work to plan the $j$ -th day of IMOI, where $0 \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 $n-1$ and every day loses one productivity point up to her last preparation day where she has productivity score of $0$ .

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 $a$ tasks on a day with productivity $b$ , her score for that day is $a \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=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. $l_i=0$ for all $0 \le i \le m-1$ .

Input

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

The first line of the test case contains three integer numbers

n

m

and

k

— the number of days, the number of IMOI events and the length of the camp.

The following

m

lines contains two integer numbers in each:

l_i

r_i

— the

i

-th event starts on the

l_i

-th day and ends on the

r_i

-th day (inclusive).

Output

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

Limits

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

$1 \le n \le 1000$
$0 \le m \le 1000$
$k = 0$
$0 = l_i \le r_i < n$ for all $0 \le i \le m-1$ .

Example

Input:

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][0,1,3,2]. That way Binna will get 666 points for the first event (3+2+1)(3 + 2 + 1)(3+2+1), 555 points for the second event (3+23+23+2) and 333 points for the third event. So the total number of points is 141414.
Case #1: The optimal order to plan the days in is [0,1,2][0,1, 2][0,1,2]. That way Binna will get 3 points for the first event, 333 points for the second event and 333 points for the third event. So the total number of points is 999.
Case #2: The optimal order to plan the days in is [0,1,2][0, 1, 2][0,1,2]. That way Binna will get 333 points for the first event and 333 points for the second event. So the total number of points is 666.

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.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2: Hard Times (12 points)

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

Input & Output

Same as subtask 1.

Limits

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

Example

Input:

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][0,3,1,2]. That way Binna will get 222 points for the first event, 444 points for the second event and 333 points for the third event. So the total number of points is 999.
Case #1: The optimal order to plan the days in is [1,2,0][1, 2, 0][1,2,0]. That way Binna will get 222 points for the first event, 333 points for the second event and 333 points for the third event. So the total number of points is 888.
Case #2: The optimal order to plan the days in is [2,1,0][2, 1, 0][2,1,0]. That way Binna will get 333 points for the first event and 333 points for the second event. So the total number of points is 666.

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.

Do not navigate away while your solution is running.

Output

Source Code

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 $n \le 10^{5}$ and $m \le 10^{5}$ .

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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 $0 \le k \le n$ .

Example

Input:

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][0,1,3,2]. That way Binna will get 555 points for the camp planning, 111 points for the first event, 555 points for the second event and 333 points for the third event. So the total number of points is 141414.
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][1,2,0]. That way Binna will get 333 points for the camp planning, 222 points for the first event, 333 points for the second event and 333 points for the third event. So the total number of points is 111111.
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][2,1,0]. That way Binna will get 222 points for the camp planning, 333 points for the first event and 333 points for the second event. So the total number of points is 888.

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.

Do not navigate away while your solution is running.

Output

Source Code

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 $n \le 10^{5}$ and $m \le 10^{5}$ .

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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

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 $N$ chambers. There are $N-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 $T$ . This is followed by $T$ test cases in the following format: The first line of the test case contains $N$ , the number of chambers in the labyrinth.

$N$ lines follow, each line has two characters $m_i$ $t_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 $N-1$ more lines follow, describing the structure of the labyrinth. Each line with two integers $v_i$ $u_i$ , separated by a space, representing a corridor between the chamber $v_i$ and $u_i$ .

Output

For the $i$ -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 $0$ . Every other chamber is connected to the central chamber.

Limits

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

$1 \le N \le 100\,000$
$u_i = 0$

Example

Input:

Output:

Case #0: 2
Case #1: 0

Comment:

Case #0:
In this example, the tomb has four chambers, chamber 000 centered in the middle and three chambers connected to it.
We need to move the torch away from chamber 111, and move a torch into chamber 333. Unfortunately, we cannot directly do this.
Instead, we first move the torch from chamber 111 to chamber 000 getting chamber 111 correct, but chamber 000 wrong.
Then move the torch from chamber 000 to chamber 333.
Chamber 000 has no torch anymore, but chamber 333 has, as desired by the map.
So the solution is 2 as we moved a torch through corridor 1−01-01−0 and through 0−30-30−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.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2: Dark Tomb (11 points)

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

Limits

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

$1 \le N \le 100\,000$
$c_i = 1$ for one $i$ and $c_i = 0$ for all else
$t_i = 1$ for one $i$ and $t_i = 0$ for all else

Example

Input:

Output:

Case #0: 3
Case #1: 2

Comment:

Case #0:
The labyrinth is ordered on a line like this: 0−1−2−30-1-2-30−1−2−3.
We need to move the torch from chamber 333 all the way to chamber 000, 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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$ test cases. In every test case:

$1 \le N \le 1\,000\,000$
$u_i = v_i - 1$ for $1 \le u_i \le N-1$

Example

Input:

Output:

Case #0: 3
Case #1: 6

Comment:

Case #0:
Similar as Case #0 in subtask 2.
Case #1:
Move the torch from chamber 222 to chamber 444, passing through 222 corridors.
Then move the torch from chamber 111 to chamber 444, passing through 222 corridors again.
Finally, move the torch from chamber 000 to chamber 333, passing through 222 corridors again.
Since the corridors 1−21-21−2 and 2−32-32−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.

Do not navigate away while your solution is running.

Output

Source Code

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 $h$ 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 $h-1$ chambers. Starting from the second chamber of this ‘left line’, there is another line, with $h-2$ chambers. Continue like this until the last chamber of this ‘left line’ (here there is no further line, as it would contain $0$ chambers). In total there will be $n = \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=100$ test cases. In every test case:

$1 \le N \le 1\,000$

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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=100$ test cases. In every test case:

$1 \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.

Do not navigate away while your solution is running.

Output

Source Code

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

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 $N$ 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,{\dots},N-1$ ) and Stofl notices that there is exactly one stone of every size (in particular that means that there are exactly $N$ stones).

Next to the pile of stones there are $K-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 $K$ 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 $N-1$ goes on the bottom, the stone with size $N-2$ on top of it, then the stone with size $N-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 $K$ stable patches.

Input

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

The first line of each test case contains three numbers $N,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 $K$ lines will describe the piles of stone. Each of these lines starts with a number $r$ with $0\le r\le N$ , the number of stones on this pile, followed by $r$ numbers $s_{0},s_{1},{\dots}s_{r-1}$ where $0 \le s_i\le N-1$ indicating the size of the $i$ -th stone on this pile from the bottom to the top (that is, $s_{0}$ is the size of the bottom most stone and $s_{r-1}$ is the size of the stone on top of the pile).

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

It is guaranteed that every stone size from $0$ to $N-1$ appears exactly once.

Output

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

Limits

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

$1 \le N \le 1000$ ,
$2\le K\le 10$ ,
$1\le M\le 10000$ .

Example

Input:

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

2

and the second pile has two stones, the stone of size

0

on the bottom and the stone of size

1

on top of it. We get three instructions from Stofl. With the first instruction, we move the stone of size

2

from pile

0

to pile

1

, then we move the same stone back to pile

0

(as we put it on the top of pile

1

when we moved it there). With the third instruction, we move stone

1

from pile

1

to pile

0

. Thus we end up with pile

0

having two stones, the stone of size

2

on the bottom and the stone of size

1

on top, and pile

1

having only the stone of size

0

Case #1: Here we have three piles of stones, the first one having three stones, the stone of size

0

at the bottom, the stone of size

3

on top of it and the stone of size

1

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

4

on the bottom and the stone of size

2

on top of it. We now get five instructions from Stofl. With the first instruction, we move the stone of size

1

to the empty pile

1

. Then we move the stone of size

3

to pile

2

and the stone of size

1

back from pile

1

to pile

0

(now sitting on top of the stone of size

0

). Then we move the stone of size

3

from pile

2

to the (again empty) pile

1

and do the same with the stone of size

2

(placing it on top of the stone of size

3

). Thus we are left with the stones of size

0

and

1

on pile

0

, the stones of size

3

and

2

on pile

1

and the stone of size

4

on pile

2

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

Download input again

You have 5 minutes and 0 seconds left.

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

Do not navigate away while your solution is running.

Output

Source Code

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 $0$ 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 $T$ . The $T$ test cases follow in the following format:

The first line of each test case contains two numbers $N,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 $N$ numbers, separated by spaces, $s_{0},s_{1},{\dots},s_{N-1}$ where $0 \le s_i\le N-1$ indicating the size of the $i$ -th stone on the first pile from the bottom to the top (that is, $s_{0}$ is the size of the bottom most stone and $s_{N-1}$ is the size of the stone on top of the pile).

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

Output

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

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

Limits

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

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

Example

Input:

Output:

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.

Do not navigate away while your solution is running.

Output

Source Code

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 $4500$ moves.

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

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

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

Scoring

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

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

Do not navigate away while your solution is running.

Output

Source Code

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 $2500$ moves.

Input

Same as Subtask 2

Output

Same as Subtask 2

Limits

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

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

Scoring

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

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

Do not navigate away while your solution is running.

Output

Source Code

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

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 $T$ . $T$ test cases follow of the following format:

The first line contains three integers $N$ — the number of junctions, $M$ — the number of canals, and $K$ — the number of junctions that are water sources.
The next $M$ lines contain two junction numbers each, denoting two junctions connected by a canal. The junctions are numbered from $0$ to $N-1$ .
The next line contains $K$ distinct junction numbers that are water sources.

Output

For the $t$ -th test case, output a line containing “Case #t:”, followed by two integers $S$ and $P$ : 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 $i$ -th of the following $P$ lines, print three integers $a_i$ , $b_i$ , and $c_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=100$ .
$1 \le N \le 3$ .
$0 \le M \le N-1$ .
$K=1$ .

Example

Input:

Output:

Case #0: 2 1
0 2 1

Comment:

After the improvement, junctions

0

and

1

are connected. Since junction

1

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.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 2: Wadi Abbad (13 Points)

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

Limits

$T=100$ .
$1 \le N \le 7$ .
$0 \le M \le N-1$ .
$K=1$ .

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 3: Wadi El-Kharit (21 Points)

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

Limits

$T=100$ .
$1 \le N \le 100$ .
$0 \le M \le N-1$ .
$K=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.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4: Mendesian (24 Points)

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

Limits

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

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 5: Nile (38 Points)

In this subtask there are at most $100$ junctions.

Limits

$T=100$ .
$1 \le N \le 100$ .
$0 \le M \le N-1$ .
$1 \le K \le N$ .

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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

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 $a$ , the distance between O and B is $b$ .

Wares have to be transported between trade post A ( $a$ kilometers left of oasis O) and trade post B ( $b$ 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 $N$ donkeys ( $0,1,{\dots},N-1$ ) are initially stationed at the oasis. The $i$ -th donkey can travel at most $d_i$ kilometers in one day. You are given the $d_{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 $i$ travelled his $d_i$ kilometers, it will not be able to move until the end of the day.

If a donkey reaches A you can tell it to pick up the wares from the trade post.
If two donkeys $i$ and $j$ 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=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 $T$ . $T$ test cases follow in the following format:

The first line of the test case contains three numbers

N

a

and

b

A second line follows with

N

integers, distances

d_{0},d_{1},{\dots},d_{N-1}

the

i

-th donkey can travel.

Output

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

Limits

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

$1 \le N \le 100$
$0 \le a \le 100$
$b = 0$
$0 \le d_i \le 100$ for all $0 \le i \le N-1$ .

Example

Input:

Output:

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

Comment:

Case #0: The distance is 333 km and the donkey can travel at most 555 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 666 km can go all the way to A (333 km) and back (another 333 km), therefore this is possible and the output is YES.
Case #2: Take the donkey 111 and move 444 km left, take the wares and move 1km1km1km to the right, which uses up all the available d1=5d_{1}=5d1​=5 km. Take donkey 222 and move left by 333 km, pick up the wares, and move right by 111 km.  Finally, take donkey 000, move left by 222 km, pick up the wares and move right by 222 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.

Do not navigate away while your solution is running.

Output

Source Code

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 $b$ we have $0 \le b \le 100$ .

Example

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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, $a$ and $b$ 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=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

N

A second line follows with

N

integers, distances

d_{0},d_{1},{\dots},d_{N-1}

the

i

-th donkey can travel.

Output

For the $i$ -th test case, output a line “Case #i: b”, where $b$ 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 $10^{-6}$ . In other words, if your output is $x$ and the correct solution is $y$ , your output is correct if and only if $|x-y| \le 10^{-6}$ .

Limits

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

$1 \le N \le 100$
$0 \le d_i \le 100$ for all $0 \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.

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4: Karga Oasis (35 points)

Same as subtask 3, but in this subtask we have $b=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 $i$ -th test case, output a line “Case #i: a”, where $a$ 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 $10^{-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.

Do not navigate away while your solution is running.

Output

Source Code

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 $b$ is fixed and given in the input. Help Binna to find the maximum distance $a$ such that trade is possible.

Input

The first line of the test case contains two integers

N

and

b

A second line follows with

N

integers, distances

d_{0},d_{1},{\dots},d_{N-1}

the

i

-th donkey can travel.

Output

For the $i$ -th test case, output a line “Case #i: a” where $a$ 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 $10^{-6}$ .

Input:

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.

Do not navigate away while your solution is running.

Output

Source Code

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

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

Rank	Username	Total (600)	harvest (100)	exhibition (100)	cruisetrip (100)	calendar (100)	labyrinth (100)	pyramids (100)
	loading ...

Regular Ranking

Rank	Username	Total (600)	calendar (100)	labyrinth (100)	pyramids (100)	irrigation (100)	caravan (100)	1h (100)
	loading ...