First Round SOI 2019

Overview

This contest is over.

TaskTotalSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
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 TT. TT configurations follow, each consisting of two lines. The first line contains the number of balls NN, the second line consists of NN numbers pip_i describing the size of the ii-th ball.

Output

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

Limits

  • T=100T=100
  • N=2N = 2
  • 1pi1061 \le p_i \le 10^{6}
  • p0=p1p_{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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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 tt-th configuration as “Case #t: s”, where ss is either “Single” if all balls merge to one ball, or “Multiple” if there are multiple balls left.

Limits

  • T=100T=100
  • 1N10001 \le N \le 1000
  • 1pi1061 \le p_i \le 10^{6}
  • p0=p1==pN1p_{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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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=100T=100
  • 1N10001 \le N \le 1000
  • 1pi1 \le p_i
  • The sum of all pip_i is at most 10910^{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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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

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

Input

The first line contains the number of test cases TT. TT test cases follow, each consisting of two lines. The first line contains the number of different sizes of balls NN and the maximal size CC which balls may reach. The second line contains NN numbers pip_i, the sizes of the balls which Mouse Stofl owns.

Output

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

Limits

  • T=100T=100
  • N=1N = 1
  • 1C1091 \le C \le 10^{9}
  • 1pi1091 \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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=100T=100
  • 1N1001 \le N \le 100
  • 1C10181 \le C \le 10^{18}
  • 1pi10181 \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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

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 NN skyscrapers. The height of the ii-th skyscraper is hih_i. You can ideally see the fireworks launched from the ii-th skyscraper from the jj-th skyscraper if and only if ii and jj are different and there is no kk for which both min(i,j)<k<max(i,j)\min(i,j)<k<\max(i,j) and hkhjh_k \ge h_j are true.

Please note that for subtasks 2, 3 and 5, it may take the server quite a long time to grade your solution. Please be patient.

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 TT. TT test cases follow, each consisting of two lines. The first line contains the number of skyscrapers NN and ii, the index of the skyscraper from which the fireworks are launched (always 0 in this subtask). The second line contains NN numbers hjh_j, each representing the height of the jj-th skyscraper.

Output

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

Limits

  • The number of test cases: T=100T = 100
  • The number of skyscrapers: 1N1001 \le N \le 100
  • The 0-based index of the building where the fireworks are launched: i=0i = 0
  • The height of the jj-th skyscraper for any jj: 1hj1031 \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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?

Input

Same as in Subtask 1.

Output

Same as in Subtask 1.

Limits

  • The number of test cases: T=100T = 100
  • The number of skyscrapers: 1N10000001 \le N \le 1\,000\,000
  • The 0-based index of the building where the fireworks are launched: i=0i = 0
  • The height of the jj-th skyscraper for any jj: 1hj1091 \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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 ii is not always 00 anymore.

Output

Same as in Subtask 1 and 2.

Limits

  • The number of test cases: T=100T = 100
  • The number of skyscrapers: 1N10000001 \le N \le 1\,000\,000
  • The 0-based index of the building where the fireworks are launched: 0i<N0 \le i < N
  • The height of the jj-th skyscraper for any jj: 1hj1091 \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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 TT. TT test cases follow, each consisting of two lines. The first line contains the number of skyscrapers NN. The second line contains NN numbers hjh_j, each representing the height of the jj-th skyscraper.

Output

For the ii-th test case, print out a single line “Case #i: M”, where MM 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=100T = 100
  • The number of skyscrapers: 1N1001 \le N \le 100
  • The height of the jj-th skyscraper for any jj: 1hj1091 \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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?

Input

Same as in Subtask 4.

Output

Same as in Subtask 4.

Limits

  • The number of test cases: T=100T = 100
  • The number of skyscrapers: 1N10000001 \le N \le 1\,000\,000
  • The height of the jj-th skyscraper for any jj: 1hj1091 \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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

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 TT (1T1001 \le T \le 100) – the number of test cases which follow.

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

hh lines follow, each containing exactly ww characters. The ii-th character of the jj-th line describes whether there is a building or not at position x=ix=i, y=jy=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 tt is the number of the test cases (0-based in increasing order) and pp 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=0x = 0 or y=0y = 0 or x=w1x = w-1 or y=h1y = h-1.

Limits

w,h100w, 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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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 hh lines with ww characters each, the following format is now used to describe the old city:

A line containing rr, the number of roads, followed by rr lines, each describing one road. The ii-th of these lines contains 4 integers xix_i, yiy_i, wiw_i, and hih_i (0xi,yi0 \le x_i, y_i, 1wi,hi1 \le w_i, h_i, xi+wiwx_i + w_i \le w, yi+hihy_i + h_i \le h). The position at xx, yy is covered by road #i if xixxi+wi1x_i \le x \le x_i + w_i - 1 and yiyyi+hi1y_i \le y \le y_i + h_i - 1. The roads can (but don’t have to) overlap, for example at an intersection.

Output

Same as in subtask 1.

Limits

w,h100w, h \le 100, r100r \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Subtask 3: Bigger map (30 points)

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

Input

Same as in subtask 2.

Output

Same as in subtask 1 and 2.

Limits

w,h109w, h \le 10^{9}, r103r \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Subtask 4: Even bigger map (30 points)

This is the same as subtasks 2 and 3, but with even bigger inputs. Careful: Please read the section grading.

Input

Same as in subtask 2 and 3.

Output

Same as in previous subtasks.

Grading

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(rlogr)O(r \log r) (possibly with some additional log factors).

Update (2018-09-16): Previously it was written O(nlogn)O(n \log n). We expect that the solution runs quasilinear in rr, 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 Θ(r2)Θ(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,h109w, h \le 10^{9}, r105r \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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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

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 PP pump stations. For that you have located NN 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 NN and LL (the maximal allowed LTC), as well as the possible building locations (x0,x1,,xN1x_{0},x_{1},\dots,x_{N-1}, where xix_i is the ii-th possible location for a pump station). Compute the minimal number of pump stations PP needed for an LTC of at most LL.

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

Input

The first line contains the number of test cases TT. TT test cases follow, each with NN and LL on the first and x0,x1,,xN1x_{0},x_{1},\dots,x_{N-1} on the second line. The locations are given in increasing order.

Output

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

  • a number P9000P\le 9000 followed by PP integers p0<p1<<pP1p_{0}<p_{1}<\dots<p_{P-1}. PP is the minimal number of pump stations needed and pip_i is the location of the ii-th pump station. If there are multiple solutions using PP pump stations, print any of them.
  • just a number P>9000P>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 LL.

Limits

  • T=100T=100
  • 1N1000001 \le N \le 100\,000
  • 1L1091 \le L \le 10^{9}
  • 0x0<x1<<xN11090\le x_{0}<x_{1}<\dots<x_{N-1}\le 10^{9}

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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Subtask 2: Fixed Pumps Count (15 points)

This time you know NN and PP, 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 TT. TT test cases follow, each with NN and PP on the first and x0,x1,,xN1x_{0},x_{1},\dots,x_{N-1} on the second line.

Output

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

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

Limits

  • T=100T=100
  • 1N1000001 \le N \le 100\,000
  • min(2,N)PN\min(2, N) \le P \le N
  • 0x0<x1<<xN11090\le x_{0}<x_{1}<\dots<x_{N-1}\le 10^{9}

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

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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 NN building locations. Even worse, neither PP nor the LTC are fixed. You only know an upper bound MM on the LTC, meaning that you never want to have an LTC higher than MM.

To deal with those numbers you write a program. You tell the program MM, the maximal number LTC you will allow. Then, the program reads all NN building locations in increasing order. In the end, it will give you MM numbers: the ii-th number (0-based) tells you the minimal number of pumps you need for guaranteeing an LTC of at most i+1i+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 TT. TT test cases follow, each with NN and MM on the first and x0,x1,,xN1x_{0},x_{1},\dots,x_{N-1} on the second line.

Output

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

Limits

  • T=100T=100
  • 1N1000001 \le N \le 100\,000
  • 1M2501 \le M \le 250
  • 0x0<x1<<xN11090\le x_{0}<x_{1}<\dots<x_{N-1}\le 10^{9}

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.

Download input again
You have 5 minutes and 0 seconds left.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

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

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

Limits

  • NN and MM are variables, i.e., you should use them in your analysis. You can assume that NN is much larger than MM.
  • The xix_i are sorted (0x0<x1<<xN10\le x_{0}<x_{1}<\dots<x_{N-1}) 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.

Grading

The memory consumption of your data structure should only depend on MM, not NN. Aim for O(M)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(M) O(NM)O(N\cdot M) 20
O(M1.5)O(M^{1.5}) O(NM0.75)O(N\cdot M^{0.75}) 40
O(M)O(M) O(NM0.75)O(N\cdot M^{0.75}) 50
O(MlogM)O(M\log M) O(NM0.5logM)O(N\cdot M^{0.5} \log M) 50
O(M)O(M) O(NM0.5(logM)2)O(N\cdot M^{0.5} (\log M)^{2}) 60

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

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 NN 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 t0,,tN1t_{0},\dots,t_{N-1} – the lengths (in seconds) of the stories our NN 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 TT.

TT test cases follow, each in the following format: The first line of each test case contains one integer NN: the total number of mice siting at the table. The second line of each test case contains NN space-separated integers: the numbers t0,,tN1t_{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 tt is the test case number (0t<T0 \le t < T) and XX is the smallest number of seconds in which all NN mice can tell their stories.
  • For subtasks 1 and 2 only: A line with NN space-separated integers y0,,yN1y_{0},\dots,y_{N-1} with the following meaning: Mouse ii should start telling its story yiy_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=100T=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

Subtask 1 (20 Points)

  • 2N82 \le N \le 8, ti32t_i \le 32 for all ii.

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.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Subtask 2 (20 Points)

  • 2N1002 \le N \le 100, t0=0t_{0}=0 and ti100t_i \le 100 for all ii.

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.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Subtask 3 (15 Points)

  • 2N1052 \le N \le 10^{5}, NN is even, ti109t_i \le 10^{9} for all ii.

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.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Subtask 4 (15 Points)

  • 2N1052 \le N \le 10^{5}, NN is odd, ti109t_i \le 10^{9} for all ii.

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.

If the time expires, or you don’t get full points, you can try again by downloading a fresh input.

You can directly run C++ solutions in your browser. For other languages, you need to download the input and manually run your solution. Please note that running in the browser is slower than running natively.

Do not navigate away while your solution is running.


            

        

Subtask 5 (30 Points)

Now assume that in subtasks 3 and 4 you were asked to also print the y0,,yN1y_{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(?)O(?) because it’s true.

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

    • an upper bound on the optimal solution: The numbers y0,,yN1y_{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 XX seconds.
    • a lower bound on the optimal solution: It is impossible that any solution uses less than XX seconds because of your proof.

    Thus the output is optimal.

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

Tank Golf

To solve this task, you should first download the host server for the game, which allows you to test your bot locally.

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
small: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 <full game state>

(player asks a query…)

Player:queryrespawn 12.345 where the player asks what would happen if I drop down at this x position
Server:state <full resulting state at rest>

(… zero or more queries in total)

Player:respawn 12.345 respawn at this location

(turn is over)

Shoot

Server:startshoot <full game state>

(player asks a query..)

Player:queryrespawn 1.13 0.9 where the player asks what would happen if I shoot with this angle and intensity
Server:state <full resulting state at rest>

(.. 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 <small state> 1.13 0.9 where the player gives a game state and asks what would happen if I shoot with this angle and intensity
Server:state <full resulting state at rest>
Player:fullqueryrespawn <small state> 12.345 where the player gives a game state and asks what would happen if I drop down at this x position
Server:state <full resulting state at rest>

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.

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

Ranking

RankUsernameTotal (600)mergeball (100)ceremony (100)tourist… (100)
touristtrap
pipeline (100)storyte… (100)
storytelling
tankgolf (100)
loading ...