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.

This contest is over.

TaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5Subtask 6
numberriddle‒/100‒/25‒/25‒/25‒/25
superpowers‒/100‒/20‒/20‒/20‒/20‒/20
cupsort‒/100‒/10‒/20‒/20‒/20‒/30
funny‒/100‒/10‒/10‒/10‒/25‒/10‒/35
dissertation‒/100‒/10‒/20‒/20‒/20‒/30
submarine‒/100‒/25‒/25‒/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,n1n_{0}, n_{1} and a target value RR. Amir now tests if he can reach the value RR by adding the two numbers or subtracting the second number from the first number.

Input

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

Output

For the ii-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=100T = 100
  • N=2N = 2
  • 0R=150 \le R = 15
  • 0ni100 \le n_i \le 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=52+3=5 and 83=58-3=5.
For the third case, 2+8=102+8=10 and 28=62-8=-6 both are unequal to 66.

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: 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 RR with at most one subtraction?

Input

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

Output

The output format is the same as in subtask 1. For the ii-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=100T = 100
  • 2N1002\le N \le 100
  • 0R=100000 \le R = 10000
  • 0ni1000 \le n_i \le 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=52+3=5
Case #2: 38+10=53-8+10=5
Case #3: 8+3+10=5-8+3+10=5 is invalid, the - can’t be used as a sign.

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: 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 RR with at most two subtraction?

Input

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

Output

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

Limits

  • T=100T = 100
  • 2N1002\le N \le 100
  • 0R=100000 \le R = 10000
  • 0ni1000 \le n_i \le 100

Examples

Input:

2
3 5
16 8 3
3 8
16 10 2

Output:

Case #1: YES
Case #2: YES

Comment:

Case #1: 1683=516-8-3=5
Case #2: 1610+2=816-10+2=8 fewer subtractions are still a valid possibility.

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: 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 TT, the number of test cases. Each test case consists of two lines: The first line contains two integers: NN, the number of numbers Amir picks and RR, the number he tries to reach. The second line contains NN integers: nin_i, the numbers Amir adds or subtracts from each other.

Output

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

Limits

  • T=100T = 100
  • 2N1002\le N \le 100
  • 0R100000 \le R \le 10\,000
  • 0ni1000 \le n_i \le 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: 1683=516-8-3=5
Case #2: 1610+2=816-10+2=8
Case #3: 4+2+2=84+2+2=8
Case #4: 2+4+6=8-2+4+6=8 but the - can’t be used as a sign.

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

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 kk (an integer). If he is bad it holds k<0k < 0, otherwise k>1k > 1 (i.e. he is good). When the device is used on a superhero, the new strength is k-k. To determine which side is stronger Stofl sums up all strengths. Help him maximize this sum SS.

Subtask 1 (20 points)

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

Input

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

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

Output

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

Limits

  • T=100T = 100
  • 0C1040 \le C \le 10^{4}
  • 1N1041 \le N \le 10^{4}
  • 1k1061 \le |k| \le 10^{6}

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

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)

You have to choose exactly CC 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=100T = 100
  • 0C1040 \le C \le 10^{4}
  • 1N1041 \le N \le 10^{4}
  • CNC \le N
  • 1k1061 \le |k| \le 10^{6}

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

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)

You have to choose CC 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=100T = 100
  • 0C1060 \le C \le 10^{6}
  • 1N1061 \le N \le 10^{6}
  • CNC \le N
  • 1k1061 \le |k| \le 10^{6}

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

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)

You can choose any number of continuous superheroes.

Input

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

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

Output

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

Limits

  • T=100T = 100
  • 1N1041 \le N \le 10^{4}
  • 1k1061 \le |k| \le 10^{6}

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

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 (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=100T = 100
  • 1N1061 \le N \le 10^{6}
  • 1k1061 \le |k| \le 10^{6}

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

Cup Sort

Mouse Stofl is participating in a cup sorting competition, where there are NN 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\le 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 TT, the number of test cases. 2T2\cdot T lines follow, two per test case: For each test case, the first line contains an integer NN, the number of cups on the table. The second line contains NN integers cic_i, ii from 11 to NN, numbers for the color of each cup.

Output

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

Limits

  • T=100T = 100
  • 1N1041 \le N \le 10^{4}
  • 0ci10 \le c_i \le 1 for each ii from 11 to NN

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

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: 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 ii-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

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: 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 TT, the number of test cases. 2T2\cdot T lines follow, two per test case: For each test case, the first line contains an integer NN, the number of cups on the table. The second line contains NN integers cic_i, numbers for the color of each cup.

Output

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

Limits

  • T=100T = 100
  • 1N1041 \le N \le 10^{4}
  • 0ci1060 \le c_i \le 10^{6} for each ii from 11 to NN

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

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

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: 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 TT, the number of test cases. 2T2\cdot T lines follow, two per test case: For each test case, the first line contains an integer KK, the number of cup groups (see below) in the input. The second line contains KK pairs of integers nin_i and cic_i, ii from 11 to KK, describing the cup groups. A cup group consists of nin_i cups of the same color cic_i.

Output

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

Limits

  • T=100T = 100
  • 1K1061 \le K \le 10^{6}
  • 1ni1061 \le n_i \le 10^{6} for each ii from 11 to KK
  • 1i=1Kni10101 \le \sum_{i=1}^K n_i \le 10^{10}
  • 0ci1090 \le c_i \le 10^{9} for each ii from 11 to KK
  • 0S<2630 \le S < 2^{63}

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

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

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)(a,b) given in the input.

Input

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

Output

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

Limits

  • T=100T = 100
  • 0a1000 \le a \le 100
  • 0b1000 \le b \le 100
  • funny(a, b) returns a result.

Examples

Input:

3
1 2
20 11
100 64

Output:

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

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: 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)(a,b), print “NOTHING” instead. (Hence, in this case, R is not necessarily a number.)

Input

As in subtask 1.

Ausgabe

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

Limits

  • T=100T = 100
  • 0a1000 \le a \le 100
  • 0b1000 \le b \le 100

Examples

Input:

3
1 3
20 12
100 65

Output:

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

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: 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)(a,b) given in the input.

Input

As in subtask 1.

Output

As in subtask 1.

Limits

  • T=100T = 100
  • 0a10180 \le a \le 10^{18}
  • 0b10180 \le b \le 10^{18}
  • 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

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: Theoretical Justification for Subtask 3 (25 points)

Explain why your solution for subtask 3 is correct for all nonnegative integers (a,b)(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 101810^{18}.) 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)(a,b) (where a0a\ge 0 and b0b\ge 0 are such that funny(a, b) returns a result), and if it has a running time of at most O(loga+logb)\mathcal O(\log a + \log b). (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.

The contest is over, you can no longer submit.

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)(a,b), print “NOTHING” instead. (Hence, in this case, R is not necessarily a number.)

Input

As in subtask 2.

Ausgabe

As in subtask 2.

Limits

  • T=100T = 100
  • 0a10180 \le a \le 10^{18}
  • 0b10180 \le b \le 10^{18}

Examples

Input:

3
1124615 3132479
20239832878787237 12563819465217353
1000000000000000000 18014398509481985

Output:

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

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 6 (35 points)

Explain why your solution for subtask 5 is correct for all nonnegative integers (a,b)(a,b). (Note that this means you also need to justify the correctness of your solution for numbers that exceed 101810^{18}.) 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)(a,b) (with a0a\ge 0 and b0b\ge 0), and if it has a running time of at most O(loga+logb)\mathcal O(\log a + \log b). (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 xx 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)))o(\log(\min(a,b))) (i.e. solutions whose running time grows strictly more slowly than logarithmic).

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

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,41,5,3,2,4 is by tearing out the pages with numbers 22 and 55. The remaining pages will then be in the correct order: 1<3<41<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 NN. The page numbers are denoted a1,a2,,aNa_{1}, a_{2}, {\dots}, a_N 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 TT – 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 NN. The following line contains NN distinct integers a1,a2,,aNa_{1}, a_{2}, {\dots}, a_N separated by single spaces.

Output

For the tt-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=100T = 100
  • 2N10002 \le N \le 1000
  • 1aiN1 \le a_i \le N
  • all aia_i 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.

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: 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 tt-th test case, print a single line “Case #t: M”, where MM is the maximum possible number of pages in a thesis that Stofl can submit.

Constraints

  • T=100T = 100
  • 2N100002 \le N \le 10\,000
  • 1aiN1 \le a_i \le N
  • all aia_i 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.

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: All the possibilities (20 points)

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

Input

The input format is the same as in Subtask 1.

Output

For the tt-th test case, print a single line “Case #t: K”, where KK 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+710^{9}+7.

Constraints

  • T=100T = 100
  • 2N50002 \le N \le 5\,000
  • 1aiN1 \le a_i \le N
  • all aia_i 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).

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: Reconstruction (20 points)

Stofl has already submitted his thesis. He remembers that the printout had NN 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 KK you computed in subtask 3 – the number of possibilities he had when choosing which pages to keep. (He remembers the exact value KK, not the value (K\textvisiblespacemod\textvisiblespace(109+7))(K \textvisiblespace\mathrm{mod}\textvisiblespace (10^{9}+ 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,,N1,2,{\dots},N such that there are exactly KK ways to create the longest possible valid thesis.

Input

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

Output

For the tt-th test case, print a single line “Case #t: a1 a2 ... aN”, where a1,,aNa_{1},{\dots},a_N is one possible order of the NN pages in the printed thesis. If there are many possible orders, you can print any of them.

Constraints

  • T=100T = 100
  • 200N1000200 \le N \le 1\,000
  • 1K10181 \le K \le 10^{18}

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

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: 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 KK (the number of possibilities he had when choosing which pages to keep), but he can’t remember the value of NN.

Given only KK, he wants to find some NN such that there is a permutation of the pages 1,2,,N1,2,{\dots},N that has exactly KK ways to create the longest possible valid thesis. But not only that, he wants to find a small value for NN.

This is a theoretical subtask.

Describe an algorithm that takes a value KK and produces a value NN and some permutation of 1,2,,N1,2,{\dots},N that has exactly KK longest possible valid theses. Explain why it is correct and what it’s time and space complexity is.

Then analyze how NN depends on KK. Let’s define the function f(K)=Nf(K)=N as the result of your algorithm. In order to score points, your function has to satisfy f(K)Clog(K)+Df(K) \le C\cdot\log(K)+D some constants CC and DD. Pick some values for CC and DD and prove that the inequality holds. (Formulated differently ff satisfies f(K)=O(log(k))f(K)=\mathcal O(log(k)) and we are interested in C=max(f(K)/log(K))C=\max (f(K)/log(K)).) Try to make your CC as small as possible.

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

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.

Creativity Task

Task

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 rmr_m (i.e. (sxdx)2+(sydy)2rm2(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_m^{2}) 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 rar_a (i.e. (sxdx)2+(sydy)2ra2(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_a^{2}).

The submarines can see a ship only if the ship is at most rvr_v 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 mm ss tt rm2r_m^{2} rv2r_v^{2} ra2r_a^{2}: the side mm it should control (0 = ships, 1 = submarines), the number of ships ss, the number of submarines tt, 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: (sxdx)2+(sydy)2rm2(s_x - d_x)^{2}+ (s_y - d_y)^{2}\le r_m^{2}). On the next line there is ww hh, the width ww and the height hh of the map. This is followed by hh lines with ww 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 xx yy (i.e. a field s for a ship and a field d for a submarine), one object per line (i.e. ss or tt lines).

The protocol depends on the side the program plays for the turns. At the End of the game you will get -1 for sls_l or svs_v 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 sls_l, the number of ships that got attacked (and therefore sunk) in the last turn. This is followed by sls_l lines each with xx yy uu vv: the coordinates of a ship xx yy as well as the coordinates of the submarine uu vv 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 svs_v, the number of visible ships. This is followed by svs_v lines each with xx yy: 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

  • 0m10 \le m \le 1
  • 1s,t10001 \le s, t \le 1000
  • 1rm,rv,ra1061 \le r_m, r_v, r_a \le 10^{6}
  • 2w,h10002 \le w, h \le 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:

map path/to/downloaded/map.txt
log logconfig.txt
ship_count 10
submarine_count 3
ship_command path/to/your/program.exe
submarine_command :sub1
radius_move 9
radius_view 25
radius_attack 9
time_limit 50
round_limit 10000
sleep_time 100
---

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 15 minutes and 0 seconds left.

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:

map path/to/downloaded/map.txt
log logconfig.txt
ship_count 10
submarine_count 3
ship_command :sub2
submarine_command path/to/your/program.exe
radius_move 9
radius_view 25
radius_attack 9
time_limit 50
round_limit 10000
sleep_time 100
---

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 15 minutes and 0 seconds left.

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.

The contest is over, you can no longer submit.

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.

You can download them here.

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

Ranking

RankUsernameTotal (600)numberr… (100)
numberriddle
superpo… (100)
superpowers
cupsort (100)funny (100)dissert… (100)
dissertation
submarine (100)
loading ...