Welcome to the Pre-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.

Contest ends at 2124-08-01T00:00:00+02:00

Task | Total | Subtask 1 | Subtask 2 | Subtask 3 | Subtask 4 | Subtask 5 |
---|---|---|---|---|---|---|

addition | ‒/100 | ‒/100 | ||||

books | ‒/100 | ‒/100 | ||||

cheeseparty | ‒/100 | ‒/50 | ‒/50 | |||

directions | ‒/100 | ‒/20 | ‒/20 | ‒/60 | ||

endurance | ‒/100 | ‒/20 | ‒/20 | ‒/20 | ‒/20 | ‒/20 |

You may use any programming language to solve the tasks of the pre-round. To solve a task, you have to design a program which solves the problem. If your solution is written in C++ you can directly submit your program on the website, which will grade your submission and display the number of points that you’ve earned as well as an explanation if you did not get all the possible points. If you used another programming language, you have to download an input file, run the program on the data in that file, write the results in another file and upload it along with the source code to the website.

In order to read the data in the input file, make sure that your program either reads directly in that file or redirect the standard input to it (in a terminal running on Linux, Windows or OS X, you can do that by using the command ‘yourprogram < inputfile’, replacing ‘yourprogram’ and ‘inputfile’ by the paths to the actual program and input file).

More elaborate explanations about how to solve the tasks of the pre-round await you on our wiki and our training page. Note that in case you get stuck on the tasks, you can move to next task and try again later: no need to solve them in order.

Don’t hesitate to contact us at info@soi.ch if you have any question about programming or the tasks.

Mouse Stofl is planning to visit the pyramids together with Mouse Binna during their trip to Egypt. However, they both would like to bring a number of friends with them. Help Stofl figure out how many tickets he has to buy, such that every friend gets one, but he doesn’t waste money unnecessarily by buying too many tickets.

You are given two integers, $A$ and $B$, $A$ containing the size of Stofl’s friend group (including Stofl), and $B$ containing the size of Binna’s friend group (including Binna). Output the sum of the numbers $A$ and $B$.

The first line contains two numbers, $A$ and $B$.

Output a line containing a single number, the sum of $A$ and $B$.

Both numbers $A$ and $B$ are smaller than 1000.

$0 \le A, B < 1000$

Input:

10 5

Output:

15

Comment:

The sum of 10 and 5 is 15, so you should output 15 in this case.

To submit for this subtask, please log in.

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

Mouse Stofl likes books, and therefore, each of his friends gives him some books as gifts. He’d like to know how many books there are in total.

Please help Mouse Stofl to calculate the total number of books.

The first line contains an integer $N$, representing the number of Mouse Stofl’s friends.

The second line contains $N$ integers $b_i$ ($0 \le i < N$), each representing the number of books that one friend gives to Mouse Stofl.

A single number, the total number of books that Mouse Stofl has received.

$1 \le N \le 1000$

$1 \le b_i \le 1000$

Input:

5 1 2 3 1 2

Output:

9

Comment:

As $1 + 2 + 3 + 1 + 2 = 9$, so there are $9$ books in total.

To submit for this subtask, please log in.

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

Mouse Stofl is in the process of organising his annual Cheeseparty. He wants to invite $N$ mouse families. Each family Stofl wants to invite consist of the same family members: 2 parent mice and $K$ children.

Stofl of course needs to make sure there is enough cheese for all mice at the party. Each mouse which comes to the party, that means every family member and Stofl, would like $S$ pieces of cheese.

Help Stofl calculate how many pieces of cheese he has to order at the cheese dairy in order for there to be exactly $S$ pieces for every mouse coming.

You get three integers, $N$, $K$ and $S$. $N$ is the amount of families that Stofl wants to invite, $K$ the amount of children in each family and $S$ the amount of pieces of cheese every mouse would like at the party.

You need to calculate the amount of pieces of cheese Stofl needs to order.

The first and only line contains three integers, $N$, $K$ and $S$.

Print a single number, the amount of pieces of cheese Stofl needs to order.

The numbers $N$, $K$ and $S$ are less than 100.

$0 \le N, K, S < 100$

Input:

4 3 6

Output:

126

Comment:

At the party there will be 4 families with 5 members each (3 kids und 2 parents) and Stofl. The families and Stofl result in a total of 21 mice, each of which would like 6 pieces of cheese resulting in a total of 126 pieces of cheese.

To submit for this subtask, please log in.

You get four integers, $N$, $K$, $S$ and $R$. $N$ is the amount of families that Stofl wants to invite, $K$ the amount of children in each family, $S$ the amount of pieces of cheese every mouse would like at the party and $R$ is the result that Stofl has calculated.

You need to check whether Stofl’s calculation was correct or not.

The first and only line contains four integers, $N$, $K$, $S$ and $R$.

Print `YES` if Stofl’s calculation was correct, otherwise print `NO`.

The numbers $N$, $K$ and $S$ are less than 100. $R$ is less than $2\,000\,000$

$0 \le N, K, S < 100$, $0 \le R < 2\,000\,000$

Input:

4 3 6 120

Output:

NO

Input:

4 3 6 126

Output:

YES

To submit for this subtask, please log in.

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

Mouse Binna and Mouse Stofl got lost on their vacation and don’t find their hotel anymore. Both of them asked a stranger for directions how to get back. Each of them were told a series of instructions, either “l” for left or “r” for right. However, as Mouse Stofl doesn’t have a very good memory, it is possible that he forgot the last few instructions he was told. Now they wonder whether they can trust the instructions or if one of the strangers was a liar! They only want to know if all the directions Stofl remembers match the directions of Binna. Can you help them?

Formally, you need to output “YES” if the directions Mouse Stofl remembers are a prefix of the directions Mouse Binna got. Otherwise, you should output “NO”.

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

The first line of the test case contains the string $b$ — the directions Mouse Binna got.

The second line contains the string $s$ — the directions Mouse Stofl got.

It is guaranteed that both strings $b$ and $s$ contain only the letters “l” standing for left and “r” standing for right.

For the $i$-th test case, output a line “`Case #i: YES`” if Stofl’s directions match exactly the beginning of Binna’s directions, or “`Case #i: NO`” otherwise.

In this subtask Stofl tried very hard to focus and managed to remember all of the instructions. The length of Binna’s directions is equal to the length of Stofl’s directions.

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

- $1 \le |b| = |s| \le 100$

where $|b|$ is the length of $b$ and $|s|$ is the length of $s$.

Input:

3 rrlr rrrr lrrrl lrrrl rrll llrr

Output:

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

To submit for this subtask, please log in.

In this subtask, Mouse Stofl was only able to remember the first instruction he was told.

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

- $1 \le |b| \le 100$
- $|s| = 1$

where $|b|$ is the length of $b$ and $|s|$ is the length of $s$.

Input:

3 llrlrr l llrlrr r rrl r

Output:

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

Comment:

To submit for this subtask, please log in.

In this subtask there are no further restrictions.

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

- $1 \le |b| \le 100$
- $1 \le |s| \le 100$

where $|b|$ is the length of $b$ and $|s|$ is the length of $s$.

Input:

4 rrlrl rrl lrrrl llrr lr lrrr llrr llrr

Output:

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

To submit for this subtask, please log in.

In anticipation of the Olympic games, 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.

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.

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.

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.

- $T=100$
- $N = 3$

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

To submit for this subtask, please log in.

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

The input format is the same as in subtask 1.

The output format is the same as in subtask 1.

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

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

The input format is the same as in subtask 1.

The output format is the same as in subtask 1.

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

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.

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.

The output format is the same as in subtask 1

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

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

To submit for this subtask, please log in.

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

The input format is the same as in subtask 4.

The output format is the same as in subtask 1.

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