First Round SOI 2019/2020

Overview

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

This contest is over.

CategoryTaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
Junior onlymarathon‒/100‒/20‒/20‒/20‒/20‒/20
Junior onlystickers‒/100‒/10‒/20‒/20‒/20‒/30
Bothbargain‒/100‒/10‒/25‒/25‒/15‒/25
Bothreversi‒/100‒/10‒/20‒/20‒/50
Bothsbb‒/100‒/25‒/25‒/25‒/25
Regular onlyarcmatch‒/100‒/10‒/10‒/10‒/30‒/40
Regular onlyearthwormsurgery‒/100‒/20‒/20‒/60
Regular onlysoiway‒/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 TT. TT test cases follow in the following format:

  • The first line of the test case contains the length NN of the road.
  • The second line consists of NN numbers pip_i describing the road, where pi=1p_i=1 if there is a hole at this spot and pi=0p_i=0 otherwise.

Output

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

Limits

  • T=100T=100
  • N=3N = 3

Examples

Input:

2
3
1 0 0
3
0 1 0

Output:

Case #0: 2
Case #1: 1

Comment:

  • In case #0, the longest possible track would be from position 11 to position 22 included (the road is 00-based) so the length is 22.
  • In case #1, there are 22 longest possible tracks all with length 11, which are at positions 00 and 22.

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

Download input again
You have 5 minutes and 0 seconds left.

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=100T=100
  • 1N1001\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.

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=100T=100
  • 1N1051\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.

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 KK holes. Help Mouse Binna find out what is the longest marathon she can organise now by fixing at most KK holes.

Input

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

  • The first line of the test case contains the length NN of the road and the number KK of holes that can be fixed.
  • The second line consists of NN numbers pip_i describing the road where pi=1p_i=1 if there is a hole and pi=0p_i=0 otherwise.

Output

The output format is the same as in subtask 1

Limits

  • T=100T=100
  • 1N1001\le N\le 100
  • K=3K=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 33 holes so the length is 1010.
  • In case #1, the longest possible track is from position 22 to position 99 by fixing the 33 holes that are in that section so the length is 88.

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

Download input again
You have 5 minutes and 0 seconds left.

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=100T=100
  • 1N1051\le N\le 10^{5}
  • 1K1001\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.

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=3N = 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 TT. TT test cases follow, in the following format:

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

The second line contains NN numbers a0,,aN1a_{0},\ldots,a_{N-1}, where aja_j represents the family of the jj-th sticker. The cost of trading one sticker of one family for a sticker of another family is 11 Swiss franc.

Output

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

Limits

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

Example

Input:

2
3 1
1 2 1
3 1
1 2 3

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 22 for one of his friends’ stickers which belongs to family 11. 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.

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 NN is not necessarily 33 anymore. Note that there are now many more families in the game than before (aj106a_j \le 10^{6}).

Limits

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

Example

Input:

3
3 1
1 3 2
5 1
1 3 3 2 1
4 1
1 1 9 10

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 11. He trades the rest away in exchange for stickers of family 11.

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.

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 KK is not restricted to 11 anymore.

Input/output

Same as in subtask 1 but KK is not necessarily 11 anymore.

Limits

There are T=100T=100 test cases. In all test cases 1N10001 \le N \le 1000, 1KN1 \le K \le N and 1aj1061 \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 11 and 55 to achieve this.

In case #2, Stofl decides to trade away stickers belonging to family 22 and 11.

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.

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 aa is worth aa Swiss francs. Stofl now trades according to the following rules:

  • Stofl never wants to downgrade a sticker from family aa into family bb with b<ab<a.
  • Stofl’s friends charge him bab-a Swiss francs if Stofl wants to trade a sticker of family aa against a sticker of family bb (with b>ab>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. KK is always equal to 22.

Limits

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

Example

Input:

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

Output:

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

Comment:

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

In case #1, Stofl trades the stickers belonging to families 77 and 88 for two stickers of family 1010. Additionaly he trades a sticker of family 44 for one of family 55.

In case #2, Stofl trades for stickers belonging to families 22 and 44.

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.

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=100T=100 test cases. In all test cases 1N1001 \le N \le 100, 1KN1 \le K \le N and 1aj1061 \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 33 for one of family 44.

In case #1, Stofl can trade sticker of family 66 for one of family 88. He then trades his two stickers belonging to family 33 for stickers of family 44. Finally, he trades his stickers of family 11 for stickers belonging to family 22. The total cost is (86)+2(43)+2(21)=6(8-6)+2(4-3)+2(2-1) = 6.

In case #2, Stofl trades the sticker belonging to family 88 for one of family 99.

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.

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 TT. TT test cases follow, in the following format:

  • The first line of the test case contains b0b_{0} and s0s_{0}, the buying price and selling prices in Mouse Binna’s home city (from Mouse Binna’s point of view).
  • The second line contains b1b_{1} and s1s_{1}, the buying and selling prices in the city in which the workshop takes place.

Output

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

Limits

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

  • 1si<bi1001 \le s_i < b_i \le 100 for every 0i10 \le i \le 1.

Example

Input:

2
4 2
7 6
8 5
3 2

Output:

Case #0: 2
Case #1: 0

Comment:

  • In case #0, the best option is to buy cheese in the first city for CHF 44 and sell it in the second city for CHF 66, making CHF 22 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.

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 NN 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 TT. TT test cases follow in the following format:

  • The first line of the test case contains NN, the number of cities visited by Moues Binna.
  • There follow NN lines, the ii-th of which contains bib_i and sis_i, the buying and selling prices in the ii-th city visited by Mouse Binna.

Output

Same as in subtask 1.

Limits

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

  • 2N10002 \le N \le 1000.
  • 1si<bi10000001 \le s_i < b_i \le 1\,000\,000 for every 0i<N0 \le i < N.

Example

Input:

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

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.

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 KK loafs of cheese. Of course, she can buy less than KK 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 TT. TT test cases follow in the following format:

  • The first line of the test case contains NN and KK, the number of cities visited by Mouse Binna and the maximal number of cheese loafs she can buy.
  • There follow NN lines, the ii-th of which contains bib_i and sis_i, the buying and selling prices in the ii-th city visited by Mouse Binna.

Output

Same as in subtasks 1 and 2.

Limits

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

  • 2N5000002 \le N \le 500\,000.
  • 1K10000001 \le K \le 1\,000\,000
  • 1si<bi10000001 \le s_i < b_i \le 1\,000\,000 for every 0i<N0 \le i < N.

Example

Input:

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

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.

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 CC 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 TT. TT test cases follow in the following format:

  • The first line of the test case contains NN and CC, the number of cities visited by Mouse Binna and the maximal number of cheese loafs she can carry at any time.
  • There follow NN lines, the ii-th of which contains bib_i and sis_i, the buying and selling prices in the ii-th city visited by Mouse Binna.

Output

Same as in subtasks 1 to 3.

Limits

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

  • 2N10002 \le N \le 1000.
  • 1C10001 \le C \le 1\,000
  • 1si<bi10000001 \le s_i < b_i \le 1\,000\,000 for every 0i<N0 \le i < N.

Example

Input:

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

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.

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 NN can be much larger.

Input

Same as in subtask 4.

Output

Same as in subtasks 1 to 4.

Limits

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

  • 2N5000002 \le N \le 500\,000.
  • 1C10000001 \le C \le 1\,000\,000
  • 1si<bi10000001 \le s_i < b_i \le 1\,000\,000 for every 0i<N0 \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.

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 NN 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 TT. This is followed by TT test cases in the following format:

The first line of the test case contains NN, the number of discs. A second line follows with a bitstring SS containing NN 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 SS contains at least one 0 and one 1. The third line contains a character DD and a bit BB 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 ii-th test case, output a single line “Case #i: R”, where RR is the bitstring representing the state after the operation. RR should only contain 0’s and 1’s.

Limits

  • T=100T=100
  • 2N1000002 \le N \le 100\,000
  • D=LD = 'L' or D=RD = 'R'
  • B=0B = 0 or B=1B = 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.

Subtask 2: Few Turns (20 points)

You are given an arrangement of NN 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 TT. TT test cases follow in the following format:

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

Output

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

Limits

  • T=100T=100
  • 2N10000002 \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.

Subtask 3: Low Cost (20 points)

Again, an arrangement of NN 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 ii-th test case, output a single line “Case #i: M”, where MM is the minimum cost.

Limits

  • T=100T=100
  • 2N10002 \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.

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(N3)O(N^{3}) O(N3)O(N^{3}) 10
O(N2)O(N^{2}) O(N2)O(N^{2}) 20
O(N2)O(N^{2}) O(N)O(N) 25
O(N2)O(N^{2}) O(1)O(1) 30
O(N)O(N) O(N)O(N) 40
O(N)O(N) O(1)O(1) 50

If you are not familiar with the O()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 NN stations and MM 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 lil_i kilometers and the price of an ordinary billet on a stretch of length lil_i is lil_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 SS 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 TT. This is followed by TT test cases in the following format:

The first line contains three integers: NN, MM, SS. The next MM lines indicate a route. The ii-th of these lines consists of three integers: aia_i, bib_i, lil_i, which specify the two terminus stations aia_i, bib_i, and the length lil_i of the route. The next SS lines describe a StoflTicket. The ii-th of these lines consists of three integers: aia_i, bib_i, pip_i, which specify the two terminus stations aia_i, bib_i, and the special price pip_i of this StoflTicket.

Output

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

Limits

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

In each test case:

  • 1N1001 \le N \le 100
  • N1M104N - 1 \le M \le 10^{4}
  • 0S1040 \le S \le 10^{4}
  • 0ai,bi<N0 \le a_i, b_i < N, aibia_i \neq b_i
  • li=pi=1l_i = p_i = 1

Example

Input:

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

Output:

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

Comment:

The graphs for the first two cases are shown below:
111101234 1111101234

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.

Subtask 2 (25 points)

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

Limits

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

In each test case:

  • 1N1001 \le N \le 100
  • N1M104N - 1 \le M \le 10^{4}
  • 0S1040 \le S \le 10^{4}
  • 0ai,bi<N0 \le a_i, b_i < N, aibia_i \neq b_i
  • 1li,pi1061 \le l_i, p_i \le 10^{6}

Example

Input:

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

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:
510105101234 51010501234

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.

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 TT. This is followed by TT test cases in the following format:

The first line contains the number of stations NN, followed by NN lines. The jj-th of these lines contains` N` integers dj,kd_{j,k} separated by spaces, which indicates the price quoted for a journey between the stations jj and kk. For j=kj = k, dj,j=0d_{j,j} = 0. In addition, dj,k=dk,jd_{j,k} = d_{k,j}.

Output

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

Limits

  • 1T1001 \le T \le 100
  • 1N1001 \le N \le 100
  • for all jkj\neq k: 1dj,k1031 \le d_{j,k} \le 10^{3}

Example

Input:

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

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.

Subtask 4 (25 points)

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

Output

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

Limits

  • 1T1001 \le T \le 100
  • 1N1001 \le N \le 100
  • for all jkj\neq k: 1dj,k1061 \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.

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 TT. TT test cases follow, each with NN, the number of mice, on the first line. On the second line 2N2N numbers follow x0,x1,,x2N1x_{0},x_{1},\dots,x_{2N-1}. The ii-th hole is owned by mouse 0xi<N0\le x_i<N, and each mouse owns exactly two holes.

Output

For the ii-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=100T=100
  • 1N1001 \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.

Subtask 2: Kallang on the shore (10 points)

Same as before, but this time 1N1000001 \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.

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 ii-th test case print a line “Case #i:” followed by NN characters L or R. If the ii-th character is “L”, this means that the two houses of mouse ii 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=100T=100
  • 1N101 \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.

Subtask 4: River Valley (30 points)

Same as before, but this time 1N50001 \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.

Subtask 5: Bedok (40 points)

This time the city is very large: 1N5000001 \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)O(n) (or O(nlogn)O(n\log n) or O(n(logn)2)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.

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 33 consecutive dark segments or 33 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 NN segments with a specific pattern s0,,sN1s_{0}, {\dots}, s_{N-1}. Mouse Binna prefers the pattern t0,,tM1t_{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 TT. TT test cases follow, each test case consists of three lines. The first line contains two integers NN and MM – the current length of Earthworm Jane and her desired length. The second line contains NN characters s0,,sN1s_{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 MM characters t0,,tM1t_{0}, {\dots}, t_{M-1}, describing the pattern Mouse Binna likes the most.

Output

For the ii-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=100T=100
  • 1N1001 \le N \le 100
  • 1M1001 \le M \le 100

Example

Input:

3
1 2
0
11
7 1
0001000
1
1 2
0
00

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.

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 XX dark segments and applying a drop of citric acid to one of his dark segments causes it to turn into XX light segments. Moreover, Earthworm Jim is a bit more sensitive to surgery, so Mouse Binna can only remove exactly YY consecutive light segments or YY 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 TT. Each test case consists of three lines. The first line contains four integers NN, MM, XX, YY – 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 NN characters s0,,sN1s_{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 MM characters t0,,tM1t_{0}, {\dots}, t_{M-1} describing the optimal pattern for Earthworm Jim.

Output

For the ii-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=100T=100
  • 1N1001 \le N \le 100
  • 1M1001 \le M \le 100
  • 1X<Y1001 \le X < Y \le 100

Example

Input:

3
1 2 2 3
0
11
9 1 3 4
111101111
0
3 5 1 123
000
11111

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.

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

  • NN, MM, XX, YY are variables. In your analysis, you may assume that NN and MM are around the same size and that both are much smaller than YY. 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+logY)O(N + M + \log Y) runtime and O(N+M)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 (x0,y0)(x_{0}, y_{0}) and (x1,y1)(x_{1}, y_{1}) is equal to (x1x0)2+(y1y0)2/12\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 mm timesteps. A train can maximally hold uu passengers. All lines, trains, stations, station types and passengers will be numbered separately and increasingly from 00.

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 kk 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: nn mm uu kk ss pp ll zz. ss, pp, ll, zz, are the number of stations, passengers, lines and trains, which occur in the input. nn lines follow with events. A description of an event allways starts with an integer tt and a character ee, where tt is the point in time and ee the type of the event. The events are sorted by time. We now describe all event types:

e=se = 's': New station. Four integers ii xx yy aa follow, the index ii, the coordinates (x,y)(x, y) and the type aa of the station.
e=pe = 'p': New passenger. Three integers ii aa bb follow, the index ii of the passenger, the starting station aa and the type bb of their destination.
e=le = 'l': New Line. An integer ii follows, the index ii of the line.
e=ze = 'z': New train. An integer ii follows, the index ii of the train.

Output

You should output a protocol of all actions you take. A description of an action always starts with an integer tt and a character aa, where tt is the point in time and aa 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=ra = 'r': Defining a line. Two integers ll aa follow, the index ll of the line and aa, the number of stations. There follow aa integers sis_i, the indices sis_i of the stations on the line, in the order in which they should be visited. Trains on the line start their journey at s0s_{0} and drive along the defined route. As soon as they reach station sa1s_{a-1} they continue to drive to s0s_{0} and start their journey once again (“Loop”-operation). If you prefer “Ping-Pong”-operation you can achieve this by defining the route as s0s_{0}, s1s_{1}, …, sa2s_{a-2}, sa1s_{a-1}, sa2s_{a-2}, …, s1s_{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 2n2n stations.

a=za = 'z': Placing a train. Three integers zz ll ss follow, the index zz of the train, the index ll of the line and the index ss 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 mm 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=1l = -1. For a temporarily removed train, there are no restrictions on when it can be placed again.

a=ea = 'e': Boarding a passenger. Two integer pp zz follow, the index pp of the passenger and the index zz of the train which the passenger boards. A passenger can only board if there have been strictly less than uu 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=aa = 'a': Passenger getting off. Two integers pp ss follow, the index pp of the passenger and the index ss of the station where the passenger is getting off. If the station has the correct type, the passenger vanishes.

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

Limits

For each subtask we have:

  • 1t1081 \le t \le 10^{8}
  • 1n1081 \le n \le 10^{8}
  • 0m1080 \le m \le 10^{8}
  • 1u1031 \le u \le 10^{3}
  • 1k1061 \le k \le 10^{6}
  • 0x,y1030 \le |x|, |y| \le 10^{3}
  • 1l251 \le l \le 25
  • 1z2001 \le z \le 200
  • 1s2001 \le s \le 200
  • 1p1071 \le p \le 10^{7}
  • 1#types2001 \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 LoadLoad, 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.

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.

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 pp be this number. Then you will receive 25min(1,p4000)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.

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.

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.

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

Junior Ranking

RankUsernameTotal (500)marathon (100)stickers (100)bargain (100)reversi (100)sbb (100)
loading ...

Regular Ranking

RankUsernameTotal (600)bargain (100)reversi (100)sbb (100)arcmatch (100)earthwo… (100)
earthwormsurgery
soiway (100)
loading ...