First Round SOI 2019/2020 - 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	marathon	‒/100	‒/20	‒/20	‒/20	‒/20	‒/20
Junior only	stickers	‒/100	‒/10	‒/20	‒/20	‒/20	‒/30
Both	bargain	‒/100	‒/10	‒/25	‒/25	‒/15	‒/25
Both	reversi	‒/100	‒/10	‒/20	‒/20	‒/50
Both	sbb	‒/100	‒/25	‒/25	‒/25	‒/25
Regular only	arcmatch	‒/100	‒/10	‒/10	‒/10	‒/30	‒/40
Regular only	earthwormsurgery	‒/100	‒/20	‒/20	‒/60
Regular only	soiway	‒/100	‒/25	‒/25	‒/25	‒/25

Marathon

In anticipation of the Olympic games in 2020, Mouse Binna decided she wants to organise a marathon for herself and her friends. The conditions for this idea seemed perfect – in her village there is a very long road. However, upon further investigation, she discovered that the road is not in a very good shape and there are a lot of holes. Since Mouse Binna doesn’t want someone to trip and hurt themselves while running, there cannot be any holes on the track. Your task is to help her organise the longest marathon possible.

Subtask 1: A short road (20 Points)

Mouse Binna wants to use only a short part of the road. Your first program should help her figure out the maximum possible length of the race.

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 road.
The second line consists of $N$ numbers $p_i$ describing the road, where $p_i=1$ if there is a hole at this spot and $p_i=0$ otherwise.

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 marathon Mouse Binna can organise.

Limits

$T=100$
$N = 3$

Examples

Input:

Output:

Case #0: 2
Case #1: 1

Comment:

In case #0, the longest possible track would be from position $1$ to position $2$ included (the road is $0$ -based) so the length is $2$ .
In case #1, there are $2$ longest possible tracks all with length $1$ , which are at positions $0$ and $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.

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 Longer Road (20 points)

Your task here is the same as in subtask 1, but with a longer road.

Input

The input format is the same as in subtask 1.

Output

The output format is the same as in subtask 1.

Limits

$T=100$
$1\le N\le 100$

Examples

The examples are the same as 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: A very long Road (20 points)

Your task here is the same as in subtask 1, but with an even longer road.

Input

The input format is the same as in subtask 1.

Output

The output format is the same as in subtask 1.

Limits

$T=100$
$1\le N\le 10^{5}$

Examples

The examples are the same as 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 4: Fix the road (20 points)

While Mouse Binna was thinking of the possible marathons she could organise, a friend of hers who is working in construction proposed to fix some of the holes on the road. However she only has enough material to fix $K$ holes. Help Mouse Binna find out what is the longest marathon she can organise now by fixing at most $K$ holes.

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 road and the number $K$ of holes that can be fixed.
The second line consists of $N$ numbers $p_i$ describing the road where $p_i=1$ if there is a hole and $p_i=0$ otherwise.

Output

The output format is the same as in subtask 1

Limits

$T=100$
$1\le N\le 100$
$K=3$

Examples

Input:

2
10 3
0 0 0 1 1 1 0 0 0 0
12 3
0 1 0 0 1 1 0 1 0 0 1 0

Output:

Case #0: 10
Case #1: 8

Comment:

In case #0, the longest possible track is from the beginning to the end by fixing all $3$ holes so the length is $10$ .
In case #1, the longest possible track is from position $2$ to position $9$ by fixing the $3$ holes that are in that section so the length is $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 5: Marathon (20 points)

Same as in subtask 4, but with a longer road and more material to fix holes.

Input

The input format is the same as in subtask 4.

Output

The output format is the same as in subtask 1.

Limits

$T=100$
$1\le N\le 10^{5}$
$1\le K\le 100$

Examples

Same as in subtask 4.

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

Stickers

Mouse Stofl loves collecting stickers. After buying many of them, he realises that each sticker belongs to a specific family. His wish is now to have as few different families of stickers as possible. Unfortunately, the stickers he buys are given at random, but he can trade some of his stickers with his friends. Depending on how nice his friends are, he has to pay them additional money to convince them of trading their stickers.

Your goal is to help Stofl to minimize the number of different families he owns, without paying too much.

Subtask 1 (10 points)

Stofl bought exactly three ( $N = 3$ ) stickers and as his friends are really nice, they are willing to trade their stickers if he pays them one Swiss franc for every sticker trade. Help him to minimize the amount of money he has to spend so that all of his stickers belong to only one family.

Input

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

The first line of the test case contains $N$ , the number of stickers Stofl owns (in this subtask, we have $N=3$ ) and $K$ , the maximum number of different families Stofl wants to own after all his trades (in this subtask, we have $K=1$ ).

The second line contains $N$ numbers $a_{0},\ldots,a_{N-1}$ , where $a_j$ represents the family of the $j$ -th sticker. The cost of trading one sticker of one family for a sticker of another family is $1$ Swiss franc.

Output

For the $i$ -th test case, output a line “Case #i: M”, where $M$ is the minimal amount of money Stofl has to spend.

Limits

There are $T=100$ test cases. In all test cases $N=3$ , $K=1$ and $1 \le a_j \le 100$ .

Example

Input:

Output:

Case #0: 1
Case #1: 2

Comment:

In case #0, Stofl already owns two stickers of the same family, he then trades the sticker belonging to family $2$ for one of his friends’ stickers which belongs to family $1$ . He needs to pay one franc as he makes one trade.

In case #1, Stofl has to trade at least two stickers with his friends to have three stickers of the same family.

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

Stofl fell in love with this game so he decided to buy even more stickers. He now owns more than three stickers.

Input/output

Same as in subtask 1, but $N$ is not necessarily $3$ anymore. Note that there are now many more families in the game than before ( $a_j \le 10^{6}$ ).

Limits

There are $T=100$ test cases. In all test cases $1 \le N \le 1000$ , $K=1$ and $1 \le a_j \le 10^{6}$ .

Example

Input:

Output:

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

Comment:

In case #0, Stofl has to trade two stickers.

In case #1, one possible solution is to trade away the stickers belonging to the families 1 and 2. He can do this with three trades.

In case #2, Stofl keeps the stickers belonging to family $1$ . He trades the rest away in exchange for stickers of family $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 (20 points)

Stofl spent a lot of money to buy the stickers and realizes he can’t keep spending as much as before to trade stickers. He decides that owning more than one family of stickers isn’t that bad after all. The maximum number of different families $K$ is not restricted to $1$ anymore.

Input/output

Same as in subtask 1 but $K$ is not necessarily $1$ anymore.

Limits

There are $T=100$ test cases. In all test cases $1 \le N \le 1000$ , $1 \le K \le N$ and $1 \le a_j \le 10^{6}$ .

Example

Input:

3
3 3
1 8 70
5 2
1 2 2 5 3
7 2
9 2 13 1 13 9 13

Output:

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

Comment:

In case #0, Stofl can own up to three different sticker families. So he does not have to trade at all.

In case #1, Stofl can own up to two sticker families. He could trade away the families $1$ and $5$ to achieve this.

In case #2, Stofl decides to trade away stickers belonging to family $2$ and $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 (20 points)

Stofl is now done with buying new stickers. Since the last update of the game, families now have values. In particular, family $a$ is worth $a$ Swiss francs. Stofl now trades according to the following rules:

Stofl never wants to downgrade a sticker from family $a$ into family $b$ with $b<a$ .
Stofl’s friends charge him $b-a$ Swiss francs if Stofl wants to trade a sticker of family $a$ against a sticker of family $b$ (with $b>a$ ).

Can you help Stofl to find the minimum amount he has to pay in order to make all his stickers belong to one of at most two families?

Input/output

Same as in subtask 1. $K$ is always equal to $2$ .

Limits

There are $T=100$ test cases. In all test cases, $1 \le N \le 100$ , $K=2$ and $1 \le a_j \le 10^{6}$ .

Example

Input:

Output:

Case #0: 1
Case #1: 6
Case #2: 2

Comment:

In case #0, Stofl decides to trade the sticker of family $1$ for another sticker of family $2$ . This way, he owns stickers of at most $2$ different families.

In case #1, Stofl trades the stickers belonging to families $7$ and $8$ for two stickers of family $10$ . Additionaly he trades a sticker of family $4$ for one of family $5$ .

In case #2, Stofl trades for stickers belonging to families $2$ and $4$ .

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

Stofl wants to expand his collection of stickers and no longer restricts himself to only two families anymore. Help him solve the general case.

Input/output

Same as in subtask 1.

Limits

There are $T=100$ test cases. In all test cases $1 \le N \le 100$ , $1 \le K \le N$ and $1 \le a_j \le 10^{6}$ .

Example

Input:

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

Output:

Case #0: 1
Case #1: 6
Case #2: 1

Comment:

In case #0, Stofl trades the sticker belonging to family $3$ for one of family $4$ .

In case #1, Stofl can trade sticker of family $6$ for one of family $8$ . He then trades his two stickers belonging to family $3$ for stickers of family $4$ . Finally, he trades his stickers of family $1$ for stickers belonging to family $2$ . The total cost is $(8-6)+2(4-3)+2(2-1) = 6$ .

In case #2, Stofl trades the sticker belonging to family $8$ for one of family $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

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

Bargain

This year, Mouse Binna participates for the first time in the Swiss Mouse Olympiad in Informatics. This involves a lot of travel by train, and unlike its human counterpart, the SMOI does not refund train tickets. As taking the train in Switzerland is quite expensive, Mouse Binna has a brilliant idea: in each city in which she passes during her trips, she goes to a market where she can buy cheese from a merchant or sell some that she has already acquired. The prices, of course, vary from city to city. Binna’s goal is to buy cheese for not too much money and resell it later for a profit, in order to pay for her tickets. Can you help her figure out where to buy and where to sell cheese so that she can maximize her profits?

Subtask 1: Workshop (10 points)

The first event to which a participant must go to succeed in the olympiad is the workshop in autumn. Mouse Binna decides to go in order to learn the programming and algorithmic skills needed for the first round (you can do so too: more information on this page).

Since there are workshops organized in several regions of Switzerland, Mouse Binna does not need to travel far, she can even use a direct train. That means there are exactly two cities where she can buy or sell cheese: her home city and the one in which the workshop is organized. She does not have any money to buy cheese herself, but she talked with her parents about the project and they agreed to pay for at most one loaf of cheese. That means that Binna can buy and sell at most once in total. Of course, she’s not obliged to buy anything; in that case, she just makes no profit, which is better than losing money.

There’s another restriction: in order to get home early on the last day, Mouse Binna wants to do all of this on her way to the workshop. That means she can’t sell cheese from the second city in the first one.

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 $b_{0}$ and $s_{0}$ , the buying price and selling prices in Mouse Binna’s home city (from Mouse Binna’s point of view).
The second line contains $b_{1}$ and $s_{1}$ , the buying and selling prices in the city in which the workshop takes place.

Output

You should output $T$ lines, one for each test case. For the $i$ -th test case, output a line “Case #i: P”, where $P$ is the maximal profit made by Binna. Note that test cases are numbered from $0$ to $T-1$ and not from $1$ to $T$ .

Limits

There are $T=100$ test cases. In every test case, the following restriction holds:

$1 \le s_i < b_i \le 100$ for every $0 \le i \le 1$ .

Example

Input:

Output:

Case #0: 2
Case #1: 0

Comment:

In case #0, the best option is to buy cheese in the first city for CHF $4$ and sell it in the second city for CHF $6$ , making CHF $2$ of profit.
In case #1, it’s better not to buy or sell any cheese, as one could do that only at a loss. Note that it is not possible to buy cheese from the second city and resell it the first one.

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

Thanks to the training in the workshop, Mouse Binna has done really well in the first round and has qualified for the SMOI Winter Camp! She decides to buy and sell cheese on her way, exactly like last time.

There’s just one big difference: there is no direct train to the camp. Mouse Binna must change trains in several places, which means she’ll visit $N$ cities in total. That makes the travel longer, but has a big advantage: there are now many more opportunities to make a profit. Note, again, that you can’t go back to an earlier city to sell cheese you’ve bought in a later one.

Input

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

The first line of the test case contains $N$ , the number of cities visited by Moues Binna.
There follow $N$ lines, the $i$ -th of which contains $b_i$ and $s_i$ , the buying and selling prices in the $i$ -th city visited by Mouse Binna.

Output

Same as in subtask 1.

Limits

There are $T=100$ test cases. In every test case, the following restrictions hold:

$2 \le N \le 1000$ .
$1 \le s_i < b_i \le 1\,000\,000$ for every $0 \le i < N$ .

Example

Input:

Output:

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

Comment:

In case #0, the only way to make money is to buy cheese in the first city and to resell it in the third one.
In case #1, there is no way to make a profit whatsoever.
In case #2, one can make a profit in two ways: buying in the first city and selling in the second one or buying in the third city and selling in the last one. The first option is more profitable.

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

After the camp, Mouse Binna has kept on training well and obtained a good result in the second round, and, later, a gold medal in the national finals. That’s why she’s now qualified for the International Mouse Olympiad in Informatics, which takes place in Singapore this year. She decides to still travel via trains (in reality, some busses would be needed as well), as she wants to continue buying and selling cheese on the way. She has realized that she can make quite a lot of money that way.

Because of the good results of the first experiments, Mouse Binna’s parents trust her more and allow her to buy a maximum of $K$ loafs of cheese. Of course, she can buy less than $K$ loafs, and she can buy or sell several ones in the same city. Help her figure out where to buy and sell the cheese exactly in order to make the biggest possible profit.

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$ and $K$ , the number of cities visited by Mouse Binna and the maximal number of cheese loafs she can buy.
There follow $N$ lines, the $i$ -th of which contains $b_i$ and $s_i$ , the buying and selling prices in the $i$ -th city visited by Mouse Binna.

Output

Same as in subtasks 1 and 2.

Limits

There are $T=100$ test cases. In every test case, the following restrictions hold:

$2 \le N \le 500\,000$ .
$1 \le K \le 1\,000\,000$
$1 \le s_i < b_i \le 1\,000\,000$ for every $0 \le i < N$ .

Example

Input:

Output:

Case #0: 2
Case #1: 9

Comment:

In case #0, a possible – but not the only – way to make money is to buy one cheese in the first city, resell in the third one, buy one more in the fourth one and resell it in the last one.
In case #1, the best way to make money is to buy three loafs of cheese in the first city and resell them all in the next one.

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: Leader Binna (15 points)

Mouse Binna has done well in the IMOI and is starting university now. She’d like to give back what she can to the SMOI and becomes a leader there. That means she still has to travel to some national events to train students, and for that reason, she wants to continue making money with her cheese business.

There is one key difference now: Mouse Binna is an adult and does not need her parents’ help anymore. She can just borrow money from the bank, which agrees to lend her any amount without interests because of her previous successes. Mouse Binna is therefore not limited in the total amount of cheese loafs she can purchase. Of course, she cannot take an infinite quantity of cheese with her. She can, at any time, carry only $C$ units of cheese at most. Help her again to find where and how much cheese she should buy and sell.

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$ and $C$ , the number of cities visited by Mouse Binna and the maximal number of cheese loafs she can carry at any time.
There follow $N$ lines, the $i$ -th of which contains $b_i$ and $s_i$ , the buying and selling prices in the $i$ -th city visited by Mouse Binna.

Output

Same as in subtasks 1 to 3.

Limits

There are $T=100$ test cases. In every test case, the following restrictions hold:

$2 \le N \le 1000$ .
$1 \le C \le 1\,000$
$1 \le s_i < b_i \le 1\,000\,000$ for every $0 \le i < N$ .

Example

Input:

Output:

Case #0: 20

Comment:

In case #0, the best way to make money is to buy four units in the first town, resell them in the following one, buy four more in the fourth one and resell them in the sixth one.

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: Back at IMOI (25 points)

Binna has worked hard to prepare the Swiss participants for the next International Mouse Olympiad in Informatics and has well earned her place as one of the two leaders accompanying the national team there. Help her optimize her profits on the way there.

This subtask is the same problem as subtask 4, but $N$ can be much larger.

Input

Same as in subtask 4.

Output

Same as in subtasks 1 to 4.

Limits

There are $T=100$ test cases. In every test case, the following restrictions hold:

$2 \le N \le 500\,000$ .
$1 \le C \le 1\,000\,000$
$1 \le s_i < b_i \le 1\,000\,000$ for every $0 \le i < N$ .

Example

See subtask 4.

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

Reversi

Mouse Binna and Mouse Stofl are playing a strategy board game called Reversi . Usually it is played with discs on an 8×8 board and two players. They quickly got bored playing it and came up with their own version which is played on an (endless) row:

Each disc occupying a square has a dark and a light side.

If we now place a dark disc to the left end of the line then every light disc between that and the next dark disc is flipped.

A similar thing happens if we add a light disc to the left end. Note that if we add a disc with the same colour as the one at the end of the line then no disc gets flipped. The same procedure applies to the right end.

Here, you can play around with the mechanics to get familiar with them:

Our mice came up with some interesting questions for you to solve.

Subtask 1: One Turn (10 points)

Given an arrangement of $N$ continuous discs and the operation of appending either a light or dark disk on either the left or the right end output the state after the operation.

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 discs. A second line follows with a bitstring $S$ containing $N$ characters consisting only of 0’s and 1’s, where a 0 represents a dark and a 1 a light disc. It is guaranteed that $S$ contains at least one 0 and one 1. The third line contains a character $D$ and a bit $B$ describing the operations:

L 1: append a ligth disc to the left
L 0: append a dark to the left
R 1: append a ligth to the right
R 0: append a dark to the right

Output

For the $i$ -th test case, output a single line “Case #i: R”, where $R$ is the bitstring representing the state after the operation. $R$ should only contain 0’s and 1’s.

Limits

$T=100$
$2 \le N \le 100\,000$
$D = 'L'$ or $D = 'R'$
$B = 0$ or $B = 1$

Example

Input:

3
4
1000
R 1
7
0101010
L 0
15
000011111100100
L 1

Output:

Case #0: 11111
Case #1: 00101010
Case #2: 1111111111100100

Comment:

Case #0: Appending a light disk to the right end will cause the three dark discs to flip to light discs.

Case #1: The leftmost disc is already dark so appending a dark disc to the left won’t flip any discs.

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: Few Turns (20 points)

You are given an arrangement of $N$ continous discs. What is the minimum number of operations you need such that all discs will be of the same colour?

Input

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

The first line of the test case contains $N$ , the number of discs. A second line follows with a sequence $S$ of length $N$ , consisting only of 0’s and 1’s, where a 0 represents a dark and a 1 a light disc. It is guaranteed that $S$ contains at least one 0 and one 1.

Output

For the $i$ -th test case, output a single line “Case #i: M”, where $M$ is the minimum number of operations.

Limits

$T=100$
$2 \le N \le 1\,000\,000$

Example

Input:

3
4
1000
7
0101010
15
000011111100100

Output:

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

Comment:

Case #0: adding a light disk to the right already suffices
Case #1: one possibility: R1 L1 R0 R1 L0 L1
Case #2: one possibility: L1 L0 L1 R1

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: Low Cost (20 points)

Again, an arrangement of $N$ continous discs is given. We define now the cost of an operation as the number of discs that get flipped + 1 (meaning we include the newly appended disc). Your task is now to calculate the minimum cost you need such that all discs will be the same colour.

Input

Same as in Subtask 2.

Output

For the $i$ -th test case, output a single line “Case #i: M”, where $M$ is the minimum cost.

Limits

$T=100$
$2 \le N \le 1\,000$

Example

Input:

3
4
1000
7
0101010
15
000011111100100

Output:

Case #0: 2
Case #1: 24
Case #2: 21

Comment:

Case #0: adding a dark disk to the left costs only 2, this is the best option
Case #1: one possibility: L1 R1 L0 L1 R0 R1
Case #2: one possibility: R1 R0 R1 L1

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: In Theory… (50 points)

You should do the same as in substask 3. But Mouse Stofl and Mouse Binna don’t trust your solution, meaning you need to justify why your solution is correct.

Describe an algorithm that can solve subtask 3 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.

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

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

We give you the option to hand in your solution earlier and you will receive a feedback within roughly a week. This includes how many points you would get and comments on where to improve the solution. Afterwards, you may adjust your solution and send it in again for more points. Submissions after 26.11.2019 will not receive any feedback before the end of the round.

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

Running time	Memory usage	Max score
any	any	5
$O(N^{3})$	$O(N^{3})$	10
$O(N^{2})$	$O(N^{2})$	20
$O(N^{2})$	$O(N)$	25
$O(N^{2})$	$O(1)$	30
$O(N)$	$O(N)$	40
$O(N)$	$O(1)$	50

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.

Here you can see a rough outline of the marking scheme and how the points are awarded for an explanation:

10% of the maximum points are given for a good description of the idea and algorithm
70% are given for the argumentation why it is correct
10% are given for the runtime-space analysis
- 7.5% for the runtime
- 2.5% for the space
10% are given for a nice pseudocode

Submissions after 26.11.2019 will not receive any feedback before the end of the round.

The contest is over, you can no longer submit.

Don’t waste time

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

Stofl's mountain railways

Stofl’s mountain railways (SBB) operates a rail network with $N$ stations and $M$ routes, which each run in both directions. It is possible from any station to reach every other station by several intermediate routes (i.e., the network is connected). Each track has a length of $l_i$ kilometers and the price of an ordinary billet on a stretch of length $l_i$ is $l_i$ , so the price per kilometer is one. As is common in the mountains, a direct connection between two stations need not be the shortest, i.e. there may be an alternative route with multiple intermediate routes, which is shorter overall.

The SBB have recently introduced a savings offer, the so-called StoflTicket. A StoflTicket is offered to for $S$ pairs of train stations and allows a ride between the two stations (in any direction) for a special price.

You now realize that the cheapest price for a ride between two stations can be reached possibly only through a combination of ordinary tickets and StoflTickets. So you want to start a startup which calculates the cheapest price for a trip between two stations. The only goal is to get the best possible price, even if for that a route must be traveled several times.

In order for your server to provide an instant response, you want the cheapest price for each pair of stations precalculated.

Subtask 1 (25 points)

You are given a description of the rail network of the SBB as well as StoflTickets. Your job is to find the lowest price for a journey between each pair of stations.

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 contains three integers: $N$ , $M$ , $S$ . The next $M$ lines indicate a route. The $i$ -th of these lines consists of three integers: $a_i$ , $b_i$ , $l_i$ , which specify the two terminus stations $a_i$ , $b_i$ , and the length $l_i$ of the route. The next $S$ lines describe a StoflTicket. The $i$ -th of these lines consists of three integers: $a_i$ , $b_i$ , $p_i$ , which specify the two terminus stations $a_i$ , $b_i$ , and the special price $p_i$ of this StoflTicket.

Output

For the $i$ -th test case, issue a line “Case #i: N”, followed by $N$ lines. The $j$ -th line contains $N$ integers $d_{j,k}$ , separated by spaces, which indicates the cheapest price for a ride between the stations $j$ and $k$ . For $j=k$ you should output $d_{j,j}=0$ .

Limits

There are $1 \le T \le 100$ test cases.

In each test case:

$1 \le N \le 100$
$N - 1 \le M \le 10^{4}$
$0 \le S \le 10^{4}$
$0 \le a_i, b_i < N$ , $a_i \neq b_i$
$l_i = p_i = 1$

Example

Input:

Output:

Comment:

The graphs for the first two cases are shown below:

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)

The task as well as input/output are the same as for Subtask 1.

Limits

There are $1 \le T \le 100$ test cases.

In each test case:

$1 \le N \le 100$
$N - 1 \le M \le 10^{4}$
$0 \le S \le 10^{4}$
$0 \le a_i, b_i < N$ , $a_i \neq b_i$
$1 \le l_i, p_i \le 10^{6}$

Example

Input:

Output:

Case #0: 5
0 5 15 25 30
5 0 10 20 25
15 10 0 10 15
25 20 10 0 5
30 25 15 5 0
Case #1: 5
0 5 15 6 1
5 0 10 11 6
15 10 0 10 15
6 11 10 0 5
1 6 15 5 0
Case #2: 3
0 2 1
2 0 3
1 3 0

Comment:

The graphs for the first two cases are shown below:

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)

The SBB want to bankrupt your start-up so they introduced the same feature into their own app. You have now queried all their pairwise prices and want to find out whether there is a rail network and StoflTickets offers, such that the prices correspond. If there are several solutions, you should first minimize the number of StoflTickets and then minimize the total length of the regular connections. If there are still several solutions with these additional criteria, you can output any of them.

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 contains the number of stations $N$ , followed by $N$ lines. The $j$ -th of these lines contains` N` integers $d_{j,k}$ separated by spaces, which indicates the price quoted for a journey between the stations $j$ and $k$ . For $j = k$ , $d_{j,j} = 0$ . In addition, $d_{j,k} = d_{k,j}$ .

Output

For the $i$ -th test case, if an input exists for subtask 1, which returns the $i$ -th test case as output, output a line “Case #i: OK”, followed by an input for subtask 1, which returns the $i$ -th test case as output, in the same format as in Subtask 1. Otherwise, output a line “Case #i: Inconsistent”.

Limits

$1 \le T \le 100$
$1 \le N \le 100$
for all $j\neq k$ : $1 \le d_{j,k} \le 10^{3}$

Example

Input:

Output:

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

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)

The task as well as input are the same as for Subtask 3.

Output

For the $i$ -th test case, if an input exists for Subtask 2 which returns the $i$ -th test case as output, output a line “Case #i: OK”, followed by an input for Subtask 2, which returns the $i$ -th test case as output, in the same format as in Subtask 2. Otherwise, output a line “Case #i: Inconsistent”.

Limits

$1 \le T \le 100$
$1 \le N \le 100$
for all $j\neq k$ : $1 \le d_{j,k} \le 10^{6}$

Example

Input:

3
5
0 5 15 25 30
5 0 10 20 25
15 10 0 10 15
25 20 10 0 5
30 25 15 5 0
5
0 5 15 6 1
5 0 10 11 6
15 10 0 10 15
6 11 10 0 5
1 6 15 5 0
3
0 1 2
1 0 10
2 10 0

Output:

Case #0: OK
5 4 0
0 1 5
1 2 10
2 3 10
3 4 5
Case #1: OK
5 5 0
0 1 5
0 4 1
1 2 10
2 3 10
3 4 5
Case #2: Inconsistent

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

Arc Match

Mouse Stofl is visiting his friends in Mousepore. Unlike in Switzerland, where each mouse lives in a single mouse hole, in Mousepore each mouse owns two holes. All holes in Mousepore are arranged in a single street on a straight line. As the mice have to commute quite frequently from one of their holes to the other one and this often leads to clashes, they ask Mouse Stofl for help to plan how to build non-intersecting connections. A connection is a path that connects two holes of a mouse directly (without using the street) and non-intersection means that a path can be drawn without crossing the street or another path (see visualization). Paths can either be built on the right or the left side of the street.

Subtask 1: Lim Chu Kang on the shore (10 points)

Since the street goes along the shoreline, the paths can only be built on the left side of the street.

Is it possible to do that without having two paths overlap?

Input

The first line contains the number of test cases $T$ . $T$ test cases follow, each with $N$ , the number of mice, on the first line. On the second line $2N$ numbers follow $x_{0},x_{1},\dots,x_{2N-1}$ . The $i$ -th hole is owned by mouse $0\le x_i<N$ , and each mouse owns exactly two holes.

Output

For the $i$ -th test case print a line “Case #i:” followed by “Possible” if it is possible to build the connection paths without having them intersect. If it is impossible to do so, then you should print “Impossible” instead.

Limits

$T=100$
$1 \le N \le 100$

Example

Input:

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

Output:

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

Case #1 (impossible):
*---*
| *-|-*
| | | |
0 1 0 1

Case #2 (possible):
        *-----*
*-* *-* | *-* |
| | | | | | | |
0 0 1 1 2 3 3 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: Kallang on the shore (10 points)

Same as before, but this time $1 \le N \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

Subtask 3: Tengah (10 points)

Now the area is surrounded by land, so the connections can be built on both sides. Is it possible now? If yes, print which path goes on which side.

Output

For the $i$ -th test case print a line “Case #i:” followed by $N$ characters L or R. If the $i$ -th character is “L”, this means that the two houses of mouse $i$ are connected by a path on the left, if the character is “R” they are connected on the right. If there are multiple possibilities, print any of them.

Limits

$T=100$
$1 \le N \le 10$

Example

Input:

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

Output:

Case #0: LLRL
Case #1: RLR
Case #2: Impossible
Case #3: RR
Case #4: RLRLRLRL

Comment:

In Case #0, other possibilities would be LLLR, RRLR or RRRL.

Case #1:
*-----*
|     |
1 2 0 1 0 2
  | |   | |
  | *---* |
  *-------*

Case #2 (impossible):
*-----*
|     |
1 2 0 1 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 4: River Valley (30 points)

Same as before, but this time $1 \le N \le 5\,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

Subtask 5: Bedok (40 points)

This time the city is very large: $1 \le N \le 500\,000$ .

Output

Only print Possible or Impossible (otherwise the output is too large to be uploaded).

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)$ (or $O(n\log n)$ or $O(n(\log n)^{2})$ ). 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).

Earthworm Surgery

Mouse Binna wants to become a surgeon one day. In her garden, she found the perfect test subjects on which she can practice and perfect her surgery skills: earthworms. Earthworms consists of light and dark brown segments. Depending on her mood, Mouse Binna likes some patterns more than others, so she tries to change the earthworms’ patterns to the ones she thinks fit them best.

Subtask 1: Earthworm Jane (20 points)

Mouse Binna’s surgery patient is Earthworm Jane. Mouse Binna figured out that applying a drop of citric acid to a segment of Earthworm Jane causes that segment to grow rapidly and change its color. A light segment will turn into two dark segments and a dark segment will turn into two light segments. As this causes Earthworm Jane to grow longer and longer, Mouse Binna may want to remove some segments. Based on experiments on some other earthworms, Mouse Binna determined that she can only remove $3$ consecutive dark segments or $3$ consecutive light segments. Any other surgery would end very badly for Earthworm Jane… Mouse Binna can switch between adding drops of citric acid and surgery operations at any time.

Currently, Earthworm Jane consists of $N$ segments with a specific pattern $s_{0}, {\dots}, s_{N-1}$ . Mouse Binna prefers the pattern $t_{0}, {\dots}, t_{M-1}$ . Can you help her figure out whether she can change the pattern to the one she desires?

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 two integers $N$ and $M$ – the current length of Earthworm Jane and her desired length. The second line contains $N$ characters $s_{0}, {\dots}, s_{N-1}$ , describing the initial pattern of Earthworm Jane. The character 1 is used to describe a light segment and 0 denotes a dark segment. The third line contains $M$ characters $t_{0}, {\dots}, t_{M-1}$ , describing the pattern Mouse Binna likes the most.

Output

For the $i$ -th test case print a line “Case #i:” followed by “YES” or “NO”, indicating whether Mouse Binna can turn Earthworm Jane’s pattern into the one Mouse Binna likes the most.

Limits

$T=100$
$1 \le N \le 100$
$1 \le M \le 100$

Example

Input:

Output:

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

Comment:

In case #0, Mouse Binna applies a drop of citric acid to Earthworm Jane’s only segment. In case #1, Mouse Binna first removes the first three dark segments, then she removes the last three dark segments. In case #2, no matter which operations Mouse Binna performs, the pattern will never be 00.

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: Earthworm Jim (20 points)

Earthworm Jane survived the surgery and she’s very happy with her new pattern. She has now invited her brother, Earthworm Jim, to Mouse Binna.

Mouse Binna has already figured out the optimal pattern for Earthworm Jim. Unfortunately Earthworm Jim behaves a bit differently: Applying a drop of citric acid to one of his light segments causes it to turn into $X$ dark segments and applying a drop of citric acid to one of his dark segments causes it to turn into $X$ light segments. Moreover, Earthworm Jim is a bit more sensitive to surgery, so Mouse Binna can only remove exactly $Y$ consecutive light segments or $Y$ consecutive dark segments from him.

Help her determine if she can give Earthworm Jim his optimal pattern.

Input

The first line contains the number of test cases $T$ . Each test case consists of three lines. The first line contains four integers $N$ , $M$ , $X$ , $Y$ – the current length of Earthworm Jim, the desired length of Earthworm Jim and two parameters describing how Earthworm Jim reacts to citric acid and his constraints on surgery. The second line contains $N$ characters $s_{0}, {\dots}, s_{N-1}$ , describing the initial pattern of Earthworm Jim. The character 1 is used to describe a light segment and 0 denotes a dark segment. The third line contains $M$ characters $t_{0}, {\dots}, t_{M-1}$ describing the optimal pattern for Earthworm Jim.

Output

For the $i$ -th test case print a line “Case #i:” followed by “YES” or “NO”, indicating whether Mouse Binna can give Earthworm Jim his optimal pattern.

Limits

$T=100$
$1 \le N \le 100$
$1 \le M \le 100$
$1 \le X < Y \le 100$

Example

Input:

Output:

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

Comment:

Case #0 is the same as case #0 of subtask 1. In case #1, Mouse Binna first removes the first four light segments and then removes the last four light segments. In case #2, Mouse Binna can’t change the length of Earthworm Jim.

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 (Theoretical): Even longer earthworms (60 points)

Earthworm Jim liked his new pattern (although he’s a bit dizzy from all the citric acid he’s received), so he’s told some of his friends about Mouse Binna’s surgery skills. They were quite impressed, so now Mouse Binna has a lot of work to do.

This is a theoretical subtask. Describe an algorithm that can solve subtask 2 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, i.e. explain why Mouse Binna can achieve her pattern if the algorithm prints “YES” and explain why it is impossible for Mouse Binna to achieve her pattern if the algorithm prints “NO”
how much time and memory it uses.

Limits

$N$ , $M$ , $X$ , $Y$ are variables. In your analysis, you may assume that $N$ and $M$ are around the same size and that both are much smaller than $Y$ . 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 + M + \log Y)$ runtime and $O(N+M)$ 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).

SOIway

In Soicity, the capital of Mouseland, a new subway system is supposed to be built, the SOIway. The mayor of Soicity has tasked her best engineer, Mouse Binna, to build the new system. Help Mouse Binna to optimally plan the SOIway lines.

The SOIway network consists of different stations. Over time, new stations are added, which need to be included in the network. For every station you are given their coordinates and their type. The distance between two stations with the coordinates $(x_{0}, y_{0})$ and $(x_{1}, y_{1})$ is equal to $\lceil \sqrt{(x_{1}- x_{0})^{2}+ (y_{1}- y_{0})^{2}} / 12 \rceil$ (i.e. the rounded up euclidean distance with a correction factor). A train traveling between two stations needs exactly the amount of distance many time steps. A stay in a station needs exactly one time step. Furthermore, you are given a list of passengers with their respective starting position, starting time and their destination type. The station where the passengers start is fixed, but the destination could be any station of the correct type. Time is defined as the number of time steps since the start of the simulation.

Your task is to determine which lines should operate on which stations and how many trains should be used on a given line. You should also specify when passengers board a train and when they get off. The passengers can change the train any number of times. You can reposition trains from a given line at most every $m$ timesteps. A train can maximally hold $u$ passengers. All lines, trains, stations, station types and passengers will be numbered separately and increasingly from $0$ .

In the beginning there are no stations, no passengers and you don’t have any trains or lines available. Those are added during the simulation, i.e. from time to time you will receive new lines and new trains, which can be used.

The goal is to operate the SOIway as long as possible, without overloading the network. The network is overloaded if there is a station with strictly more than $k$ passengers. This restriction is only enforced at the end of a turn. It’s no problem if there are too many people at a station during a turn.

Input

The first line contains some constants given as integers: $n$ $m$ $u$ $k$ $s$ $p$ $l$ $z$ . $s$ , $p$ , $l$ , $z$ , are the number of stations, passengers, lines and trains, which occur in the input. $n$ lines follow with events. A description of an event allways starts with an integer $t$ and a character $e$ , where $t$ is the point in time and $e$ the type of the event. The events are sorted by time. We now describe all event types:

e=′s′e = 's'e=′s′: New station. Four integers iii xxx yyy aaa follow, the index iii, the coordinates (x,y)(x, y)(x,y) and the type aaa of the station.
e=′p′e = 'p'e=′p′: New passenger. Three integers iii aaa bbb follow, the index iii of the passenger, the starting station aaa and the type bbb of their destination.
e=′l′e = 'l'e=′l′: New Line. An integer iii follows, the index iii of the line.
e=′z′e = 'z'e=′z′: New train. An integer iii follows, the index iii of the train.

Output

You should output a protocol of all actions you take. A description of an action always starts with an integer $t$ and a character $a$ , where $t$ is the point in time and $a$ the type of the action. The actions are sorted by time. Actions with the same point in time will be executed in the order of the protocol. We now describe all action types:

$a = 'r'$ : Defining a line. Two integers $l$ $a$ follow, the index $l$ of the line and $a$ , the number of stations. There follow $a$ integers $s_i$ , the indices $s_i$ of the stations on the line, in the order in which they should be visited. Trains on the line start their journey at $s_{0}$ and drive along the defined route. As soon as they reach station $s_{a-1}$ they continue to drive to $s_{0}$ and start their journey once again (“Loop”-operation). If you prefer “Ping-Pong”-operation you can achieve this by defining the route as $s_{0}$ , $s_{1}$ , …, $s_{a-2}$ , $s_{a-1}$ , $s_{a-2}$ , …, $s_{1}$ . The same action can be used to modify an existing line. A line can only be defined if no train is assigned to that line. So to modify a line, all assigned trains have to be removed first. A line can contain at most $2n$ stations.

$a = 'z'$ : Placing a train. Three integers $z$ $l$ $s$ follow, the index $z$ of the train, the index $l$ of the line and the index $s$ of the station within the line, where the train should start. A train can only be (re)placed if it is empty and was not placed in the last $m$ time steps. The train starts its journey from the given starting point and begins after a time step (in which a passenger could board) to drive right away. To temporarily remove a train, use $l = -1$ . For a temporarily removed train, there are no restrictions on when it can be placed again.

$a = 'e'$ : Boarding a passenger. Two integer $p$ $z$ follow, the index $p$ of the passenger and the index $z$ of the train which the passenger boards. A passenger can only board if there have been strictly less than $u$ passengers in the train before and if the train is located at the same station as the passenger. The train is located at the station exactly at the point in time where it arrives, i.e. at the time when it leaves, no more passenger can board.

$a = 'a'$ : Passenger getting off. Two integers $p$ $s$ follow, the index $p$ of the passenger and the index $s$ of the station where the passenger is getting off. If the station has the correct type, the passenger vanishes.

$a = 'd'$ : Debug output. The rest of the line will be displayed on the visualization at the corresponding time.

Limits

For each subtask we have:

$1 \le t \le 10^{8}$
$1 \le n \le 10^{8}$
$0 \le m \le 10^{8}$
$1 \le u \le 10^{3}$
$1 \le k \le 10^{6}$
$0 \le |x|, |y| \le 10^{3}$
$1 \le l \le 25$
$1 \le z \le 200$
$1 \le s \le 200$
$1 \le p \le 10^{7}$
$1 \le \#types \le 200$

Example

Input:

472 400 12 29 20 450 1 1
0 s 0 0 0 0
0 s 1 -18 -26 1
0 s 2 40 -55 2
0 s 3 -15 60 3
0 s 4 -97 -18 4
0 s 5 40 -15 5
0 s 6 -70 93 6
0 s 7 77 113 7
0 s 8 86 -119 8
0 s 9 142 2 9
...<snip>...
0 l 0
0 z 0
1 p 0 4 0
4 p 1 8 17
4 p 2 14 8
6 p 3 7 9
6 p 4 2 11
8 p 5 12 16
10 p 6 9 14
12 p 7 13 2
14 p 8 13 1
15 p 9 1 9
21 p 10 5 0
21 p 11 6 1
21 p 12 7 15
22 p 13 7 0
23 p 14 18 5
24 p 15 17 15
25 p 16 10 6
...<snip>...

Output:

27 r 0 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
27 z 0 0 0
27 e 17 0
...<snip>...
1459 a 17 15
...<snip>...

Additional Tools

You can find a Visualization here. You can also download it here together with a simple example in C++.

For the visualization, you just have to open the file soiwayviz.html in your browser. Afterwards, you can choose the input file, which you have downloaded, and the output file, which your program has generated, and let it display. With space you can start/stop the simulation, with the arrow-keys you can go back and forth (left and right) individual frames or adjust the speed (up and down with shift in integer steps).

Pro Tip: To avoid manually selecting the files, you could place a file debug_input.js in the same folder. This Javascript file has to define the two variables debug_input and debug_output (use Backticks ‘\`’ for strings on multiple lines). If you don’t choose any file in the Browser and click $Load$ , then this file will be read. This way you can write a small script which executes your program and automatically generates the file debug_input.js.

The example in C++ reads the entire Input and performs a few simple actions such as defining a line and boarding a passenger. This example obviously will not get any points, but you can use this as a template for your solution.

Subtask 1: Town (25 Points)

You have exactly one line and one train and all stations are available from the beginning. Each station has a different type. The input is fixed, i.e. every time you download an input you will get exactly the same file. You will get points depending on the number of passenger you managed to transport. If you did not transport all the passengers, you will get at most 60% of the points.

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 10 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: City (25 Points)

You have several lines and trains from the beginning and all the stations are available from the beginning. The input is fixed, i.e. every time you download an input you will get exactly the same file. You will get points dependent on the number of passenger you managed to transport. If you did not transport all the passengers, you will get at most 60% of the points.

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 10 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: Capital (25 Points)

There are no further restrictions. You will get points depending on the number of time steps reached before the network is overloaded. Let $p$ be this number. Then you will receive $25 \cdot \min(1, \sqrt{\frac{p}{4000}})$ points. The input is fixed, i.e., every time you download an input, you will get exactly the same file.

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 20 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: Metropolis (25 Points)

There are no further limits. You will get points depending on the performance of the other participants. On the SOI-Day, we will look at all the submissions and determine the best program. To submit a solution for this subtask, you have to score at least 15 points in subtask 3.

The input files, which will be used on the tournament, will be generated similarly to the inputs of subtask 3. In particular, the probabilities of the events and their parameters are the same. You can generate different inputs. You can also specify how large the input should be.

Input size

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

Junior Ranking

Rank	Username	Total (500)	marathon (100)	stickers (100)	bargain (100)	reversi (100)	sbb (100)
	loading ...

Regular Ranking

Rank	Username	Total (600)	bargain (100)	reversi (100)	sbb (100)	arcmatch (100)	earthwo… (100) earthwormsurgery	soiway (100)
	loading ...