Pre-Round - Swiss Olympiad in Informatics

Overview

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.

The preround can be solved at any time and runs during the whole year.

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

Tips

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.

Addition

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.

Subtask 1 (100 points)

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

Input

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

Output

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

Limits

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

$0 \le A, B < 1000$

Example

Input:

10 5

Output:

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

Books

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.

Subtask 1 (100 points)

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

Input

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.

Output

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

Limits

$1 \le N \le 1000$

$1 \le b_i \le 1000$

Example

Input:

5
1 2 3 1 2

Output:

Comment:

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

Cheeseparty

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.

Subtask 1 (50 points)

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.

Input

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

Output

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

Limits

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

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

Example

Input:

4 3 6

Output:

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.

Subtask 2 (50 points)

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.

Input

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

Output

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

Limits

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$

Example

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

Directions

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

Input

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

The first line of the test case contains 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.

Output

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.

Subtask 1: Very good memory (20 points)

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.

Limits

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

Example

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.

Subtask 2: Very bad memory (20 points)

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

Limits

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

Example

Input:

3
llrlrr
l
llrlrr
r
rrl
r

Output:

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

Comment:

Case #0: The instruction Stofl remembered is left which is the same as the first instruction Binna got.

Case #1: The instruction Stofl remembered is right but the first instruction of Binna is left.

To submit for this subtask, please log in.

Subtask 3: General case (60 points)

In this subtask there are no further restrictions.

Limits

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

Example

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.

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

Endurance

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.

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

To submit for this subtask, please log in.

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.

To submit for this subtask, please log in.

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.

To submit for this subtask, please log in.

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

To submit for this subtask, please log in.

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.

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