First Round SOI 2019

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

2
2
5 5
2
7 7

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.

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

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

Case #0: Multiple
Case #1: Single

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

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

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

Case #0: Single
Case #1: Multiple

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

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

2
1 20
5
1 50
7

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.

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

2
2 30
5 10
4 50
3 6 7 123

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.

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

1
6 0
3 2 4 4 6 5

Case #0: 3

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

Input

Same as in Subtask 1.

Output

Same as in Subtask 1.

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.

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

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

Case #0: 4

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

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

1
9
5 3 2 4 3 2 3 3 1

Case #0: 5

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

Input

Same as in Subtask 4.

Output

Same as in Subtask 4.

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.

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

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

Case #0: POSSIBLE
Case #1: IMPOSSIBLE

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

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.

Output

Same as in subtask 1.

Limits

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

Sample

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

Case #0: POSSIBLE
Case #1: IMPOSSIBLE

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

Input

Same as in subtask 2.

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.

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

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_{1}<\dots<p_{P-1}$. $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}<x_{1}<\dots<x_{N-1}\le 10^{9}$

Example

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

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

Big input:

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

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

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

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}<x_{1}<\dots<x_{N-1}\le 10^{9}$

Example

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

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

Big input:

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

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

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

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}<x_{1}<\dots<x_{N-1}\le 10^{9}$

Example

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

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.

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

The contest is over, you can no longer submit.

Subtask 1 (20 Points)

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

Subtask 2 (20 Points)

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

Subtask 3 (15 Points)

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

Subtask 4 (15 Points)

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

Subtask 5 (30 Points)

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.

Respawn

(player asks a query…)

(… zero or more queries in total)

(turn is over)

Shoot

(player asks a query..)

(.. zero or more queries in total)

(turn is over)

Queries that are always possible while it’s your turn