First Round SOI 2020/2021 - 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	stairracing	‒/100	‒/25	‒/25	‒/25	‒/25
Junior only	secretcode	‒/100	‒/25	‒/25	‒/25	‒/25
Both	bamboo	‒/100	‒/15	‒/25	‒/25	‒/35
Both	batteryfix	‒/100	‒/10	‒/10	‒/10	‒/70
Both	lilypads	‒/100	‒/15	‒/25	‒/20	‒/40
Regular only	changifalls	‒/100	‒/15	‒/15	‒/20	‒/25	‒/25
Regular only	satay	‒/100	‒/20	‒/20	‒/10	‒/50
Regular only	muffins	‒/100	‒/25	‒/25	‒/50

Stair Racing

Ready to scale 1336 steps, 226 metres, 73 storeys? Register now for the Swissôtel Vertical Marathon.

The Asian tower running scene began in Raffles City, Singapore in 1987, where Swissotel The Stamford hotel was chosen as the venue of a vertical marathon across a mere 1336 staircase steps.

Mouse Binna is the main organizer of such an event. For this year’s edition, she’d like to organize a triathlon: the racing track starts with a vertical downward section, followed by a horizontal section, followed by a vertical upward section. She has already chosen a street through Singapore where she wants to host the event. On each side of the street, there are exactly $N$ skyscrapers at unit distance such that each skyscraper on one side of the street is facing another skyscraper on the other side. Mouse Binna knows the height of each skyscraper and she will choose a racing track that has the largest total length, starting on the roof of one of the skyscrapers, going down the stairs to the street, where it will lead to a skyscraper on the other side of the street and end on its roof. The total length of the racing track is given by the sum of heights of the skyscrapers and their distance along the street.

Subtask 1: A very short street (25 Points)

Mouse Binna has chosen a street with only one skyscraper on each side.

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 the length $N$ of the street. (Here, $N=1$ .)
The second line contains the height $a$ of the skyscraper on one side of the street.
The third line contains the height $b$ of the skyscraper on the other side of the street.

Output

You should output $T$ lines, one for each test case. For the $i$ -th test case, output “Case #i: l”, where $l$ is equal to the maximum length of the racing track Mouse Binna can choose.

Limits

$T = 100$
$N = 1$
$1\le a, b\le 1336$

Example

Input:

Output:

Case #0: 5
Case #1: 1337

Comment:

In both cases, there are exactly two possible tracks, both with the same total length. (The racing tracks start on the roof of one of the two skyscrapers, go down to the street and up to the roof of the other skyscraper.)

Interactive visualization

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: A short street (25 Points)

Mouse Binna has chosen a street with two skyscrapers on each side.

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 the length $N$ of the street. (Here, $N=2$ .)
The second line contains the heights $a_{0}$ and $a_{1}$ of the skyscrapers on one side of the street.
The third line contains the heights $b_{0}$ and $b_{1}$ of the skyscrapers on the other side of the street.

Output

Same as subtask 1 – $T$ lines of the form “Case #i: l”, where $l$ is the maximum total length.

Limits

$T = 100$
$N = 2$
$1\le a_i, b_i\le 10^{6}$

Examples

Input:

Output:

Case #0: 3
Case #1: 1338
Case #2: 2672

Comment:

Case #0: A longest possible track may start on a skyscraper at position 000, go down to the street, move to position 111 and up the skyscraper, for a total length of 1+1+1=31+1+1=31+1+1=3.
Case #1: We choose one high and one not-so-high skyscraper and connect them with a horizontal segment of length 111 for a total length of 1336+1+1=13381336+1+1=13381336+1+1=1338. (Note that it is impossible to use both high skyscrapers in the racing track, as they are on the same side of the street.)
Case #2: Both skyscrapers of height 133613361336 are included in the racing track, but there is no horizontal segment.

Interactive visualization

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: A longer street (25 Points)

Mouse Binna has chosen a street with up to $1000$ skyscrapers on each side.

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 the length $N$ of the street.
The second line consists of $N$ numbers $a_i$ describing the heights of the skyscrapers on one side of the street.
The third line consists of $N$ numbers $b_i$ describing the heights of the skyscrapers on the other side of the street.

Limits

$T = 100$
$1\le N\le 1000$
$1\le a_i, b_i\le 10^{6}$

Output

Same as subtasks 1 and 2.

Examples

Input:

Output:

Case #0: 11

Interactive visualization

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 long street (25 Points)

Mouse Binna has chosen a street with up to $10^{5}$ skyscrapers on each side.

Input and Output

Same as subtask 3.

Limits

$T = 100$
$1\le N\le 10^{5}$
$1\le a_i, b_i\le 10^{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

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

Secret Code

Mouse Stofl has recently been interested in the field of cryptography. After learning about different types of encryption protocols, he has decided to invent his own, Stofl’s Secret Hash (SSH). Ideally, the decryption process should be as simple as possible, so that as many mice as possible could receive secure messages. He spent so much time coming up with a complicated encoding method, that he doesn’t know if a simple decoding method even exists.

Stofl decides that a decoding method is simple if he can replace each letter of the alphabet with another letter to retrieve the decrypted cleartext from the encrypted message. This replacement policy is called the translation table of an encryption. For example, if we are given the sentence: “I like cats” by using a translation table that replaces each c with an h, we recieve the sentence: “I like hats”.

As he wants to give the decoding table to his friends, he found a nice way to write them down. He first writes down the character which a will be replaced with, then the one b will be replaced with and so on. So if his translation table is cca, then a gets replaced with c, b gets replaced with c and c gets replaced with a.

Subtask 1 (25 points)

Mouse Stofl would like to know if a simple decoding exists. He decides to start with words only containing the letters a and b.

Input

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

The first and only line of the testcase consists of two strings. The first string is the encrypted message. The second string is the decrypted cleartext.

Output

For the $i$ -th test case, if a valid translation table exists, output a line “Case #i: Yes”, followed by a line with a valid translation table. Otherwise, output a line “Case #i: No”.

For each translation table, only the first two letters are considered.

Limits

There are $T=100$ test cases. In every test case, $1 \le L \le 1000$ , where $L$ is the number of letters in a word.

Each word only contains the letters a and b.

Example

Input:

4
abb baa
aaa aba
aba aaa
bbb bbb

Output:

Case #0: Yes
ba
Case #1: No
Case #2: Yes
aa
Case #3: Yes
ab

Comment:

Case #0: Each a is replaced with a b and each b is replaced with an a. This results in the translation table ba.
Case #1: A valid translation table does not exist.
Case #2: Both a and b are replaced with a.
Case #3: Although a does not appear in the encrypted word, a replacement letter must be given. Both ab and bb are valid translation tables.

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

Stofl is now ready to check his encoding methods on words with any letters of the alphabet.

Input

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

The first and only line of the testcase consists of two strings. The first string is the encrypted message. The second string is the decrypted cleartext.

Each word consists of lowercase letters.

Output

For the $i$ -th test case, if a valid translation table exists, output a line “Case #i: Yes”, followed by a line with a valid translation table. Otherwise output a line “Case #i: No”. Note that you need to print the whole translation table (that is, for all lowercase letters), even if some letters are unused.

Limits

There are $T=100$ test cases. In every test case, $1 \le L \le 1000$ , where $L$ is the number of letters in a word.

Example

Input:

4
abc cab
aac abc
xyz aaa
abc xyz

Output:

Case #0: Yes
cabaaaaaaaaaaaaaaaaaaaaaaa
Case #1: No
Case #2: Yes
aaaaaaaaaaaaaaaaaaaaaaaaaa
Case #3: Yes
xyzaaaaaaaaaaaaaaaaaaaaaaa

Comment:

Case #0: a is replaced by c, b is replaced by a and c is replaced by b. All other letters may be replaced by any other letter to result in a valid translation table.

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

While Stofl invented his encryption protocol, Binna independently developed her own. Both mice decide that a simple decoding method is preferable, however, they disagree on which encryption method should be used. They now want to find translation tables such that their encrypted words decrypt to the same words. Additionally, they want these words to have as many unique letters as possible.

Input

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

The first line contains two integers $N$ and $L$ , the number of encrypted words (here, always 2) and the length of each word. $N$ lines follow describing the encrypted word of each mouse.

Each word consists of lowercase letters.

Output

For the $i$ -th test case, output a line “Case #i: U D”, where $U$ is an integer representing the number of unique letters in the decrypted word and $D$ is the decrypted word. After that, $N$ lines follow, with the translation table of each mouse.

Limits

There are $T=100$ test cases. In every test case, $N = 2$ and $1 \le L \le 1000$ , where $L$ is the number of letters in a word.

Example

Input:

2
2 4
milk
lime
2 5
motor
happy

Output:

Case #0: 4 cake
aaaaaaaaaaekcaaaaaaaaaaaaa
aaaaeaaaaaackaaaaaaaaaaaaa
Case #1: 3 caaar
aaaaaaaaaaaacaaaaraaaaaaaa
aaaaaaacaaaaaaaaaaaaaaaara

Comment:

Case #0: Any string that has four unique letters and for which valid translation tables exist from the strings milk and lime to the given string are correct answers. This is just one example.

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

Mouse Binna and Stofl are so fascinated by the topic that they decide to tell all their friends. Their friends find it equally fascinating and decide to invent their own encryption protocols. Once again, they want to find translation tables and words which can be decrypted from the encrypted words. As before, they want the decodings to have as many unique letters as possible.

Input

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

The first line contains two integers $N$ and $L$ , the number of encrypted words and the length of each word. $N$ lines follow describing the encrypted word of each mouse.

Each word consists of lowercase letters.

Output

Limits

There are $T=100$ test cases. In every test case, $2 \le N \le 100$ and $1 \le L \le 1000$ , where $L$ is the number of letters in a word.

Example

Input:

1
3 5
motor
happy
ember

Output:

Case #0: 2 aaaar
aaaaaaaaaaaaaaaaaraaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaara
aaaaaaaaaaaaaaaaaraaaaaaaa

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

Bamboo

This year’s IOI will take place in Singapore and thus Mouse Binna is eager to learn about the traditional way of cutting bamboo. In particular, she wants to train cutting bamboo sticks arranged in a line to a certain height pattern. For the cutting work, she possesses a dao, a single-edged sword from Singapore whose primary use is chopping bamboo. Because there are many bamboo sticks to cut and swinging the dao costs a lot of energy, she would like to perform as few swings as possible. However, cutting the bamboo sticks to the patterned height takes up all of her concentration and she cannot figure out the minimal number of swings needed to cut down the bamboo sticks at the same time. Please help her with this calculation!

You are given the list of the heights in the pattern, $h_{0}, h_{1}{\dots} h_{N-1}$ . Binna is still a beginner in bamboo cutting and thus she can only perform a simple strike technique which allows her, for any $i$ , $j$ and $h$ , to cut all bamboo sticks between $h_i$ and $h_{j-1}$ down to the height $h$ . (Formally, the new height for the bamboo sticks in range $i,i+1,\dots,j-1$ is the minimum of the previous height and the cutting height $h$ .) Initially, all bamboo sticks have infinite height.

Subtask 1: Three Bamboos (15 points)

When Mouse Binna is starting her training, her endurance is still very weak and she limits the number of bamboo sticks to $N=3$ .

Input

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

The first line of the test case contains $N$ , the length of the pattern.
On the following line, a list is given containing the heights $h_{0}, h_{1}{\dots} h_{N-1}$ of the pattern.

Output

For the $i$ -th test case, output a line “Case #i: S”, where $S$ is the minimal number of swings that Binna needs to accomplish her task.

Limits

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

$N = 3$
$1 \le h_i \le 100\,000$ .

Example

Input:

Output:

Case #0: 2
Case #1: 3

Comment:

Case #0:
Cut 000: from h0h_{0}h0​ to h2h_{2}h2​ at height 333 resulting in [3,3,3][3, 3, 3][3,3,3]
Cut 111: from h1h_{1}h1​ to h1h_{1}h1​ at height 222 resulting in [3,2,3][3, 2, 3][3,2,3]
Case #1:
Cut 000: from h0h_{0}h0​ to h2h_{2}h2​ at height 777 resulting in [7,7,7][7, 7, 7][7,7,7]
Cut 111: from h0h_{0}h0​ to h0h_{0}h0​ at height 555 resulting in [5,7,7][5, 7, 7][5,7,7]
Cut 222: from h2h_{2}h2​ to h2h_{2}h2​ at height 111 resulting in [5,7,1][5, 7, 1][5,7,1]

Interactive visualization

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 Heights (25 points)

After Mouse Binna successfully completed her first training, she would now like to concentrate on long swings. She doesn’t feel completely comfortable with the dao yet and therefore decides to set the pattern heights to either $1$ or $2$ .

Input/Output

Same as in subtask 1.

Limits

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

$N \le 300\,000$
$1 \le h_i \le 2$ .

Example

Input:

2
6
1 1 1 1 2 1
5
2 2 1 1 1

Output:

Case #0: 3
Case #1: 2

Comment:

Case #0:
Cut 000: from h0h_{0}h0​ to h5h_{5}h5​ at height 222 resulting in [2,2,2,2,2,2][2, 2, 2, 2, 2, 2][2,2,2,2,2,2]
Cut 111: from h5h_{5}h5​ to h5h_{5}h5​ at height 111 resulting in [2,2,2,2,2,1][2, 2, 2, 2, 2, 1][2,2,2,2,2,1]
Cut 222: from h0h_{0}h0​ to h3h_{3}h3​ at height 111 resulting in [1,1,1,1,2,1][1, 1, 1, 1, 2, 1][1,1,1,1,2,1]
Case #1:
Cut 000: from h0h_{0}h0​ to h4h_{4}h4​ at height 222 resulting in [2,2,2,2,2][2, 2, 2, 2, 2][2,2,2,2,2]
Cut 111: from h2h_{2}h2​ to h4h_{4}h4​ at height 111 resulting in [2,2,1,1,1][2, 2, 1, 1, 1][2,2,1,1,1]

Interactive visualization

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: Small Forest (25 points)

After her second training session, Binna got used to bamboo cutting and wants to further raise the difficulty and removes the height limit of the previous subtask. Even though she was able to improve her endurance during the training, the endurance rests her limiting factor and cutting at many different heights is very energy-sapping. Hence, she limits the number of bamboo sticks to $1000$ .

Input/Output

Same as in subtask 1.

Limits

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

$N \le 1000$
$1 \le h_i \le 100\,000$ .

Example

Input:

1
8
8 2 5 2 1 5 5 8

Output:

Case #0: 5

Comment:

Case #0:
Cut 000: from h0h_{0}h0​ to h7h_{7}h7​ at height 888 resulting in [8,8,8,8,8,8,8,8][8, 8, 8, 8, 8, 8, 8, 8][8,8,8,8,8,8,8,8]
Cut 111: from h4h_{4}h4​ to h4h_{4}h4​ at height 111 resulting in [8,8,8,8,1,8,8,8][8, 8, 8, 8, 1, 8, 8, 8][8,8,8,8,1,8,8,8]
Cut 222: from h1h_{1}h1​ to h6h_{6}h6​ at height 555 resulting in [8,5,5,5,1,5,5,8][8, 5, 5, 5, 1, 5, 5, 8][8,5,5,5,1,5,5,8]
Cut 333: from h3h_{3}h3​ to h3h_{3}h3​ at height 222 resulting in [8,5,5,2,1,5,5,8][8, 5, 5, 2, 1, 5, 5, 8][8,5,5,2,1,5,5,8]
Cut 444: from h1h_{1}h1​ to h1h_{1}h1​ at height 222 resulting in [8,2,5,2,1,5,5,8][8, 2, 5, 2, 1, 5, 5, 8][8,2,5,2,1,5,5,8]

Interactive visualization

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: Large Forest (35 points)

After all of those training sessions, Mouse Binna became a true bamboo cutting expert and she is now able to cut patterns for any number of sticks $N$ .

Input/Output

Same as in Subtask 1.

Limits

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

$N \le 300\,000$
$1 \le h_i \le 100\,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).

Battery Fix

Mouse Stofl has taken his laptop with him to Singapore to practice for IOI. Unfortunately his computer was built to be resistant against the cold weather (in case he wants to go skiing) but not against the humid hot weather of Southeast Asia and therefore his battery broke. After examining the battery, he realized that he can easily fix the broken battery by connecting the poles, which are placed on a circle, with heat-resistant wires.

After some research he found the rules of the battery:

There are $2 \cdot N$ poles evenly distributed on the circle.
Every pole has a potential level $p_i$ between $0$ and $2 \cdot N - 1$ .
Every potential level occurs exactly once.

And the rules he must follow to ensure a running battery:

Every pole must be connected to exactly one other pole by a wire.
Wires are not allowed to overlap.
A wire connecting a pole with potential $p_i$ and $p_j$ has power $|p_i - p_j|$ . For the computer to work, the sum of the powers has to be maximized.

If there are several ways to connect the poles correctly, then Stofl can choose any of the correct ways. Help him to figure out how he should wire his broken battery!

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$ , half the number of poles. A second line follows with a list containing the potential levels $p_{0}, p_{1}, {\dots} p_{2 \cdot N - 1}$ . The list is guaranteed to be a permutation of $\{0, 1, {\dots}, 2 \cdot N - 1}$ .

(Note: $p_{0}$ corresponds to the potential level at the “top” of the circle (like 12 on a clock) and the other levels are in clockwise order.)

Output

For the $i$ -th test case, output a line “Case #i:”, followed by a description of the wires. Output $N$ lines, each describing a wire by two numbers $a$ and $b$ , meaning Stofl connects pole $a$ and pole $b$ by a wire. Of course, the wiring should follow the above stated rules. Note: $a$ and $b$ correspond to the position of the poles, not their level.

Subtask 1: Ordered (10 points)

Stofl wrongly assumes that the potential levels are ordered and therefore asked you first to solve this simpler case.

Limits

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

$1 \le N \le 1\,000$
$p_i = i$

Example

Input:

Output:

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

Comment:

Case #0:
The solution 0 – 1 and 2 – 3 wouldn’t maximize the sum of powers.
The solution 0 – 2 and 1 – 3 would maximize the sum of powers, but the wires overlap.
Case #1:
This is the only possibility.

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: Small Battery (10 points)

After realizing his wrong assumption, he now asks you to solve the correct case on a smaller scale.

Limits

There are $T=100$ test cases. In every test case: $1 \le N \le 10$ .

Example

Input:

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

Output:

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

Comment:

Case #0:

3 – 0 and 2 – 1 would be also a correct 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 3: Medium Battery (10 points)

Now Stofl asks you to solve the problem for his computer-sized battery.

Limits

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

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

Subtask 4 (Theoretical): Future Developments (70 points)

After fixing his computer, Stofl decides to start a battery fixing workshop (when he’s back from IOI). To ensure the safety of other computers, he asks you to prove the correctness of your algorithm. He also asks you to guarantee that your algorithm runs fast enough and uses as little memory as possible.

Describe an algorithm that can solve the task and analyze it. This is a theoretical task, so you should reason why your solution is correct and what asymptotic running time and memory usage your solution has.

See the table below in ‘Grading’ to see how many points can be achieved for a given runtime and memory usage.

Check out the wiki for more information on how to solve/write theoretical tasks: Theoretical Intro

Output

Hand in a document (preferably PDF) that describes

how your algorithm works,
why your algorithm is correct, and
what its running time and memory usage are.

Grading

For this task, we give you the option to hand in your solution earlier to receive a feedback. This includes comments on parts of your solution which are unclear and a rough estimate of points. Afterwards, you may adjust your solution and send it in again for more points.

To receive feedback, you have to submit a solution before 30.10.2020 23:59. If you have submitted a solution, you will get a feedback for it on 02.11.2020.

If everything is correct, we will give you points based on the table below.

Running time	Memory usage	Max score
$O(N^{2})$	$O(N^{2})$	15
$O(N \cdot \log N)$	$O(N \cdot \log N)$	30
$O(N)$	$O(N)$	40
$O(N \cdot \log N)$	$O(\log N)$	60
$O(N \cdot \log N)$	$O(1)$	70

If you are not familiar with the $O()$ notation, you can read about it here.

Note: You can assume that the input is given as a read-only array, which means you can’t change the values. This array doesn’t count to your memory, so only additional memory counts to your memory analysis.

Write your output into an append-only-stream. This means you can produce your output using functions such as print, write or with cout <<. You have no read access to your output, but it also does not count towards your memory usage.

Try to send in your solution, even if it is incomplete or slow. We also award partial points for crucial observations which are helpful to solve the task.

The contest is over, you can no longer submit.

Note: This story is fictional. Don’t try to fix your batteries at home this way!

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

Lily Pads

The Singapore river is full of lily pads, all neatly ordered in a line. Frog Pepe discovered that they are very bouncy and wants to use them to jump around.

By jumping on the i-th lily pad, Frog Pepe can bounce to any lily pad that’s between $a_i$ to $b_i$ steps away from it. In other words by jumping on lily pad $i$ ( $0\le i<N$ ) he can reach all lily pads $j$ ( $0\le j<N$ ) with $a_i \le |i-j| \le b_i$ .

Frog Pepe starts on lily pad $S$ . Help him reach lily pad $F$ in as few as bounces as possible.

Input

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

the first line contains, $N$ , $S$ and $F$ – the number of lily pads, the index of the start lily pad, and the index of the target lily pad.
the second line contains $N$ numbers $a_i$ , the minimal bounciness of the $i-th$ lily pad.
the third line contains $N$ numbers $b_i$ , the maximal bounciness of the $i-th$ lily pad.

Output

For the $i$ -th test case print a line “Case #i:” followed by a single integer: the minimal number of jumps to go from $S$ to $F$ . If it is impossible to get from $S$ to $F$ , print -1 instead.

Limits

In all subtasks:

There are $T=100$ test cases.
$0\le S,F<n$ .
$1\le a_i\le b_i\le n$ for all $i$ .

Subtask 1 (15 points)

$1\le N\le 100$ and $a_i=1$ for all $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

Subtask 2 (25 points)

$1\le N\le 10^{6}$ and $a_i=1$ for all $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

Subtask 3 (20 points)

$1\le N\le 100$ .

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

Download input again

You have 5 minutes and 0 seconds left.

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

Do not navigate away while your solution is running.

Output

Source Code

Subtask 4 (40 points)

$1\le N\le 10^{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

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

Changi Falls

https://upload.wikimedia.org/wikipedia/commons/thumb/e/e9/JewelSingaporeVortex1.jpg/800px-JewelSingaporeVortex1.jpg

Rain Vortex inside the “Jewel” area at Changi Airport.

https://www.luxurytravelmag.com.au/wp-content/uploads/2019/03/forest-valley-gallery-3-min.jpg

One of the terraced waterfalls in Jewel Changi.

Jewel Changi is a nature-themed entertainment complex on the landside of Changi Airport in Singapore. Its centrepiece is the world’s tallest indoor waterfall, the Rain Vortex, which is surrounded by a terraced forest setting.

While visiting Jewel Changi on her way to IOI, Mouse Binna was impressed by the architecture of the terraced forest setting, and she especially enjoyed the looks of the waterfalls. Binna was wondering if one could build an even bigger waterfall within the Jewel Changi, and suddenly she could be found mapping out the whole area and calculating the perfect location for a waterfall.

Jewel Changi consist of multiple terraces in the shape of a circle, the predominant shape in its architecture. Terraces are flat areas delimited by walls. Terraces can be nested, i.e. some platform can reside inside another platform, but they never intersect.

Mouse Binna only considers waterfalls that are not too long, meaning they can pass through at most $L$ terraces that are successively receding. Formally, let $t_{0},\dots,t_{k-1}$ be a sequence of terraces. It is a viable location of a waterfall exactly when:

$k\le L$ , i.e. it flows through at most $L$ terraces.
$t_i$ and $t_{i+1}$ are adjacent terraces, meaning either $t_i$ is directly inside $t_{i+1}$ or vice versa. [1]
The water always flows down, meaning the height of terrace $t_i$ must be strictly larger than the one of $t_{i+1}$ .

The height difference of a waterfall is the difference of altitudes from terrace $t_{0}$ to terrace $t_{k-1}$ .

Since Binna is already exhausted from mapping out the area, help her figure out the maximum height difference.

[1]	A terrace $t$ is directly inside another terrace $t'$ iff t is inside $t'$ and there is no terrace $t''$ such that $t$ is inside $t''$ and $t''$ is inside $t'$ .

Subtask 1: Concentric Circles (15 points)

Based on a quick glance, Binna assumed that all circles have the center at the Rain Vortex at location $(0,0)$ . She thinks this can give her a good idea of the height difference already.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow. The first line of each test case contains two integers $N$ and $L$ , the number of platforms and the maximum length. The following $N$ lines contain 4 numbers each: $x_i$ , $y_i$ , $r_i$ and $h_i$ , meaning that the $i$ -th terrace has center at coordinate $(x_i,y_i)$ , its radius is $r_i$ and the altitude is $h_i$ .

Note that in this subtask, $x_i=y_i=0$ .

Output

For the $i$ -th test case print a line “Case #i:” followed by a single integer: the maximum height difference of a viable waterfall.

Limits

$T=100$ .
$1 \le L \le N \le 1\,000\,000$ .
$0\le h_i\le 10^{9}$ for all $0\le i<N$ .
$1\le r_i\le 10^{9}$ for all $0\le i<N$ .
$x_i=y_i=0$ for all $0\le i<N$ . This is the special restriction for subtask 1.

Example

Input:

3
5 3
0 0 1 3
0 0 2 2
0 0 3 1
0 0 4 4
0 0 5 1
5 3
0 0 2 4
0 0 5 3
0 0 1 1
0 0 3 1
0 0 4 2
6 4
0 0 340073108 5
0 0 355849419 20
0 0 706293447 21
0 0 809063052 72
0 0 878401727 14
0 0 999963596 29

Output:

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

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: Flowing Inwards (15 points)

Taking a closer look, Mouse Binna noticed that not all circles actually are centered at $(0,0)$ . However, she noticed another trend: smaller circles have smaller altitude. In fact, Binna discovered that the approximately coincide, i.e. $r_i\approx h_i$ and she decides to compute the maximum height difference using that approximation.

Input and Output

Same as subtask 1.

Limits

$T=100$ .
$1 \le L \le N \le 1000$ .
$0\le h_i\le 10^{9}$ for all $0\le i<N$ .
$1\le r_i\le 10^{9}$ for all $0\le i<N$ .
$-10^{9}\le x_i,y_i \le 10^{9}$ for all $0\le i<N$ .
$r_i=h_i$ for all $0\le i<N$ . This is the special restriction for 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

Subtask 3: Jewel Changi (20 points)

Mapping out the airport a second time, it turns out that none of the assumptions from before actually hold.

Input and Output

Same as subtasks 1 and 2.

Limits

$T=100$ .
$1 \le L \le N \le 1000$ .
$0\le h_i\le 10^{9}$ for all $0\le i<N$ .
$1\le r_i\le 10^{9}$ for all $0\le i<N$ .
$-10^{9}\le x_i,y_i \le 10^{9}$ for all $0\le i<N$ .

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: Prepping for a Giant Jewel Changi (25 points)

After a full day of measuring, Binna finally produced high-detail maps with up to $N=10^{6}$ terraces.

Before she starts computing waterfall location, Binna wants to do some preparation work: for each terrace, she wants to know the index of its adjacent outer terrace.

Input

Similar to subtasks 1, 2 and 3, but this time the $L$ is missing, since it’s not needed.

Output

Let’s denote the outer terrace of $i$ as $p_i$ . If $i$ is already the outer-most terrace, $p_i=-1$ .

For each test case, output a single number, the hash of all outputs:

\sum_{i=0}^{N-1} (p_i+2)\cdot 1000003^i\text{ mod }1000000007

Limits

$T=100$ .
$1 \le N \le 1\,000\,000$ .
Same limits for $h_i$ , $r_i$ , $x_i$ and $y_i$ as subtask 3.

Grading

Since we can’t ensure that optimized brute-force solutions or heuristics won’t be able to pass, we will manually check all submissions and may retroactively give an accepted submission 0 points.

We expect a solution that runs in $O(N(\log N)^c)$ (for a constant $c$ ). See Introduction to Algorithm Design on what those symbols mean.

Unless you exploit how the tests are generated or were squeezing your solution through the time limit, you should be fine.

Note: We need around 20sec to generate the input (depending on your browser and machine). Please be patient.

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: Giant Jewel Changi (25 points)

Finally, time has come to compute the perfect location for the waterfall. Mouse Binna is very excited and has already decided to call it the “Changi Falls”. Can you help Mouse Binna one last time?

Input

The first line contains the number of test cases $T$ . $T$ test cases follow. The first line of each test case contains an two integers $N$ and $L$ , the number of platforms and the maximum length. The following $N$ lines contain 5 numbers each: $x_i$ , $y_i$ , $r_i$ , $h_i$ and $p_i$ , meaning that the $i$ -th terrace has center at coordinate $(x_i,y_i)$ , its radius is $r_i$ and the altitude is $h_i$ and its outer terrace has index $p_i$ (where $p_i=-1$ if it is already outer-most).

The $p_i$ correspond to the output of subtask 4, looking at them is optional, but intended as help.

Output

Same as subtasks 1, 2 and 3.

Limits

$T=100$ .
$1 \le L \le N \le 1\,000\,000$ .
Same limits for $h_i$ , $r_i$ , $x_i$ and $y_i$ as subtask 3.

Grading

We expect a solution that runs in $O(N(\log N)^c)$ (for a constant $c$ ). See Introduction to Algorithm Design on what those symbols mean.

Unless you exploit how the tests are generated or were squeezing your solution through the time limit, you should be fine.

Note: We need around 20sec to generate the input (depending on your browser and machine) and another 20sec to verify your submission. Please be patient.

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

Satay

Satay is a traditional Singaporean dish that consists of meat stripes that are grilled on a skewer. It is often served with peanut sauce and pieces of cucumber and onion.

Subtask 1: Just Skewers (20 points)

A group of $N$ mice hast just eaten some Satay and they’re left with just the skewers. Each mouse is holding exactly one skewer. The mice figured it would probably be easiest to hand all skewers to one mouse, so that only that mouse has to look for a waste bin.

Some pairs of mice are standing next to each other. The mice want to avoid accidentally hitting bystanders with skewers, so only mice that are standing next to each other may hand skewers to each other. It just so happens that for every pair of mice, there is a unique way of passing skewers from the first mouse to the second mouse, possibly via some other mice.

Whenever a mouse hands skewers to another mouse, there is a risk that the mouse might accidentally drop the skewers. Mouse Stofl has estimated that the risk of dropping the skewers is equal to the number of skewers that were passed. Dropping the skewers is very embarrassing, so you want to minimize the total risk. Can you figure out how to get all skewers to the same mouse?

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each test case consists of three lines. The first line contains an integer $N$ – the number of mice in the group. The second line contains $N-1$ integers $a_{1}, \dots, a_{N-1}$ and the third line contains $N-1$ integers $b_{1}, \dots, b_{N-1}$ . For $i=1,\dots,N-1$ , the mice $a_i$ and $b_i$ are standing next to each other.

It is guaranteed that for every pair of distinct mice $a$ and $b$ , there is an integer $k$ and a unique sequence $a = m_{1}, \dots, m_k = b$ of distinct mice such that $m_i$ and $m_{i+1}$ are standing next to each other for all $i$ .

Output

For the $i$ -th test case, print a line “Case #i:” followed by a single integer: the minimum total risk needed to pass all skewers to a single mouse.

Limits

$T=100$
$2 \le N \le 100$
$0 \le a_i, b_i < N$

Example

Input:

Output:

Case #0: 3
Case #1: 9

Comment:

In case #0, all mice are standing next to mouse

0

and it is optimal to have mouse

0

collect all skewers. In case #1, there are multiple optimal solutions. You can collect all skewers at mouse

2

or at mouse

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 2: Everything to Stofl (20 points)

The mice successfully managed to throw away all skewers without dropping any of them. The Satay was very delicious, so they decided to have some Satay with peanut sauce. The peanut sauce was served on a small plate, so now the mice have to deal with both the skewers and the plates. Mouse Stofl wasn’t happy with how long it took the mouse in subtask 1 to find the trash, so this time, he wants to do it himself.

At the moment, every mouse is holding a plate with a skewer on top of it, and the goal is to get all plates and skewers to Mouse Stofl. Having skewers below or between plates make the stack of plates very unstable, which would greatly increase the risk of dropping the plates, so the mice want to avoid this at all costs.

Unfortunately, the plates are quite heavy, which means the mice have to use both hands to hold the plates. This severely limits their options: If two mice are standing next to each other, the first mouse can always pass any number of skewers to the next mouse. Additionally, if the second mouse is not holding any skewers, the first mouse may pass all of its skewers and any number of plates to the second mouse. Mouse Stofl estimates that the risk of dropping something if $x$ skewers and $y$ plates are passed to another mouse is $S \cdot x + P \cdot y$ for some constants $S$ and $P$ .

Can you figure out the least risky way of getting all skewers and all plates to Stofl?

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each test case consists of three lines. The first line contains three integers $N$ , $S$ and $P$ – the number of mice in the group and two parameters describing the risk of passing skewers and plates. The second line contains $N-1$ integers $a_{1}, \dots, a_{N-1}$ and the third line contains $N-1$ integers $b_{1}, \dots, b_{N-1}$ . For $i=1,\dots,N-1$ , the mice $a_i$ and $b_i$ are standing next to each other.

Output

For the $i$ -th test case, print a line “Case #i:” followed by a single integer: the minimum total risk needed to pass all skewers and plates to mouse Stofl (mouse 0).

Limits

$T=100$
$2 \le N \le 10^{5}$
$1 \le S, P \le 10^{5}$
$0 \le a_i, b_i < N$

Example

Input:

Output:

Case #0: 22
Case #1: 66
Case #2: 48

Comment:

In Case #0, the mice could proceed as follows: Pass one skewer from mouse 1 to mouse 0, then pass two skewers from mouse 0 to mouse 2. After these two steps, all skewers are held by mouse 2. Then pass one plate from mouse 1 to mouse 0 and finally, pass three skewers and one plate from mouse 2 to mouse 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: Skewers and plates without Stofl (10 points)

While mouse Stofl is busy trying to find a trash can, the remaining mice decide to have some more Satay. Can you help them figure out the least risky way of dealing with the plates and skewers afterwards?

The situation is the same as in subtask 2, but there is no mouse Stofl, so you can pick the mouse that collects all the plates and skewers.

Input

Same as in subtask 2.

Output

For the $i$ -th test case, print a line “Case #i:” followed by a single integer: the minimum total risk needed to pass all skewers and all plates to a single mouse.

Limits

$T=100$
$2 \le N \le 10^{5}$
$1 \le S, P \le 10^{5}$
$0 \le a_i, b_i < N$

Example

Input:

Output:

Case #0: 22
Case #1: 48
Case #2: 38

Comment:

In Case #0, having mouse 0 collect everything carries the least risk. In Case #1, there are multiple optimal solutions, where either mouse 1 or mouse 2 collects everything.

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 (Theoretical): More Skewers and Plates (50 points)

Mouse Stofl is nowhere to be seen, but the mice are still hungry, so they go for some more Satay. This in turn gives them more skewers and plates to deal with, so they again ask you to help them minimize the risk of dropping them.

This is a theoretical subtask. Describe an algorithm that can solve subtask 3 and analyze its running time and memory usage.

You should optimize for running time first and memory usage second.

Hand in a document (preferably PDF) that describes

how your algorithm works,
why your algorithm is correct. In particular, you should explain why your answer is feasible, i.e. describe a strategy for the mice that achieves the total risk you output, and explain why your answer is optimal, i.e. show that there is no strategy that results in less total risk.
how much time and memory it uses.

Limits

$N$ , $S$ , $P$ are variables. You can assume that basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform and that storing one integer uses a single unit of memory.
To get full points for this subtask, you should aim for $O(N)$ runtime and $O(N)$ memory.

The contest is over, you can no longer submit.

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

Muffins

SOI participants like muffins [citation needed]. Mice Stofl and Binna have invited some participants into their apartment for training and would like to provide the necessary amount of muffins to keep them motivated while solving difficult tasks. They have set up their kitchen, but are unsure how to best coordinate the muffin baking process. You can help them by assuming the role of either Stofl or Binna and baking muffins as efficiently as possible.

Baking Muffins

The muffin baking process consists of seven different stations. Whenever your mouse is idle it can either move to a different station, work on the current station or do nothing. In the beginning, the mouse is at no station and thus first has to move to a station. The speed of a mouse working at a specific station is always proportional to their skill at that specific station. The stations are as follows:

Dough Station: Here you can fetch the basic ingredients for muffin dough. The available action is to fetch a fixed amount of dough in a fixed amount of time. Fetched ingredients are stored on the table.

Chocolate Station: Here you can fetch the chocolate for chocolate muffin dough. The available action is to fetch a fixed amount of chocolate in a fixed amount of time. Fetched ingredients are stored on the table.

Lemon Station: Here you can fetch lemons for lemon muffin dough. The available action is to fetch a fixed amount of lemons in a fixed amount of time. Fetched ingredients are stored on the table.

Bowl Filling Station: Here you can take ingredients from the table and fill them into bowls. There is a fixed number of bowls. All bowls have the same, fixed capacity. The available action is to take a 1:1 mixture of either one chocolate and one dough, or one lemon and one dough and fill it in a given bowl. The bowl must either be empty or not have been mixed yet and must not currently be in use by a different mouse. The action works by specifying the type, either chocolate or lemons and the bowl in which to fill it. The bowl will automatically be filled with one piece of chocolate/lemon and one piece of dough, so the content will increase by two.

Bowl Mixing Station: Here you can take a bowl and mix its ingredients. The available action is to select a bowl and mix it, which takes a fixed amount of time. The bowl must not currently be in use by a different mouse.

Cup Filling Station: Here you can fill the ingredients from mixed bowls into muffin cups. The available action is to select a bowl and fill one unit of its content into cups. One unit of ingredients fills exactly one cup. This takes a fixed amount of time. There is a limited number of cups available. The cups can be used for both chocolate and lemon muffins, but their sum mustn’t exceed the maximum number of cups. Only one mouse can work on this action at the same time.

Baking Station: Here you can finally bake muffins. The available action is to take all of the currently filled cups and bake them into finished muffins. Putting the muffin cups into the oven takes a fixed amount of time. The oven then takes a fixed amount of time for baking. The action can only be executed if the oven is not currently baking muffins and only one mouse can work on it at the same time. Once the action is started, all cups are emptied and can be reused. Any cups that are filled while this action is running will not be put into the oven.

The formulas for calculating the exact time taken are as follows:

Dough: $\text{dough\_skill}$
Chocolate: $\text{chocolate\_skill}$
Lemons: $\text{lemon\_skill}$
Bowl Filling: $\text{bowl\_filling\_skill} \times 2$
Bowl Mixing: $\text{bowl\_mixing\_skill}$
Cup Filling: $\text{cup\_filling\_skill}$
Baking (excluding oven): $\text{baking\_skill}$
Baking (including oven): $\text{baking\_skill} + \text{baking\_time}$

Skill values, the oven’s baking time, the maximum number of cups and bowls and the bowl capacity are constant within a single game. Skill values can be different for different mice. All skill values are guaranteed to be non-negative and less than $10^{6}$ .

It takes a fixed amount of time to move to a station. This switching time is different for every station, but the same for every mouse and doesnt change during one game.

Storages

There are three different storages for muffin ingredients. The first is the table for raw dough, chocolate and lemons. You can store an infinite amount of resources on the table. The second are bowls. For one game, there’s a fixed amount of bowls, each with the same capacity. A bowl can only be filled with dough of the same type, except when it is empty, then it can be filled with any type of dough. A bowl can be either mixed or not mixed. A bowl can only be in use by one mouse at a time. The third storage type are cups. There is a limited number of total cups available. Each cup can either be filled with chocolate dough or lemon dough, or be empty.

There will never be more than $100$ bowls, the capacity of a bowl will never exceed $1000$ and there will be at most $5000$ cups available.

Fulfilling Orders

In order to keep the participants stimulated, Stofl and Binna have created a muffin schedule. Each order consists of a type of muffin, either chocolate or lemon, the amount of muffins and the time to deliver. All muffins that have finished baking are considered available for orders and will automatically be used to fill orders. Orders can be filled partially. One point is awarded for every successfully baked muffin in an order. Once the time for an order passes, all available muffins of the given type, but at most the given amount are taken for that order. Once the time for an order has passed, it’s impossible for any future muffins to be used for it.

You will never have to bake more than $1000$ total muffins.

Implementation

There are wrappers available to handle communication with the judge for Python and C++. These are provided with the sample bots in each language.

Each game begins with the definition of each Mouse’s skill values, the oven baking time, the number of dough, chocolate and lemons that can be fetched in one go, the maximum number of cups and bowls and the bowl capacity. The order list is also given at the beginning of the game. Then the mice take turns in order of their id. There are call-ins to inform you of the other player’s actions. Once it is your turn, you can use one of the given methods to execute an action.

You can download the sample bots for C++ and Python here.

Subtask 1

Binna went to an international competition and Stofl wants to bake some muffins for his best friend Flappi. Flappi tells him whether he wants chocolate or lemon muffins and how hungry it is. Sometimes Flappi is very hungry, so he can ask for up to $1000$ muffins. As a special condition for this subtask only, Stofl always has a whole number multiple of muffin cups as there is space in the bowls, i.e. $\text{max\_cups} = k \times \text{bowl\_capacity} \times \text{bowl\_count}, k \in \mathbb{N}$ . You have to tell Stofl how to bake a fixed amount of one type of muffins in the shortest total time possible. This means there will only be one order.

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

Stofl was very happy that you could help him bake for Flappi. He thought of some special cases where he was unsure how he would handle them. They can contain combinations of chocolate and lemon muffins. Try to fulfill as many orders as possible, it is ok if you can’t fulfill them all. The input will always be the same. Each test case will be scored based on the following formula:

$25 \cdot \text{min}\left(1,\frac{\text{muffins\_baked}^{3}}{100^{3}}\right)$

The total score is the average of the scores on each test case.

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

Binna is back and it’s time to bake some muffins for the participants now. This time Stofl and Binna have to cooperate, you can only help one of them at a time. The other mouse will be controlled by another program. Your submission will be scored depending on how well it cooperates with all other programs.

For testing, you can try running two instances of your own bot, or running your own bot alongside the sample bot. Check the updated readme in the sample bot package on how to do so. Once you’re done, you can upload up to three different bots in a zip archive. Only your best submission will count.

The contest is over, you can no longer submit.

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

Junior Ranking

Rank	Username	Total (500)	stairra… (100) stairracing	secretcode (100)	bamboo (100)	batteryfix (100)	lilypads (100)
	loading ...

Regular Ranking

Rank	Username	Total (600)	bamboo (100)	batteryfix (100)	lilypads (100)	changif… (100) changifalls	satay (100)	muffins (100)
	loading ...