Pre-Round

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.

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

TaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 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, AA and BB, AA containing the size of Stofl’s friend group (including Stofl), and BB containing the size of Binna’s friend group (including Binna). Output the sum of the numbers AA and BB.

Input

The first line contains two numbers, AA and BB.

Output

Output a line containing a single number, the sum of AA and BB.

Limits

Both numbers AA and BB are smaller than 1000.

0A,B<10000 \le A, B < 1000

Example

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

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 NN, representing the number of Mouse Stofl’s friends.

The second line contains NN integers bib_i (0i<N0 \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

1N10001 \le N \le 1000

1bi10001 \le b_i \le 1000

Example

Input:

5
1 2 3 1 2

Output:

9

Comment:

As 1+2+3+1+2=91 + 2 + 3 + 1 + 2 = 9, so there are 99 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 NN mouse families. Each family Stofl wants to invite consist of the same family members: 2 parent mice and KK 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 SS 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 SS pieces for every mouse coming.

Subtask 1 (50 points)

You get three integers, NN, KK and SS. NN is the amount of families that Stofl wants to invite, KK the amount of children in each family and SS 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, NN, KK and SS.

Output

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

Limits

The numbers NN, KK and SS are less than 100.

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

Example

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.

Subtask 2 (50 points)

You get four integers, NN, KK, SS and RR. NN is the amount of families that Stofl wants to invite, KK the amount of children in each family, SS the amount of pieces of cheese every mouse would like at the party and RR 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, NN, KK, SS and RR.

Output

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

Limits

The numbers NN, KK and SS are less than 100. RR is less than 20000002\,000\,000

0N,K,S<1000 \le N, K, S < 100, 0R<20000000 \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 TT. The TT test cases follow in the following format:

The first line of the test case contains the string bb — the directions Mouse Binna got.
The second line contains the string ss — the directions Mouse Stofl got.

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

Output

For the ii-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=100T=100 test cases. In each test case we have:

  • 1b=s1001 \le |b| = |s| \le 100

where b|b| is the length of bb and s|s| is the length of ss.

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=100T=100 test cases. In each test case we have:

  • 1b1001 \le |b| \le 100
  • s=1|s| = 1

where b|b| is the length of bb and s|s| is the length of ss.

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=100T=100 test cases. In each test case we have:

  • 1b1001 \le |b| \le 100
  • 1s1001 \le |s| \le 100

where b|b| is the length of bb and s|s| is the length of ss.

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

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

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