# First Round SOI 2019

## Overview

This contest is over.

mergeball‒/100‒/20‒/20‒/20‒/20‒/20
ceremony‒/100‒/10‒/20‒/20‒/10‒/40
touristtrap‒/100‒/20‒/20‒/30‒/30
pipeline‒/100‒/15‒/15‒/10‒/60
storytelling‒/100‒/20‒/20‒/15‒/15‒/30
tankgolf‒/100‒/100

## Merge Ball

Mouse Stofl has a new favorite game: mergeball. In this game there are balls of different sizes on a horizontal rod. As soon as two balls of the same size touch they merge and form a new ball with double the size. If there are multiple possibilities Stofl can decide which balls he wants to merge first as long as there are no other balls in between.

Mous Stofl realizes after some experimentation that it might not always be possible to reach all sizes depending on the starting configuration. As there are very many starting configurations Stofl is not able to test them all by himself. You have to write a program for Mouse Stofl to help him in his quest.

### Subtask 1: Final configuration with two balls (20 Points)

Very often there are two balls of the same size on the rod. Your first program should help Stofl figure out how large the balls get after he merged them.

#### Input

The first line contains the number of configurations $T$. $T$ configurations follow, each consisting of two lines. The first line contains the number of balls $N$, the second line consists of $N$ numbers $p_i$ describing the size of the $i$-th ball.

#### Output

For the $t$-th configuration output “Case #t: k”, where $k$ is the size of the resulting ball.

#### Limits

• $T=100$
• $N = 2$
• $1 \le p_i \le 10^{6}$
• $p_{0}=p_{1}$

#### Examples

Input:

2
2
5 5
2
7 7

Output:

Case #0: 10
Case #1: 14

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: All to one (20 Points)

For the next games Mouse Stofl only wants to know whether he is able to merge all the balls. First he only considers games where all the balls have the same initial size.

#### Input

The input format is the same as in subtask 1.

#### Output

Output the $t$-th configuration as “Case #t: s”, where $s$ is either “Single” if all balls merge to one ball, or “Multiple” if there are multiple balls left.

#### Limits

• $T=100$
• $1 \le N \le 1000$
• $1 \le p_i \le 10^{6}$
• $p_{0}=p_{1}={\dots}=p_{N-1}$, i.e. all balls have the same size.

#### Examples

Input:

2
5
3 3 3 3 3
4
7 7 7 7

Output:

Case #0: Multiple
Case #1: Single

Comment:

Case #0: No matter what Stofl does there will always be at least 2 balls left, e.g. 12 3. Case #1: Stofl starts with the middle two 7, reaching configuration 7 14 7. He can not merge more balls. However, if he is a bit more attentive he can merge all balls to one of size 28.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: All to one – Part 2 (20 Points)

This subtask is the same as subtask 2 but at the start not all of the balls have to be the same size.

#### Input

The input format is the same as in subtask 1.

#### Output

The output format is the same as in subtask 2.

#### Limits

• $T=100$
• $1 \le N \le 1000$
• $1 \le p_i$
• The sum of all $p_i$ is at most $10^{9}$.

#### Examples

Input:

2
5
3 3 6 6 6
4
7 7 11 11

Output:

Case #0: Single
Case #1: Multiple

Comment:

Case #0: After merging the 3 large balls Stofl can merge the four balls of size 6. Case #1: 22 and 14 can not be merged, therefore two balls remain.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 4: To infinity (20 Punkte)

Stofl already knows the game quite well and wants to build one for himself. At the start he only has balls of one size.

Stofl wants to know in advance which sizes can be reached in his game. To prevent the players from being scared by large balls it is not allowed for balls to be larger than $C$.

Write a program which calculates all possible sizes $\le C$ of balls which can be reached. Print them in sorted order.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow, each consisting of two lines. The first line contains the number of different sizes of balls $N$ and the maximal size $C$ which balls may reach. The second line contains $N$ numbers $p_i$, the sizes of the balls which Mouse Stofl owns.

#### Output

For the $t$-th test case print “Case #t: K $x_{0}$ $x_{1}$ ${\dots}$ $x_{K-1}$” where $K$ is the number of sizes which can be formed, followed by this $K$ numbers in increasing order.

#### Limits

• $T=100$
• $N = 1$
• $1 \le C \le 10^{9}$
• $1 \le p_i \le 10^{9}$

#### Examples

Input:

2
1 20
5
1 50
7

Output:

Case #0: 3 5 10 20
Case #1: 3 7 14 28

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 5: To infinity and beyond! (20 Points)

Mouse Stofl now has more sizes of balls and can therefore build even more complex games.

#### Input

The input format is the same as in subtask 4.

#### Output

The output format is the same as in subtask 4.

#### Limits

• $T=100$
• $1 \le N \le 100$
• $1 \le C \le 10^{18}$
• $1 \le p_i \le 10^{18}$

#### Examples

Input:

2
2 30
5 10
4 50
3 6 7 123

Output:

Case #0: 3 5 10 20
Case #1: 8 3 6 7 12 14 24 28 48

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

## Ceremony

This year, the Mouse Olympiad in Informatics takes place, just as its human counterpart, in Baku, Azerbaijan. The organizers have asked Mouse Stofl to help them prepare the opening ceremony of the competition.

In particular, he’s been designated to organize the big fireworks display that is meant to impress the delegations from all around the world. Stofl is an expert in fireworks, so he’s sure to put on a great show, but there is one little problem: he has to make sure everyone can find a good spot to watch the fireworks.

His idea is the following: there are a lot of new buildings and skyscrapers in Baku, and he would like to launch the fireworks from the top of one of these buildings, and have the participants watch the show from another rooftop. Of course, since there are so many delegations, not everybody is going to fit on a single rooftop, and Stofl wants to find as many suitable rooftops as possible to host as many participants as possible in ideal conditions.

Although there are a lot of buildings to choose from, they aren’t all ideal: the problem is that all these buildings have different heights, and Stofl is not sure whether the fireworks will be visible from every rooftop in the city, since some other buildings may block the view. As a rule of thumb, he’s decided to use the following criterion to determine if the view is ideal: a rooftop offers a good view of the fireworks display if and only if all the buildings standing between the rooftop and the building from which the fireworks are launched are strictly smaller than the rooftop’s building. No participant is allowed to watch from the rooftop where the organizers fire the rockets, for obvious security and liability reasons.

For the sake of simplicity, we will think of the skyscrapers as all standing in a row. There are $N$ skyscrapers. The height of the $i$-th skyscraper is $h_i$. You can ideally see the fireworks launched from the $i$-th skyscraper from the $j$-th skyscraper if and only if $i$ and $j$ are different and there is no $k$ for which both $\min(i,j) and $h_k \ge h_j$ are true.

### Subtask 1: Launch the fireworks from the westmost building (10 points)

Mouse Stofl would like to know if his simple idea works. He wants to launch the fireworks from the westmost building and install participants on other rooftops rented by the organization from which they can get an ideal view. However, he’s not sure that there are enough buildings offering such a view. Help him figure out how many exactly.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow, each consisting of two lines. The first line contains the number of skyscrapers $N$ and $i$, the index of the skyscraper from which the fireworks are launched (always 0 in this subtask). The second line contains $N$ numbers $h_j$, each representing the height of the $j$-th skyscraper.

#### Output

For the $i$-th test case, print out a single line “Case #i: M”, where $M$ denotes the total number of skyscrapers offering an ideal view of the fireworks display.

#### Limits

• The number of test cases: $T = 100$
• The number of skyscrapers: $1 \le N \le 100$
• The 0-based index of the building where the fireworks are launched: $i = 0$
• The height of the $j$-th skyscraper for any $j$: $1 \le h_j \le 10^{3}$

#### Sample

Input:

1
6 0
3 2 4 4 6 5

Output:

Case #0: 3

Comment:

Buildings #1, #2 and #4 offer an ideal view. Note that the height of building #0 doesn’t matter. Building #3 doesn’t have an ideal view because building #2 has the same height nor does #5 have, because building #4 is taller.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: More available buildings (20 points)

Unfortunately, using your results from Subtask 1, Mouse Stofl determined that there are not enough skyscrapers with an ideal view of the fireworks. Luckily, he contacted owners of other buildings and a lot of them agreed to lend their rooftops for the night. Can you help Stofl again, this time taking into account the many new buildings?

#### Limits

• The number of test cases: $T = 100$
• The number of skyscrapers: $1 \le N \le 1\,000\,000$
• The 0-based index of the building where the fireworks are launched: $i = 0$
• The height of the $j$-th skyscraper for any $j$: $1 \le h_j \le 10^{9}$

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: Launching from another building (20 points)

Unfortunately, Mouse Stofl got into trouble with the authorities: they won’t let him launch the fireworks from the skyscraper he originally intended to use. However, they assigned him a new building from which he’s allowed to launch the fireworks. Can you help him calculate how many skyscrapers offer an ideal view now?

#### Input

Same as in Subtask 1 and 2, but $i$ is not always $0$ anymore.

#### Output

Same as in Subtask 1 and 2.

#### Limits

• The number of test cases: $T = 100$
• The number of skyscrapers: $1 \le N \le 1\,000\,000$
• The 0-based index of the building where the fireworks are launched: $0 \le i < N$
• The height of the $j$-th skyscraper for any $j$: $1 \le h_j \le 10^{9}$

#### Sample

Input:

1
9 4
5 3 2 4 3 2 3 3 1

Output:

Case #0: 4

Comment:

Buildings #0, #3, #5 and #6 offer an ideal view.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 4: Find the building with optimal visibility (10 points)

Mouse Stofl has resolved all the problems he had with the administration and they will now let them use any building to launch his fireworks. That gives Stofl a good opportunity to save a bit on his expenses, by choosing the most visible building. He’s also thinking of using only the originally planned buildings, to save a little more. Help him find out how many buildings will be able to see the fireworks display if he chooses optimally from where to launch them.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow, each consisting of two lines. The first line contains the number of skyscrapers $N$. The second line contains $N$ numbers $h_j$, each representing the height of the $j$-th skyscraper.

#### Output

For the $i$-th test case, print out a single line “Case #i: M”, where $M$ denotes the maximal total number of skyscrapers offering an ideal view of the fireworks if these are launched from the optimal skyscraper.

#### Limits

• The number of test cases: $T = 100$
• The number of skyscrapers: $1 \le N \le 100$
• The height of the $j$-th skyscraper for any $j$: $1 \le h_j \le 10^{9}$

#### Sample

Input:

1
9
5 3 2 4 3 2 3 3 1

Output:

Case #0: 5

Comment:

The optimal building where to launch the fireworks is #6. If Stofl chooses this one, buildings #0, #3, #4, #5 and #7 offer an ideal view.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 5: Find the building with optimal visibility with many buildings (40 points)

Since it turned out the configuration with fewer buildings didn’t offer enough places with ideal visibility for every contestant, Stofl decided to use every building he can, without any regard to his expenses. Can you help him compute how many he may use in the best case, just as in the last subtask, but with many more skyscrapers?

#### Limits

• The number of test cases: $T = 100$
• The number of skyscrapers: $1 \le N \le 1\,000\,000$
• The height of the $j$-th skyscraper for any $j$: $1 \le h_j \le 10^{9}$

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

## Tourist Trap

Mouse Stofl is currently visiting Baku, the capital city of Azerbaijan. Baku has an old part, which is very beautiful, but also difficult to navigate, because it consists of many narrow streets almost forming a maze. That’s why Stofl chose to go on a guided tour through the city. As the tour progressed however, Stofl got the impression that they will have to go through a store and buy something to continue their trip. Stofl is very frugal and doesn’t want to spend any money if possible, therefore he would prefer to stop the sightseeing early instead.

The question that arises is whether it is possible to get out of the old city without going through a building (which are all stores). Luckily Mouse Stofl has a phone with GPS which shows exactly where he is and has also downloaded a map of the old city of Baku. Can he escape the tourist trap?

### Subtask 1: ASCII map (20 points)

#### Input

The first line of the input contains a single integer $T$ ($1 \le T \le 100$) – the number of test cases which follow.

Each test case starts with a line containing four integers $w$, $h$, $x$, and $y$ ($w,h \ge 1$, $0 \le x < w$, $0 \le y < h$), the dimensions of the old city of Baku and Stofl’s position.

$h$ lines follow, each containing exactly $w$ characters. The $i$-th character of the $j$-th line describes whether there is a building or not at position $x=i$, $y=j$: # for a building and _ for no building.

#### Output

For each test case you should output a single line containing the string “Case #t: p” where $t$ is the number of the test cases (0-based in increasing order) and $p$ is either “POSSIBLE” or “IMPOSSIBLE”: whether or not it is possible to reach any of the border squares without going through a building, i.e. somewhere with $x = 0$ or $y = 0$ or $x = w-1$ or $y = h-1$.

#### Limits

$w, h \le 100$

#### Example

Input:

2
10 8 2 4
########__
#____###__
#_#_____##
#_#__##_##
#__####__#
########_#
##_______#
##_#######
8 7 1 1
######_#
#___##_#
#___##__
#___##_#
####___#
######_#
######_#

Output:

Case #0: POSSIBLE
Case #1: IMPOSSIBLE

Comment:

Case #0: Stofl starts at the end of the left-hand L-shaped road and can walk to the southern exit.

Case #1: Stofl starts at the piazza in the north west, but it is not connected to the eastern road.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: Vector map (20 points)

The creator of the map Stofl is using has updated their map format, because it was getting very large for bigger maps. Now, the roads are stored as a series of rectangles.

#### Input

The map format is now different. Instead of the $h$ lines with $w$ characters each, the following format is now used to describe the old city:

A line containing $r$, the number of roads, followed by $r$ lines, each describing one road. The $i$-th of these lines contains 4 integers $x_i$, $y_i$, $w_i$, and $h_i$ ($0 \le x_i, y_i$, $1 \le w_i, h_i$, $x_i + w_i \le w$, $y_i + h_i \le h$). The position at $x$, $y$ is covered by road #i if $x_i \le x \le x_i + w_i - 1$ and $y_i \le y \le y_i + h_i - 1$. The roads can (but don’t have to) overlap, for example at an intersection.

#### Limits

$w, h \le 100$, $r \le 100$

#### Sample

Input:

2
10 8 2 4
10
1 1 1 4
2 4 1 1
2 1 3 1
3 2 2 2
3 2 5 1
7 2 1 3
8 4 1 3
2 6 7 1
2 6 1 2
8 0 2 2
8 7 1 1
4
1 1 3 3
4 4 2 1
6 0 1 7
6 2 2 1

Output:

Case #0: POSSIBLE
Case #1: IMPOSSIBLE

Comment:

These are the same inputs as in the sample for subtask 1, just in the new format. 8 7 1 1 is the first line of the second testcase.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: Bigger map (30 points)

This is the same as subtask 2, but with bigger inputs.

#### Output

Same as in subtask 1 and 2.

#### Limits

$w, h \le 10^{9}$, $r \le 10^{3}$

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 4: Even bigger map (30 points)

#### Input

Same as in subtask 2 and 3.

#### Output

Within reasonable limits, it is in this contest format possible that optimized brute-force solutions may pass. Therefore, we will manually check all submissions and may retroactively give an accepted submission 0 points.

We expect a solution that runs in $O(r \log r)$ (possibly with some additional log factors).

Update (2018-09-16): Previously it was written $O(n \log n)$. We expect that the solution runs quasilinear in $r$, the number of streets. It’s not sufficient to be quasilinear in the size of the map or the number of intersections (which could be up to $Θ(r^{2})$).

To check that your solution fulfills the requirements, you can check it locally on pre-generated testdata: touristtrap-sub4-large.in and touristtrap-sub4-large.out. Your solution should take between 2min and 10 minutes to compute the correct result.

#### Limits

$w, h \le 10^{9}$, $r \le 10^{5}$

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

## Pipeline

Azerbaijan is the birthplace of the oil industry. To distribute their oil over the world, the Baku—Tbilisi—Ceyhan (BTC) pipeline has recently been opened. Now you are in charge of an even more ambitious project: the Erzurum—Tulcea—Herisau (ETH) pipeline that connects Baku via the BTC and ETH pipeline directly to Switzerland.

The main challenge for such long pipelines is to keep the oil flowing. In order to push the oil forward, you plan to build $P$ pump stations. For that you have located $N$ possible building spots for those pump stations. The speed of the oil crucially depends on its distance to the nearest pump station. The longest segment without any pump station will be the bottleneck of the whole pipeline. In oil speek, the length of the longest segment without pumps is called the “longest thrust circumvent” (LTC). Your goal is to minimize the LTC.

### Subtask 1: Fixed LTC (15 points)

You know $N$ and $L$ (the maximal allowed LTC), as well as the possible building locations ($x_{0},x_{1},\dots,x_{N-1}$, where $x_i$ is the $i$-th possible location for a pump station). Compute the minimal number of pump stations $P$ needed for an LTC of at most $L$.

The pipeline starts at $x_{0}$ and ends at $x_{N-1}$. For technical reasons, locations $x_{0}$ and $x_{N-1}$ must always contain a pump station.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow, each with $N$ and $L$ on the first and $x_{0},x_{1},\dots,x_{N-1}$ on the second line. The locations are given in increasing order.

#### Output

For the $i$-th test case print a line “Case #i:” followed by either:

• a number $P\le 9000$ followed by $P$ integers $p_{0}. $P$ is the minimal number of pump stations needed and $p_i$ is the location of the $i$-th pump station. If there are multiple solutions using $P$ pump stations, print any of them.
• just a number $P>9000$ if more than 9000 pump stations are needed.
• Impossible” if it is impossible to build the pump stations in such a way that the LTC is at most $L$.

#### Limits

• $T=100$
• $1 \le N \le 100\,000$
• $1 \le L \le 10^{9}$
• $0\le x_{0}

#### Example

Input:

4
6 4
2 4 6 7 11 12
3 3
1000 1003 1007
1 3
5
5 2
0 1 2 3 4

Output:

Case #0: 5 2 4 7 11 12
Case #1: Impossible
Case #2: 1 5
Case #3: 3 0 2 4

Comment:

In Case #0, another possibility would have been 5 2 6 7 11 12.

Big input:

Input:

2
9000 1
0 1 2 3 ... 8999
9001 1
0 1 2 3 ... 8999 9000

Output:

Case #0: 9000 0 1 2 ... 8999
Case #1: 9001

Comment:

The dots are just for illustrative purposes. You can download the input file here.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 2: Fixed Pumps Count (15 points)

This time you know $N$ and $P$, the number of pumps as well as the possible building locations. Compute the minimal LTC that you can achieve.

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow, each with $N$ and $P$ on the first and $x_{0},x_{1},\dots,x_{N-1}$ on the second line.

#### Output

For the $i$-th test case print two lines. The first line should be “Case #i: L”, where $L$ is the minimal LTC you can achieve by optimally placing $P$ pump stations.

On the second line, if $P\le 9000$, write exactly $P$ numbers $p_{0},p_{1},\dots,p_{P-1}$, the locations of the pump stations. If $P\ge 9001$, write “Over 9000” instead of the locations of pump stations. Here, $P$ denotes the value from the input.

#### Limits

• $T=100$
• $1 \le N \le 100\,000$
• $\min(2, N) \le P \le N$
• $0\le x_{0}

#### Example

Input:

4
6 5
2 4 6 7 11 12
3 2
1000 1003 1007
1 1
5
5 4
0 1 2 3 4

Output:

Case #0: 4
2 6 7 11 12
Case #1: 7
1000 1007
Case #2: 0
5
Case #3: 2
0 1 2 4

Comment:

Note that in Case #3, the pump at location 1 (or alternatively 3) is basically a waste because it doesn’t influence the LTC. But you need to build exactly $P$ pump stations.

Big input:

Input:

2
9000 9000
0 1 2 3 ... 8999
9001 9001
0 1 2 3 ... 8999 9000

Output:

Case #0: 1
0 1 2 ... 8999
Case #1: 1
Over 9000

Comment:

The dots are just for illustrative purposes. You can download the input file here.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 3: Walking down the BTC (10 points)

The new planned pipeline is so long that there is no way you are able to remember all $N$ building locations. Even worse, neither $P$ nor the LTC are fixed. You only know an upper bound $M$ on the LTC, meaning that you never want to have an LTC higher than $M$.

To deal with those numbers you write a program. You tell the program $M$, the maximal number LTC you will allow. Then, the program reads all $N$ building locations in increasing order. In the end, it will give you $M$ numbers: the $i$-th number (0-based) tells you the minimal number of pumps you need for guaranteeing an LTC of at most $i+1$.

Before taking on the ETH pipeline, you walk down the smaller BTC. In the BTC, the input is small enough so that your program can store all numbers. However, the last subtask will be exactly the same except that it is about the ETH and there you can no longer do that. To save you some work we recommend you to read the last subtask before solving this one (though you can solve this subtask by any means necessary).

#### Input

The first line contains the number of test cases $T$. $T$ test cases follow, each with $N$ and $M$ on the first and $x_{0},x_{1},\dots,x_{N-1}$ on the second line.

#### Output

For the $i$-th test case print a single line “Case #i:”, followed by $M$ numbers “$p_{0},p_{1},\dots,p_{M-1}$”, where $p_i$ is the minimal number of pump stations you need for achieving an LTC of at most $i+1$. If it is not possible, print $-1$ instead.

#### Limits

• $T=100$
• $1 \le N \le 100\,000$
• $1 \le M \le 250$
• $0\le x_{0}

#### Example

Input:

4
6 10
2 4 6 7 11 12
3 7
1000 1003 1007
1 1
5
5 4
0 1 2 3 4

Output:

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

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

### Subtask 4 (Theoretical): Walking down the ETH (60 points)

Now it’s time for the real thing: the ETH. As we can not verify the memory consumption of your program, this is a theoretical subtask. Describe an algorithm that can solve subtask 3 and analyze its running time and memory usage.

You should optimize for memory usage first and running time second. See grading for more details.

Hand in a document (preferably PDF) that describes

• why your algorithm is correct, and
• how much memory and time it needs.

#### Limits

• $N$ and $M$ are variables, i.e., you should use them in your analysis. You can assume that $N$ is much larger than $M$.
• The $x_i$ are sorted ($0\le x_{0}) but can get arbitrarily large. You can assume that basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) take a unit time step to perform and that storing one integer uses a single memory unit.

The memory consumption of your data structure should only depend on $M$, not $N$. Aim for $O(M)$ memory, but it’s fine if you need slightly more than that.

If everything else is correct, we will give you points based on the table below.

Memory usage Running time Max score
$O(M)$ $O(N\cdot M)$ 20
$O(M^{1.5})$ $O(N\cdot M^{0.75})$ 40
$O(M)$ $O(N\cdot M^{0.75})$ 50
$O(M\log M)$ $O(N\cdot M^{0.5} \log M)$ 50
$O(M)$ $O(N\cdot M^{0.5} (\log M)^{2})$ 60

The contest is over, you can no longer submit.

## Storytelling

Mouse Stofl went to explore Azerbaijan so that he can tell you what to see and do there when you go to compete in IOI 2019. Today he visited the famous fire mountain Yanar Dag – a place where rocks and water spontaneously ignite into flames. In the evening Stofl has arranged an overnight stay at Mouse Yusif’s home. The hospitality of Azerbaijani mice astonished Stofl as Yusif’s whole family has gathered at Yusif’s home to honor Stofl.

For the dinner all $N$ mice (including Stofl) sat around a round table. In Azerbaijan it is customary to tell stories before eating dinner. This storytelling has to follow some strict rules (especially in the presence of a dear guest):

• Each mouse has to tell exactly one story to its neighbors.
• A story has to be told without interruptions.
• While a mouse is telling a story, both of its neighbors have to listen – i.e., they cannot tell their own stories at the same time.
• The mice are good listeners: a mouse can listen to both its neighbors at the same time.
• The food is not served until all stories are told.

The mice are already quite hungry and they want food as soon as possible.

You are given positive integers $t_{0},\dots,t_{N-1}$ – the lengths (in seconds) of the stories our $N$ mice want to tell tonight. The lengths are given in the order in which the mice sit at the table. Find the optimal schedule for the storytelling.

### Input

The first line contains the number of test cases $T$.

$T$ test cases follow, each in the following format: The first line of each test case contains one integer $N$: the total number of mice siting at the table. The second line of each test case contains $N$ space-separated integers: the numbers $t_{0},\dots,t_{N-1}$.

### Output

For each test case, output two (subtasks 1 and 2) or one (subtasks 3 and 4) lines:

• A line of the form “Case #t: X” where $t$ is the test case number ($0 \le t < T$) and $X$ is the smallest number of seconds in which all $N$ mice can tell their stories.
• For subtasks 1 and 2 only: A line with $N$ space-separated integers $y_{0},\dots,y_{N-1}$ with the following meaning: Mouse $i$ should start telling its story $y_i$ seconds after the beginning of dinner.

If there are multiple optimal solutions, you may output any one of them.

### Limits

• For all test cases: $T=100$.

### Examples

Input:

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

Output:

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

• $2 \le N \le 8$, $t_i \le 32$ for all $i$.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

• $2 \le N \le 100$, $t_{0}=0$ and $t_i \le 100$ for all $i$.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

• $2 \le N \le 10^{5}$, $N$ is even, $t_i \le 10^{9}$ for all $i$.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

• $2 \le N \le 10^{5}$, $N$ is odd, $t_i \le 10^{9}$ for all $i$.

The contest is over, you can no longer submit. But you can still solve the task (‘upsolve’ it), and check your solution here.

You have 5 minutes and 0 seconds left.

Now assume that in subtasks 3 and 4 you were asked to also print the $y_{0},\dots,y_{N-1}$.

Give a proof that your solutions of subtask 3 and 4 are correct and analyze their running time. A correct proof for only one of the two subtasks (3 or 4) is worth at most 15 points.

We recommend the following proof template: (The italic statements should be completed by you.)

1. The algorithm looks like this and computes that because of this explanation.

2. Its running time and space usage is $O(?)$ because it’s true.

3. Given an arbitrary input $t_{0},\dots,t_{N-1}$, the output of the algorithm is both:

• an upper bound on the optimal solution: The numbers $y_{0},\dots,y_{N-1}$ as produced by the algorithm satisfy the constraints because of your proof thus any optimal solution must use at most $X$ seconds.
• a lower bound on the optimal solution: It is impossible that any solution uses less than $X$ seconds because of your proof.

Thus the output is optimal.

The contest is over, you can no longer submit.

## Tank Golf

Check out the Readme to the host server as well, there you find instructions on how to compile the host server. You can find some example bots in the directory bots/ to get you started.

If you encounter any problems while compiling the host server, don’t hesitate to ask questions to pascal@soi.ch.

See TankGolf on the Google Playstore for Android. The task is basically to write a bot for this game.

Two tanks are in a 2d physics simulation (upright), where a tank can shoot a bullet with a desired angle and intensity. The bullet causes an explotion wherever it impacts a surface, and the goal is to push or throw the other tank into a hole in the map through the shockwave of the explosion. The player take turns at shooting, and one can only shoot when both tanks have come to a rest after the last explosion (or the bullet shot by the opponent has fallen off the map). When a player falls through the hole, the opponent gets a point and the player respawns.

The task is to write a bot that, given the current positions and orientations of the tanks, determines an angle and intensity to shoot. The shot will be executed with a uniform random distribution within a small range around the desired angle and intensity. The uncertainty radius depends on the square of the intensity, such that long range shots are more risky than short range.

The game server provides a function to look up the impact position of the bullet, and the positions where the tanks come to a rest after the explosion, given a game state and desired trajectory. The bot can call this lookup function as often as you want, but please make sure that the bot doesn’t take longer than a few seconds for every turn (The time required to show the visualization isn’t counted in this). The randomness will only be added when the bot commits to a final shot, and does not affect any lookups.

The description of the map can be found in geometry/maps/map1.json, or you can look at it using the provided visualization. The map used in the contest will be exactly the same.

To respawn, your bot can chose an x-coordinate to spawn at, then the tank will drop down at this x-coordinate from a fixed y-coordinate. Y is fixed to make sure you can’t spawn into the floor or the other player. If you want to spawn right above the hole, you are very welcome to do so. There is also a query method available for respawning, similar to the query method for shots. A tank respawns as soon as they fell off the map. If both tanks fall off the map, both spawn in first, then the bots continue in their alternating order of shooting turns.

### Protocol

There are two types of round, one where the bot can line up a shot, and one where the bot chooses a spawn position.

Your bot will always see itself as player A in the protocol, so player B is always the opponent in the data that you receive.

A game state has two representations, one for transmitting the full state and one for a subset of the full state:

full: playerA.x playerA.y playerA.angle playerB.x playerB.y playerB.angle last_impact.x last_impact.y scores.playerA scores.playerB playerA.x playerA.y playerA.angle playerB.x playerB.y playerB.angle

A position that is not on the map is represented as -1, -1. For example a player position if they fell off the map or last_impact before the first shot are -1, -1.

Every round starts by the server sending the current type of round: ‘startrespawn’ or ‘startshoot’, followed by the full state (Initial spawn counts as respawn)

#### Respawn

Server: startrespawn

Player: queryrespawn 12.345 where the player asks what would happen if I drop down at this x position state

(… zero or more queries in total)

Player: respawn 12.345 respawn at this location

(turn is over)

#### Shoot

Server: startshoot

Player: queryrespawn 1.13 0.9 where the player asks what would happen if I shoot with this angle and intensity state

(.. zero or more queries in total)

Player: shoot 1.13 0.9 shoot with this angle and intensity

(turn is over)

#### Queries that are always possible while it’s your turn

Player: fullqueryshoot 1.13 0.9 where the player gives a game state and asks what would happen if I shoot with this angle and intensity state fullqueryrespawn 12.345 where the player gives a game state and asks what would happen if I drop down at this x position state

### Example

Note that this example only shows the communication for one of the players.

< is server to client and > is client to server

< startrespawn -1 -1 0 -1 -1 0 -1 -1 0 0   # We're player one and thus noone is on the map yet. Bullet hasn't impacted yet. Scores are at zero.
# read as: tank A: (-1, -1) 0 | tank B: (-1, -1) 0 | impact pos: (-1, -1) | scores: 0 0
> respawn 2                                # Spawn at position 2

(other player respawns)

< startshoot 2 1 0 6 1 0 -1 -1 0 0         # Other player has spawned at coordinate 6. We shoot first
> queryshoot -1.13 0.6                     # Simulate shot 1.13 radian to the right
< state 2 1 0 -1 -1 0 7.2 1                # Other player would fall in hole, we wouldn't move. We would get a point.
# read as: tank A: (2, 1) 0 | tank B: (-1, -1) 0 | impact pos: (7.2, 1) | scores: 1 0
> shoot -1.13 0.6                          # Shoot as simulated before.
# What the player doesn't know immediately, but what we see in the next server command is, that the shot
# didn't work out because of the added randomness (impact was at 7.4, 1). We didn't get a point.

(other player shoots)

< startrespawn -1 -1 0 4.6 1 0 1.5 1 0 1   # The other player scored during their turn (last impact was at 1.5, 1). We need to select a respawn position.
> respawn 6

< startshoot 6 1 0 4.6 1 0 1.5 1 0 1       # We get to shoot immediately after respawning, because the other player was the last one to shoot.
...


### Submit (100 points)

You play against the other participants of the SOI. At SOI-Day the programs will compete in a tournament to determine the best bot. You are allowed to submit up to three bots. Your best bot will be used for the ranking. Bundle the files in a zip archive when submitting.

The contest is over, you can no longer submit.