First Round SOI 2017

Overview

Here you can see, which tasks you have already solved. Don’t let anything stop you from picking a task at the top and getting on it!

Here you can find information and details about the first round.

We’d happily give you an introduction during one of the workshops.

numberriddle (0/100)0/250/250/250/25
superpowers (0/100)0/200/200/200/200/20
cupsort (0/100)0/100/200/200/200/30
funny (0/100)0/100/100/100/250/100/35
dissertation (0/100)0/100/200/200/200/30
submarine (0/100)0/250/250/50

Number riddle

Mouse Amir loves riddles and mathematics. Whenever he travels alone, he creates and solves puzzle games to make time pass faster. His favourite game is called the number riddle. The goal of the game is to create a valid equation out of randomly picked numbers. Amir prefers a simple version, where he is only allowed to perform additions and subtractions. He randomly picks numbers and places  +  and  −  in between. Even though it’s tempting to use the  −  to create signed numbers, Amir strictly uses is as an operator between two values.

Subtask 1: Warm up (25 points)

Mouse Amir always starts with an easy task. He picks two random numbers: n0, n1 and a target value R. Amir now tests if he can reach the value R by adding the two numbers or subtracting the second number from the first number.

Input

The first line contains one integer T, the number of test cases. Each test case consists of two lines: The first line contains two integers: N, the number of values Amir picks and R, the value he tries to reach. The second line contains N integers: ni, the numbers Amir adds or subtracts from each other.

Output

For the i-th test case, display a single line “Case #i: YES”, if it is possible to reach the number, “Case #i: NO” if not.

• T = 100
• N = 2
• 0 ≤ R = 15
• 0 ≤ ni ≤ 10

Examples

Input:

3
2 5
2 3
2 5
8 3
2 6
2 8

Output:

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

Comment:

The first two calculations are 2 + 3 = 5 and 8 − 3 = 5.
For the third case, 2 + 8 = 10 and 2 − 8 =  − 6 both are unequal to 6.

Subtask 2: One subtraction (25 points)

Mouse Amir is quite good at mental arithmetics. Adding a few dozen numbers is a piece of cake. However, he doesn’t like to subtract numbers. As before, he thinks of a series of numbers and tries to insert an operator between them. Using all numbers, is it possible to reach R with at most one subtraction?

Input

The input format is the same as in subtask 1. The first line contains one integer T, the number of test cases. Each test case consists of two lines: The first line contains two integers: N, the number of numbers Amir picks and R, the number he tries to reach. The second line contains N integers: ni, the numbers Amir adds or subtracts from each other.

Output

The output format is the same as in subtask 1. For the i-th test case, display a single line “Case #i: YES”, if it is possible to reach the number, “Case #i: NO” if not.

Limits

• T = 100
• 2 ≤ N ≤ 100
• 0 ≤ R = 10000
• 0 ≤ ni ≤ 100

Examples

Input:

3
2 5
2 3
3 5
3 8 10
3 5
8 3 10

Output:

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

Comment:

Case #1: 2 + 3 = 5
Case #2: 3 − 8 + 10 = 5
Case #3:  − 8 + 3 + 10 = 5 is invalid, the  −  can’t be used as a sign.

Subtask 3: Two subtractions (25 points)

Mouse Amir realises that with more subtractions it is more likely to build an equation. As before, he thinks of a series of numbers and tries to insert an operator between them. Using all numbers, is it possible to reach R with at most two subtraction?

Input

The input format is the same as in subtask 1. The first line contains one integer T, the number of test cases. Each test case consists of two lines: The first line contains two integers N, the number of numbers Amir picks and R, the number he tries to reach. The second line contains N integers ni, the numbers Amir adds or subtracts from each other.

Output

The output format is the same as in subtask 1. For the i-th test case, display a single line “Case #i: YES”, if it is possible to reach the number, “Case #i: NO” otherwise.

Limits

• T = 100
• 2 ≤ N ≤ 100
• 0 ≤ R = 10000
• 0 ≤ ni ≤ 100

Examples

Input:

2
3 5
16 8 3
3 8
16 10 2

Output:

Case #1: YES
Case #2: YES

Comment:

Case #1: 16 − 8 − 3 = 5
Case #2: 16 − 10 + 2 = 8 fewer subtractions are still a valid possibility.

Subtask 4: Countless possibilities (25 points)

Mouse Stofl learns about Amir’s game and they start playing it together. Unlike the previous tasks, the number of subtractions is unlimited. As before, all the numbers have to be used.

Mouse Stofl is a MOI (Mouse Olympiad in Informatics) participant. By reading the provided scripts and attending the workshops he learned about an elegant solution.

Input

The input format is the same as in subtask 1. The first line contains one integer T, the number of test cases. Each test case consists of two lines: The first line contains two integers: N, the number of numbers Amir picks and R, the number he tries to reach. The second line contains N integers: ni, the numbers Amir adds or subtracts from each other.

Output

The output format is the same as in subtask 1. For the i-th test case, display a single line “Case #i: YES”, if it is possible to reach the number, “Case #i: NO” otherwise.

Limits

• T = 100
• 2 ≤ N ≤ 100
• 0 ≤ R ≤ 10 000
• 0 ≤ ni ≤ 100

Examples

Input:

4
3 5
16 8 3
3 8
16 10 2
3 8
4 2 2
3 8
2 4 6

Output:

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

Comment:

Case #1: 16 − 8 − 3 = 5
Case #2: 16 − 10 + 2 = 8
Case #3: 4 + 2 + 2 = 8
Case #4:  − 2 + 4 + 6 = 8 but the  −  can’t be used as a sign.

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

Superpowers

Mouse Stofl invented a device which allows him to transform superheroes such that they change the side (i.e. the good ones get bad and vice versa). He plans to use this device at the next superhero convention. Help him save the world and remove the power from the bad superheroes.

Each superhero has a strength k (an integer). If he is bad it holds k < 0, otherwise k > 1 (i.e. he is good). When the device is used on a superhero, the new strength is  − k. To determine which side is stronger Stofl sums up all strengths. Help him maximize this sum S.

Subtask 1 (20 points)

You have to choose C times a superhero on which the device is applied. You can choose one hero several times.

Input

The first line contains one integer T, the number of test cases.

For each test case there is one line with an integer C (see description), an integer N (number of superheroes) and N space separated integers, the strengths of the superheroes.

Output

Print for each test case one line with “Case #i: S” where i is the index of the test case (first test case is i = 1) and S is the sum we are looking for.

Limits

• T = 100
• 0 ≤ C ≤ 104
• 1 ≤ N ≤ 104
• 1 ≤ |k| ≤ 106

Samples

Input:

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Output:

Case #1: 15
Case #2: 15
Case #3: 17

Comment:

We choose the superheroes with the following strengths:
Case #1: -3, 1, -7
Case #2: 1, 1
Case #3: -7, 1, 1, 3, 3

Subtask 2 (20 points)

You have to choose exactly C different superheroes.

Input

Same as for subtask 1.

Output

Same as for subtask 1.

Attention: the sum we are looking for can get too big for a 32-bit integer (use for example in C++ long long int instead of int to prevent this problem).

Limits

• T = 100
• 0 ≤ C ≤ 104
• 1 ≤ N ≤ 104
• C ≤ N
• 1 ≤ |k| ≤ 106

Samples

Input:

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Output:

Case #1: 15
Case #2: 9
Case #3: -3

Comment:

We choose the superheroes with the following strengths:
Case #1: -3, 1, -7
Case #2: 1, 2
Case #3: -7, 1, 2, 3, 4

Subtask 3 (20 points)

You have to choose C continuous heroes on which the device should be applied. The heroes stand in a line which means the first and the last one are not neighbors.

Input

Same as for subtask 2.

Output

Same as for subtask 2.

Limits

• T = 100
• 0 ≤ C ≤ 106
• 1 ≤ N ≤ 106
• C ≤ N
• 1 ≤ |k| ≤ 106

Samples

Input:

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Output:

Case #1: 5
Case #2: 9
Case #3: -3

Comment:

We choose the superheroes with the following strengths:
Case #1: 1, 2, -7
Case #2: 1, 2
Case #3: -7, 1, 2, 3, 4

Subtask 4 (20 points)

You can choose any number of continuous superheroes.

Input

The first line contains one integer T, the number of test cases.

For each test case there is one line with an integer N (number of superheroes) and N space separated integers, the strengths of the superheroes.

Output

Print for each test case one line with “Case #i: S” where i is the index of the test case (first test case is i = 1) and S is the sum we are looking for.

Limits

• T = 100
• 1 ≤ N ≤ 104
• 1 ≤ |k| ≤ 106

Samples

Input:

3
5 4 -3 1 2 -7
5 1 2 3 4 5
5 -7 1 2 3 4

Output:

Case #1: 11
Case #2: 15
Case #3: 17

Comment:

We choose the superheroes with the following strengths:
Case #1: -3, 1, 2, -7
Case #2: We don’t choose any heroes
Case #3: -7

Subtask 5 (20 points)

Same as subtask 4 but there are more superheroes.

Input

Same as for subtask 4.

Output

Same as for subtask 4.

Limits

• T = 100
• 1 ≤ N ≤ 106
• 1 ≤ |k| ≤ 106

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

Cup Sort

Mouse Stofl is participating in a cup sorting competition, where there are N cups of different colors on the table and he has to order them according to a given pattern. He learned how to swap two adjacent cups very elegantly. But swapping fast is not enough to win, he also needs to minimize the number of swaps he performs to reach the required end configuration. He asks for your help to determine the minimum number of swaps in the different rounds of the competition.

Subtask 1: At most one move (10 points)

All cups are either red or blue. Stofl needs to put all red cups to the left of the blue cups. Is it possible with  ≤ 1 move? The colors red and blue are represented by the numbers 0 and 1 in the input.

Input

The first line contains one integer T, the number of test cases. 2⋅T lines follow, two per test case: For each test case, the first line contains an integer N, the number of cups on the table. The second line contains N integers ci, i from 1 to N, numbers for the color of each cup.

Output

For the i-th test case, display a single line “Case #i: YES”, if it is possible with  ≤ 1 move, “Case #i: NO” otherwise.

Limits

• T = 100
• 1 ≤ N ≤ 104
• 0 ≤ ci ≤ 1 for each i from 1 to N

Examples

Input:

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

Output:

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

Comment:

Case #1: swap 3rd and 4th cup
Case #2: impossible with not more than one swap
Case #3: already in the desired configuration

Subtask 2: Two colors (20 points)

Again, all cups are either red or blue and Stofl needs to put all red cups to the left of the blue cups. But this time he wants to know the minimum number of swaps he needs to perform.

Input

The input format is the same as in Subtask 1.

Output

For the i-th test case, display a single line “Case #i: S”, where S is the minimum number of swaps needed.

Limits

The limits are the same as in Subtask 1.

Example

Input:

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

Output:

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

Comment:

Case #1: swap 3rd and 4th cup
Case #2: swap 3rd and 4th cup, then 2nd and 3rd, then 1st and 2nd
Case #3: already in the desired configuration

Subtask 3: Different colors (20 points)

This time each cup has a different color, and Stofl needs to order them like the rainbow. For the numbers in the input, this means that he needs to sort them in increasing order.

Input

The first line contains one integer T, the number of test cases. 2⋅T lines follow, two per test case: For each test case, the first line contains an integer N, the number of cups on the table. The second line contains N integers ci, numbers for the color of each cup.

Output

For the i-th test case, display a single line “Case #i: S”, where S is the minimum number of swaps needed.

Limits

• T = 100
• 1 ≤ N ≤ 104
• 0 ≤ ci ≤ 106 for each i from 1 to N

Examples

Input:

2
3
10 5 6
4
1 2 4 3

Output:

Case #1: 2
Case #2: 1

Comment:

Case #1: swap 1st and 2nd cup, then 2nd and 3rd
Case #2: swap 3rd and 4th cup

Subtask 4: General case (20 points)

Everything is the same as in subtask 3, except that there can be multiple cups of the same color.

Input

The input format is the same as in Subtask 3.

Output

The output format is the same as in Subtask 3.

Limits

The limits are the same as in Subtask 3.

Examples

Input:

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

Output:

Case #1: 3
Case #2: 2

Comment:

Case #1: swap 1st and 2nd cup, then 2nd and 3rd, then 3rd and 4th
Case #2: swap 1st and 2nd cup, then 4th and 5th

Subtask 5: Many cups (30 points)

Now, Stofl needs to order a huge amount of cups. The desired order is as in subtasks 3 and 4.

Input

The first line contains one integer T, the number of test cases. 2⋅T lines follow, two per test case: For each test case, the first line contains an integer K, the number of cup groups (see below) in the input. The second line contains K pairs of integers ni and ci, i from 1 to K, describing the cup groups. A cup group consists of ni cups of the same color ci.

Output

For the i-th test case, display a single line “Case #i: S”, where S is the minimum number of swaps needed.

Limits

• T = 100
• 1 ≤ K ≤ 106
• 1 ≤ ni ≤ 106 for each i from 1 to K
• 1 ≤ Ki = 1ni ≤ 1010
• 0 ≤ ci ≤ 109 for each i from 1 to K
• 0 ≤ S < 263

Examples

Input:

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

Output:

Case #1: 3
Case #2: 4

Comment:

Case #1: all cups written out: 10 5 5 6; swap 1st and 2nd cup, then 2nd and 3rd, then 3rd and 4th
Case #2: all cups written out: 1 1 1 1 1 2 2 2 4 4 3 3

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

Strange Function

Mouse Ali found a strange C++98 source file on his old computer. He must have written it years ago. In that file, there is the following function:

long long funny(long long a, long long b) {
long long x = 1;
while (x < b) {
x *= 2;
}
long long s = x%b;
while (a >= b) {
a = (a & (x-1)) + s*(a/x);
}
return a;
}

Regrettably, Mouse Ali has no idea whatsoever what his though processes were when he wrote this source file. However, even being as humble as he is, he still is very certain that this code must be brilliant.

Clearly it would be devastating if the insights hidden in this code were lost for future generations. Maybe you are able to figure out what exactly it is that funny computes?

Mouse Ali has translated the code into idiomatic Python, hoping it would become easier to understand in the process. Unfortunately, he was not smarter than before when he finished, but maybe the translated version is of some use to you:

def funny(a, b):
x = 1
while x < b:
x = 2*x
s = x%b
while a >= b:
a = (a & (x-1)) + s*(a//x)
return a

Subtask 1: Small Values with Termination Guarantee (10 points)

Compute the result of funny(a, b) for a few small input values. It is guaranteed that funny(a, b) returns a result for all values (a, b) given in the input.

Input

The first line of the input contains a number T, the number of pairs (a, b) that you should compute funny(a, b) for. T lines, follow, each containing two integers a and b, separated by single spaces.

Output

Print one line in the format “Case #i: R” for each test case, where i is the number of the test case (the first test case is assigned the number i = 1), and R is the result of funny(a, b).

Limits

• T = 100
• 0 ≤ a ≤ 100
• 0 ≤ b ≤ 100
• funny(a, b) returns a result.

Input:

3
1 2
20 11
100 64

Output:

Case #1: 1
Case #2: 9
Case #3: 36

Subtask 2: Small Values (10 points)

Compute the result of funny(a, b) for a few small input values. If for any reason, funny(a, b) does not return a result for certain input values (a, b), print “NOTHING” instead. (Hence, in this case, R is not necessarily a number.)

As in subtask 1.

Ausgabe

As in subtask 1, except that now “NOTHING” is an allowed result.

• T = 100
• 0 ≤ a ≤ 100
• 0 ≤ b ≤ 100

Input:

3
1 3
20 12
100 65

Output:

Case #1: 1
Case #2: 8
Case #3: NOTHING

Subtask 3: Larger Values with Termination Guarantee (10 points)

Compute the result of funny(a, b) also for larger input values now. It is guaranteed that funny(a, b) returns a result for all values (a, b) given in the input.

As in subtask 1.

Output

As in subtask 1.

Limits

• T = 100
• 0 ≤ a ≤ 1018
• 0 ≤ b ≤ 1018
• funny(a, b) returns a result.

Examples

Input:

3
1124615 3132478
20239832878787237 12563819465217352
1000000000000000000 18014398509481984

Output:

Case #1: 1124615
Case #2: 7676013413569885
Case #3: 9208081978490880

Subtask 4: Theoretical Justification for Subtask 3 (25 points)

Explain why your solution for subtask 3 is correct for all nonnegative integers (a, b) (such that funny(a, b) returns a result). (Note that this means you also need to justify the correctness of your solution for numbers that exceed 1018.) Also analyze the running time of your solution. Try to keep the formulation of your arguments as clear and precise as possible. We don’t expect a strictly rigorous mathematical proof, but your arguments should be founded and build on each other.

For this theoretical subtask, you should assume that the data type long long can represent arbitrary integers, but also that the basic operations (such as <, <=, +, -, *, /, %, & and =) can be executed in constant time none the less.

For this subtask, you can only obtain points if your solution for subtask 3 is correct for all (a, b) (where a ≥ 0 and b ≥ 0 are such that funny(a, b) returns a result), and if it has a running time of at most O(loga + logb). (You can submit for subtask 3 arbitrarily often, and we only consider the last correct submission, hence it is not an issue if your first solution to subtask 3 does not satisfy those criteria initially. For this subtask, we will only correct the last submission.)

Solutions that do not run in constant time will not score all points for this subtask.

Subtask 5 (10 points)

Compute the result of funny(a, b) for large input values. If for any reason, funny(a, b) does not return a result for certain input values (a, b), print “NOTHING” instead. (Hence, in this case, R is not necessarily a number.)

As in subtask 2.

Ausgabe

As in subtask 2.

• T = 100
• 0 ≤ a ≤ 1018
• 0 ≤ b ≤ 1018

Examples

Input:

3
1124615 3132479
20239832878787237 12563819465217353
1000000000000000000 18014398509481985

Output:

Case #1: 1124615
Case #2: 7676013413569884
Case #3: NOTHING

Subtask 6 (35 points)

Explain why your solution for subtask 5 is correct for all nonnegative integers (a, b). (Note that this means you also need to justify the correctness of your solution for numbers that exceed 1018.) Also analyze the running time of your solution. Try to keep the formulation of your arguments as clear and precise as possible. We don’t expect a strictly rigorous mathematical proof, but your arguments should be founded and build on each other.

For this theoretical subtask, you should assume that the data type long long can represent arbitrary integers, but also that the basic operations (such as <, <=, +, -, *, /, %, & and =) can be executed in constant time none the less.

For this subtask, you can only obtain points if your solution for subtask 5 is correct for all (a, b) (with a ≥ 0 and b ≥ 0), and if it has a running time of at most O(loga + logb). (You can submit for subtask 5 arbitrarily often, and we only consider the last correct submission, hence it is not an issue if your first solution to subtask 5 does not satisfy those criteria initially. For this subtask, we will only correct the last submission.)

Solutions which take only constant time except for computing x score more points than solutions that do not have this property. Full score is only given to solutions whose total running time is in o(log(min(a, b))) (i.e. solutions whose running time grows strictly more slowly than logarithmic).

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

Stofl's Dissertation

After struggling for many years, Maus Stofl has finally finished his dissertation thesis. As soon as he was done, he sent the file to a copy center to have it printed and bound. Unfortunately, the copy center did a very poor job. First of all, they printed the thesis one-sided – i.e., each page on a separate sheet of paper. What’s even worse, before binding the thesis someone shuffled the pages, so they are completely out of order!

The deadline is almost here and Stofl doesn’t have the time to print the thesis again. Therefore, he has decided to fix the printout he has by tearing out some pages. His reasoning is that nobody will care if there are gaps in the thesis as long as all remaining pages are in the correct order. For example, one way of fixing a thesis that has pages in the order 1, 5, 3, 2, 4 is by tearing out the pages with numbers 2 and 5. The remaining pages will then be in the correct order: 1 < 3 < 4.

Of course, the longer the thesis Stofl submits, the better for his defense.

In the following subtasks the total number of pages in the thesis is denoted N. The page numbers are denoted a1, a2, …, aN in the order in which they appeared in the printed copy.

Subtask 1: Two page thesis (10 points)

Determine whether Stofl can submit a dissertation thesis that has at least two pages.

Input

The first line of the input contains a single integer T – the number of test cases which follow. Each test case consists of two lines. The first line of each test case contains a single positive integer N. The following line contains N distinct integers a1, a2, …, aN separated by single spaces.

Output

For the t-th test case, print a single line “Case #t: YES”, if Stofl can submit a dissertation thesis with at least two pages. Otherwise print “Case #t: NO”.

Constraints

• T = 100
• 2 ≤ N ≤ 1000
• 1 ≤ ai ≤ N
• all ai are distinct integers

Example

Input:

3
6
1 3 5 4 2 6
3
3 1 2
2
2 1

Output:

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

Comment:

Case #1: One can remove two pages and submit a dissertation thesis consisting of four pages numbered 1, 3, 4, 6.
Case #2: There is exactly one valid solution: tear out page 3 and submit the thesis that contains pages 1 and 2.
Case #3: The only two pages are in reverse order, and there is no way to fix it.

Subtask 2: Longest thesis (20 points)

Determine the maximum number of pages that Stofl can submit.

Input

The input format is the same as in Subtask 1.

Output

For the t-th test case, print a single line “Case #t: M”, where M is the maximum possible number of pages in a thesis that Stofl can submit.

Constraints

• T = 100
• 2 ≤ N ≤ 10 000
• 1 ≤ ai ≤ N
• all ai are distinct integers

Example

Input:

3
6
1 3 5 4 2 6
7
5 6 1 3 4 2 7
2
2 1

Output:

Case #1: 4
Case #2: 4
Case #3: 1

Comment:

Case #1: One can remove two pages and submit a dissertation thesis consisting of 4 pages numbered 1, 3, 4, 6.
Case #2: Here, an optimal solution is to use pages 1, 3, 4, 7. Note that if you pick page 5, you will only be able to pick at most two other pages.
Case #3: Stofl must remove at least one of these two pages.

Subtask 3: All the possibilities (20 points)

In Subtask 2 you helped Stofl compute the maximum number M of pages he can submit. He is going to do exactly that: he wants to submit a thesis that has exactly M pages. Sometimes there can be multiple ways to produce a valid M-page thesis. Compute how many theses can Stofl choose from.

Input

The input format is the same as in Subtask 1.

Output

For the t-th test case, print a single line “Case #t: K”, where K is the number of distinct versions of the dissertation thesis Stofl can submit. Note that we only count the longest possible theses. As this number can be very large, compute and output it modulo 109 + 7.

Constraints

• T = 100
• 2 ≤ N ≤ 5 000
• 1 ≤ ai ≤ N
• all ai are distinct integers

Example

Input:

3
6
1 3 2 5 4 6
7
5 6 1 3 4 2 7
2
2 1

Output:

Case #1: 4
Case #2: 1
Case #3: 2

Comment:

Case #1: There are four different ways how Stofl can keep four pages: (1,3,5,6), (1,3,4,6), (1,2,5,6) and (1,2,4,6).
Case #2: Stofl can only keep at most four pages in the thesis and there is only one such possibility: (1,3,4,7).
Case #3: Stofl can only pick one out of the two pages. His final thesis will either be (1) or (2).

Subtask 4: Reconstruction (20 points)

Stofl has already submitted his thesis. He remembers that the printout had N pages. He also remembers that he did exactly what we described above: he removed some (possibly zero) pages to produce the longest possible valid thesis. The last thing he remembers is the value K you computed in subtask 3 – the number of possibilities he had when choosing which pages to keep. (He remembers the exact value K, not the value (K mod (109 + 7)).)

Stofl would now like to reconstruct the printout he got at the very beginning. Help him: find some permutation of the pages 1, 2, …, N such that there are exactly K ways to create the longest possible valid thesis.

Input

The first line of the input contains a single integer T – the number of test cases which follow. Each test case consists of a single line with the integers N and K, separated by a single space.

Output

For the t-th test case, print a single line “Case #t: a1 a2 ... aN”, where a1, …, aN is one possible order of the N pages in the printed thesis. If there are many possible orders, you can print any of them.

Constraints

• T = 100
• 200 ≤ N ≤ 1 000
• 1 ≤ K ≤ 1018

Example

Input:

3
6 4
7 1
2 2

Output:

Case #1: 1 3 2 5 4 6
Case #2: 5 6 1 3 4 2 7
Case #3: 2 1

Comment:

These are the three same cases that were used in Subtask 2. There are also other correct outputs. For example, in Case #2 another correct output would be the sequence (1,2,3,7,4,5,6).

Subtask 5: Reconstruction with Few Pages (30 points)

A few years later Stofl thinks back the story of Subtask 4, where he tried to reconstruct the printout. He still knows K (the number of possibilities he had when choosing which pages to keep), but he can’t remember the value of N.

Given only K, he wants to find some N such that there is a permutation of the pages 1, 2, …, N that has exactly K ways to create the longest possible valid thesis. But not only that, he wants to find a small value for N.

This is a theoretical subtask.

Describe an algorithm that takes a value K and produces a value N and some permutation of 1, 2, …, N that has exactly K longest possible valid theses. Explain why it is correct and what it’s time and space complexity is.

Then analyze how N depends on K. Let’s define the function f(K) = N as the result of your algorithm. In order to score points, your function has to satisfy f(K) ≤ C⋅log(K) + D some constants C and D. Pick some values for C and D and prove that the inequality holds. (Formulated differently f satisfies f(K) = O(log(k)) and we are interested in C = max(f(K) ⁄ log(K)).) Try to make your C as small as possible.

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

Submarine

Mouse Stofl produces cheese and delivers it even to remote places. Amongst others even across the pond. But mouse Joël doesn’t like mouse Stofl’s success very much. Therefore he bought some submarines and wants to deep-six the cheese shipment. Help both of them to settle their conflict. Write a program to control the ships of mouse Stofl or the submarines of mouse Joël respectively. There will be two programs playing against each other: one of them controls the ships and the other one the submarines.

The map we play on is given as a rectangular grid. Each field is water or land. Additionally some water fields are marked as starting points or destination points. On each field there is at most one object (= ship or submarine) per player.

Each ship starts on a starting field and each submarine starts on a destination field. The goal of the player controlling the ships is that as many ships as possible reach any destination field. The goal of the other player (controlling the submarines) is to prevent the ships from reaching a destination point by sinking them.

The two players take turns and the ships start. In each turn each object can perform exactly one action:

• Stay.
• Move. The Euclidean distance between the two fields can be at most rm (i.e. (sx − dx)2 + (sy − dy)2 ≤ r2m) and the destination field has to be free. It is allowed to jump accros land tiles.
• Attack (only submarine). The Euclidean distance between the submarine and the attacked field can be at most ra (i.e. (sx − dx)2 + (sy − dy)2 ≤ r2a).

The submarines can see a ship only if the ship is at most rv away from the submarine. The ships can see a submarine only if the the submarine sunk a ship in this turn. If a submarine attacks a field on which a ship is located the ship will sink immediately. If a ship lands on a destination field it disappears immediately and other ships can land in the same turn on the same field. Sunken ships as well as ships located on a destination field can’t be moved or attacked anymore.

Protocol

The communication between program and server is handled using Stdin / Stdout. All coordinates are 0-based and the origin is in the top left corner. The y-coordinates get bigger going down.

At the start the program receives general information about the game:

One line with m s t r2m r2v r2a: the side m it should control (0 = ships, 1 = submarines), the number of ships s, the number of submarines t, the three radii for moving, viewing and attacking each squared (you get the distances squared such that you can calculate only using integers instead of decimal numbers: (sx − dx)2 + (sy − dy)2 ≤ r2m). On the next line there is w h, the width w and the height h of the map. This is followed by h lines with w characters each (# = land, . = water, s = starting field, d = destination field).

Afterwards the program prints for each of its objects (= ship or submarine) a valid starting field x y (i.e. a field s for a ship and a field d for a submarine), one object per line (i.e. s or t lines).

The protocol depends on the side the program plays for the turns. At the End of the game you will get -1 for sl or sv respectively and your program should exit correctly.

To display a debug point you can print D x y anytime. Such an output is of course not an action.

Ship

Input: A line with sl, the number of ships that got attacked (and therefore sunk) in the last turn. This is followed by sl lines each with x y u v: the coordinates of a ship x y as well as the coordinates of the submarine u v that attacked the ship.

Output: for each remaining ship (i.e. not sunken and not yet on a destination field) one line with the desired action (M for moving) and the destination coordinates for the action. Print M x y with the current coordinates if the ship should not move. with The order of the ships has to stay the same for each turn and sunken or arrived ships are skipped.

Submarine

Input: A line with sv, the number of visible ships. This is followed by sv lines each with x y: the coordinates of a ship. The order of the ships is random and changed in each turn.

Output: for each submarine one line with the desired action (A for attack, M for moving) and the destination coordinates for the action. The order of the submarines has to stay the same for each turn.

Limits

• 0 ≤ m ≤ 1
• 1 ≤ s, t ≤ 1000
• 1 ≤ rm, rv, ra ≤ 106
• 2 ≤ w, h ≤ 1000

Your program should finish a game with this limits within a “reasonable time” (i.e. within minutes and not hours). Takes a program too long to come up with an answer it loses the current game.

Sample

> 1 10 2 9 25 9
> 100 100
[...]
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss.............................................dddd.............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss.............................................dddd.............................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
[...]
< 52 49
< 49 52
> 0
< M 54 47
< M 47 52
> 0
< M 51 47
< M 47 55
[...]
> 1
> 49 37
< M 49 44
< M 52 65
[...]
> 0
< M 52 47
< M 49 70
> 1
> 50 43
< M 52 45
< M 50 68
> 2
> 51 44
> 50 43
< A 51 44
< M 51 68
> 1
> 49 42
< M 53 45
< M 50 67
[...]
> 0
< M 26 65
< M 45 73
> 0
< M 25 64
< M 47 75
> 0
< M 23 66
< M 49 75
> -1

Subtask 1: find a path (25 points)

We forget about mouse Joël for the moment and we only help mouse Stofl. Write a program that can steer all ships to the destination. The submarines won’t attack. Use :SUB1 as a submarine command to test your program.

Use the following settings in submarine.txt:

log logconfig.txt
ship_count 10
submarine_count 3
ship_command path/to/your/program.exe
submarine_command :sub1
time_limit 50
round_limit 10000
sleep_time 100
---

Subtask 2: destroy all ships (25 points)

Now we want to help mouse Joël. All ships move randomly and won’t move on a destination field. Destroy all ships. Use :SUB2 as a ship command to test your program.

Use the following settings in submarine.txt:

log logconfig.txt
ship_count 10
submarine_count 3
ship_command :sub2
submarine_command path/to/your/program.exe
time_limit 50
round_limit 10000
sleep_time 100
---

Subtask 3: creativity tournament (50 points)

You play against the other participants of the SOI. At SOI-Day the programs will compete in a tournament to determine the best one. Your program has to be able to play both sides.

You can find the played tournament here.

Maps

To test your program we added a few maps to the server. Those maps are not necessarily the ones we use for the tournament.

Tips

It is important for interactive tasks to flush the output buffer after every turn to make sure the server can see your output.

Use the following commands:

• C/C++: fflush(stdout);
• C++: cout << flush; (not necessary if you read afterwards)
• Pascal: flush(output);
• There are similar commands in other languages.

Furthermore it is important that you don’t wait for more characters than the server gives you as an input. For example spaces or line endings in C format strings are a common source for errors. For example if you read the last variable in the input with “scanf("%d ", &x);” it will wait for the next character that is not a space or a line break. You will receive such a character only after you printed your next turn. To solve this use “scanf("%d", &x);” instead (no non-printable characters after the “%d”).

Sample bots, server and visualization

During the first round we provide the following material:

• Sample bots in different programming languages.
• A server program you can use to test your program against your own or other programs.
• A visualization to display simulated games.
• Some maps to test your bot.

Quick start

To run the server you need Java (version 7 or higher). The server program is located in the file submarine.jar and the remaining files are configuration files, sample maps and sample bots.

If you double click on submarine.jar the game as specified in submarine.txt will be simulated. You can start the server using a console (Windows: cmd, Mac: terminal, Linux: Shell) to be able to pass arguments (java -jar submarine.jar arguments). You can find the available arguments (and many more information) in the file usage.md.

You can adjust most settings in the file submarine.txt like for example which program you want to execute. Most of them should be easy to understand but you can find more information in usage.md.

FAQ

Which command do I have to use?

• Python ship_command python path/to/file.py
• Java ship_command java -jar program.jar or ship_command java package.MainClass
• compiled program ship_command ./path/to/program

I have several source files

Pack everything into a .zip file.

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