First Round SOI 2022/2023

Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

• The first line contains a single integer $N$ denoting the number of places.
• The second line consists of $N$ integers $x_i$ denoting the position of the $i$-th place.
• The third line consist of $N$ integers $h_i$ denoting the height of the $i$-th place.

Output

For the $i$-th testcase, output a line containing “Case #i:” followed by $N$ integers, where the $j$-th integer is the maximum flight distance if Binna begins at place $j$.

Limits

• $T=100$.
• $N = 2$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i \neq h_j$ for $i \neq j$, the height of each place is distinct.

Example

2
2
3 5
10 20
2
0 639
732 554

Case #0: 0 2
Case #1: 639 0

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

Limits

• $T=100$.
• $2 \le N \le 3\,000$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i > h_j$ for $i < j$, the heights of the places are decreasing (this is a special restriction of this subtask).

Example

2
5
1 3 6 8 9
8 6 5 2 1
6
0 1430 2870 5310 7590 9340
3089 2819 2582 2210 1770 1604

Case #0: 8 6 3 1 0
Case #1: 9340 7910 6470 4030 1750 0

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

Limits

• $T=100$.
• $2 \le N \le 3\,000$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• There is an index $k$ such that $h_{0}< {\dots} < h_{k - 1} < h_k > h_{k + 1} > {\dots} > h_{n - 1}$ (this is a special restriction of this subtask).

Example

2
6
1 2 6 7 8 9
1 4 5 7 6 2
8
0 957 1370 1981 2873 3001 3651 4781
675 836 949 1014 885 881 730 565

Case #0: 0 1 5 6 1 0
Case #1: 0 957 1370 2800 1908 1780 1130 0

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

Limits

• $T=100$.
• $2 \le N \le 3\,000$.
• $1 \le x_i, h_i \le 10^{9}$.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i \neq h_j$ for $i \neq j$, the height of each place is distinct.

Example

2
5
1 2 3 4 5
5 3 1 2 4
5
1 3 6 8 9
2 1 3 5 4

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

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

Limits

• $T=100$.
• $2 \le N \le 10^{6}$.
• $1 \le x_i, h_i \le 10^{12}$. Note that these increased limits lead to large results.
• $x_i < x_{i+1}$, the places are given in increasing order of position.
• $h_i \neq h_j$ for $i \neq j$, the height of each place is distinct.

Example

3
5
1 2 3 4 5
5 3 1 2 4
5
1 3 6 8 9
2 1 3 5 4
2
0 384403739351
384403739351 0

Case #0: 10
Case #1: 14
Case #2: 384403739351

Note that all but at most $10$ test cases in this subtask also satisfy the limits of the previous subtask. Please be patient, generating the test data can take a while.

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 of the following format:

• The first line contains two integers $N$ and $M$, the length of the puzzle and the number of positions of the knob.
• The second line contains $N$ integers $x_{0}, x_{1}, {\dots}, x_{N-1}$, where $x_i$ is the $i$-th position the knob needs to be rotated to.
• The third line contains a string of length $N$, where the $i$-th character indicates $d_i$.

Output

For the $i$-th testcase, output a line containing “Case #i:” followed by a single integer: the total number of wind-up steps.

Limits

• $T=100$.
• $1 \le N \le 1\,000\,000$.
• $1 \le M \le 10^{12}$.
• $0 \le x_i < M$ for all $0\le i<N$.
• $d_i=\mathtt{"L"}$ or $d_i=\mathtt{"R"}$ for all $0\le i<N$.

Example

4
1 10
3
R
1 10
3
L
2 10
3 8
RL
5 1000000000000
0 1 1 9 5
RLRLR

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

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 of the following format:

• The first line contains two integers $N$ and $M$, the length of the puzzle and the number of positions of the knob.
• The second line contains $N$ integers $x_{0}, x_{1}, {\dots}, x_{N-1}$, where $x_i$ is the $i$-th position the knob needs to be rotated to.

Output

For the $i$-th testcase, output a line containing “Case #i:” followed a single integer: the minimal total number of wind-up steps to solve this puzzle.

Limits

• $T=100$.
• $1 \le N \le 1\,000\,000$.
• $1 \le M \le 10^{12}$.
• $0 \le x_i \le M-1$ for all $0\le i<N$.
• $0 \le x_{0}\le x_{1}\le x_{2}\le {\dots} \le x_{N-2} \le x_{N-1}$. This is the special restriction for this subtask.

Example

3
3 5
1 2 3
4 8
1 3 3 7
1 10
9

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

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

Input and Output

Same as subtask 2.

Limits

• $T=100$.
• $1 \le N \le 100$. This is the special restriction for this subtask.
• $1 \le M \le 10^{12}$.
• $0 \le x_i \le M-1$ for all $0\le i<N$.

Example

2
5 7
4 0 2 4 6
11 3
2 1 2 0 2 1 2 0 2 1 2

Case #0: 7
Case #1: 6

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

Input and Output

Same as subtasks 2 and 3.

Limits

• $T=100$.
• $1 \le N \le 5\,000\,000$.
• $1 \le M \le 10^{12}$.
• $0 \le x_i < M$ for all $0\le i<N$.

Note that all but at most 30 test cases in this subtask also satisfy $N \le 1000$.

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

Example

3
1 1
.
1 1
#
1 4
#.##

Case #0: Yes
Case #1: Yes
C 0
Case #2: Yes
C 3
R 0
C 0

Example

3
2 2
.#
##
2 2
#.
..
2 4
#.##
##..

Case #0: Yes
C 1
C 1
R 1
Case #1: No
Case #2: Yes
R 0
R 0
C 0
C 0
C 1

Example

3
3 3
.#.
###
...
3 4
##..
.##.
..##
4 5
##...
.####
..#.#
....#

Case #0: Yes
R 1
R 1
C 1
R 1
Case #1: Yes
R 2
R 2
C 2
R 1
C 1
R 0
Case #2: No

Input

The first line contains the number of test cases $T$. $T$ test cases follow in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to be play them. A third line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order.

Output

For the $i$-th test case, output a line “Case #i: M”, where M is “No” if you can’t win all turns, otherwise “Yes” followed by $N$ integers separated by spaces $c_{0}\ldots c_{N-1}$, the values of your cards in the order you’re going to play them.

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 1\,000$.

Example

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

Case #0: Yes 5 1 4
Case #1: Yes 1
Case #2: No
Case #3: No

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 in the following format:

The first line of the test case contains a single integer: $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order.

Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the smallest possible number of turns that you can win.

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 500\,000$.

Note that all but at most $10$ test cases in this subtask also satisfy $1 \le N \le 10\,000$.

Example

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

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

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 in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order. A fourth line follows with $N$ integers $s_{0},\ldots,s_{N-1}$, the scores of your cards. (The $i$-th card has value $b_i$ and score $s_i$).

Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the largest possible total score that you can achieve.

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 1\,000$. All scores are $1 \le s_i \le 100\,000$.

Example

2
3
2 0 3
1 5 4
3 2 1
3
1 3 4
0 2 5
11 3 7

Case #0: 6
Case #1: 10

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 in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $r_{0},\ldots,r_{N-1}$, the scores of Stofl’s cards. (The $i$-th card has value $a_i$ and score $r_i$). A fourth line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order.

Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the largest possible total score that you can achieve.

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 500\,000$. All scores are $1 \le r_i \le 100\,000$.

Note that all but at most $10$ test cases in this subtask also satisfy $1 \le N \le 10\,000$.

Example

2
3
2 1 4
4 1 1
0 5 3
3
2 3 5
11 3 7
0 1 4

Case #0: 5
Case #1: 11

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 in the following format:

The first line of the test case contains $N$, the number of cards of each player. A second line follows with $N$ integers $a_{0},\ldots,a_{N-1}$, Mouse Stofl’s card values in the order he’s going to play them. A third line follows with $N$ integers $r_{0},\ldots,r_{N-1}$, the scores of Stofl’s cards. (The $i$-th of Stofl’s cards has value $a_i$ and score $r_i$). A fourth line follows with $N$ integers $b_{0},\ldots,b_{N-1}$, your own card values in an arbitrary order. A fifth line follows with $N$ integers $s_{0},\ldots,s_{N-1}$, the scores of your cards. (The $i$-th of your cards has value $b_i$ and score $s_i$).

Output

For the $i$-th test case, output a line “Case #i: M”, where $M$ is the largest possible total score that you can achieve.

Limits

There are $T=100$ test cases. In every test case, $1 \le N \le 500\,000$. All scores are $1 \le s_i, r_i \le 100\,000$.

Note that all but at most $10$ test cases in this subtask also satisfy $1 \le N \le 10\,000$.

Example

2
3
2 1 4
4 1 1
0 5 3
7 2 3
3
0 3 5
11 3 7
1 2 4
5 2 1

Case #0: 10
Case #1: 20

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 a single integer $T$, the number of test cases.

$T$ lines follow, each with two integers $N$ and $M$: There are $N \times M$ rooms.

Output

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

This should be followed by an ASCII representation of the crypt with some walls removed. A description of such a representation follows, but it might be easier to look at the examples below.

• If the rooms are adjacent horizontally, place a minus sign (”-”) between the corresponding letters $o$.
• If the rooms are adjacent vertically, place a pipe character (”|”) between the corresponding letters $o$.

Limits

• $T=100$.
• $2 \le N \cdot M \le 1000$.

Examples

2
3 3
4 3

Case #0:
o.o.o
|.|.|
o-o-o
|...|
o-o.o
Case #1:
o-o-o
..|..
o-o.o
|...|
o-o-o
..|.|
o-o.o

The following is an example of invalid output

3
3 3
3 3
3 3

Case #0:
o-o-o
..|..
o-o-o
..|..
o-o-o
Case #1:
o-o-o
|...|
o.o-o
|...|
o-o-o
Case #2:
o-o.o
|...|
o.o.o
..|.|
o-o-o

Interactive visualization

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

Feedback

The following example should help you understand some of the automatic feedback you might receive. Click on the box below to see it.

3
2 2
2 2
3 4

Case #0:
o-o
..|
o!o
Case #1:
o-o

..|
o!o
Case #2:
o-o-o-o
....|..
o-o-o-o
....|..
o-o-o-o

Input

The first line of input is $T$, the number of crypt layouts you should output. This number is always 20.

This will be followed by $T$ lines containing the indices of the testcases, i.e. the first line contains the number $0$, the second line the number $1$ etc.

Note that your program doesn’t actually have to read any input since the input file will always be the same.

Output

Output twenty crypt layouts. For the $i$-th crypt, output Case #i: N M with some integers $N$ and $M$ of your choice: The height and width of the crypt. After that, output the crypt itself like in Subtask 1. It should have $N \times M$ rooms.

No two crypts may have the same width and the same height. It is, however, allowed to output any number of crypts with the same width or the same height.

Limits

• $T = 20$.
• $2 \le N \cdot M \le 1000$. Note that this isn’t a constraint on the input file, but on your output file.

Example

2
0
1

Case #0: 1 2
o-o
Case #1: 2 3
o-o-o
..|..
o-o-o

The following is an example of invalid output

3
0
1
2

Case #0: 3 3
o.o.o
|.|.|
o-o-o
|...|
o-o.o
Case #1: 1 2
o-o
Case #2: 1 2
o-o

Interactive visualization

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 Subtask 1.

Output

For the $i$-th crypt, print a line “Case #i: Possible” or “Case #i: Impossible”, depending on whether it is possible to remove some walls from a $N \times M$ crypt in order to satisfy all constraints

If it is possible, output the ASCII representation as in Subtasks 1 and 2.

Limits

Same as Subtask 1.

Example

3
1 2
2 2
2 3

Case #0: Possible
o-o
Case #1: Impossible
Case #2: Possible
o-o-o
..|..
o-o-o

Interactive visualization

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

Feedback

Note that the automatic grader will not tell you if you wrongly answer “Possible”. It will only point out why your output is not a solution. This can either mean there is a solution, but you did something wrong, or it can mean there is no solution.

Limits

• $N$, $M$ are variables. 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 unit of memory.

The contest is over, you can no longer submit.

Input

The first line contains the number of test cases $T$. $T$ test cases follow of the following format:

• The first line contains one integer $N$ – the number of springs.
• The second line contains $N$ integers $t_i$ – the temperature of the $i$-th spring ($0 \leq i < N$).
• The third line contains $N$ integers $m_i$ – the amount of minerals in the water of the $i$-th spring ($0 \leq i < N$).
• The fourth line contains $N$ integers $s_i$ – the intensity of the sulfur smell at the $i$-th spring ($0 \leq i < N$).
• The fifth line contains $N$ integers $p_i$ – the beauty of the panorama at the $i$-th spring ($0 \leq i < N$).

Output

For the $t$-th test case print a line “Case #t:” followed by “YES” or “NO”, depending on whether Binna can bathe at all the springs. If the answer was “YES”, then print a single line with $N$ integers – the order in which Binna can bathe at the springs. (Springs are numbered from $0$ to $N-1$.)

Limits

• $T=100$.
• $1 \le N \le 300$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

Example

4
2
2 1
2 1
1 2
2 1
2
1 2
1 2
1 2
1 2
3
9 4 7
8 2 3
12 44 13
5 1 4
3
1 1 1
2 2 2
3 3 3
4 4 4

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

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 format as subtask 1.

Output

For the $t$-th test case print a line “Case #t:” followed by an integer $S$ – the maximum number of springs Binna can bathe at while ensuring that every spring is better then the previous. On the next line print $S$ integers – the springs Binna bathes at, in order. If there are multiple optimal solutions, you may print any one of them.

Limits

• $T=100$.
• $1 \le N \le 300$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

Example

4
2
2 1
2 1
1 2
2 1
2
1 2
1 2
1 2
1 2
3
1 1 1
2 2 2
3 3 3
4 4 4
3
4 1 8
2 3 8
9 8 7
1 5 6

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

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

For the $t$-th test case print a line “Case #t:” followed by “YES” or “NO”, depending on whether Binna and Stofl can find two routes such that every spring will be bathed at by exactly one mouse. If the answer was “YES, then print two more lines. The first line should contain the springs Binna bathes at, it order, and the second line should contain the springs Stofl bathes at, in order. (Springs are numbered from $0$ to $N-1$.)

Limits

• $T=100$.
• $1 \le N \le 1000$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

Example

4
2
1 2
1 2
1 2
1 2
2
2 1
2 1
1 2
2 1
3
1 1 1
2 2 2
3 3 3
4 4 4
3
4 1 8
2 3 8
9 8 7
1 5 6

Case #0: YES
1
0
Case #1: YES
1 0

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

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

Limits

• $T=100$.
• $1 \le N \le 100\,000$.
• $1 \le t_i, m_i, s_i, p_i \le 10^{9}$.

Note that all but at most $10$ test cases in this subtask also satisfy the limits of the previous subtask.

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 of the following format:

• The first line contains one integer $N$, the number of rooms and colors.
• The $j$-th of the next $N-1$ lines describes the $j$-th passage and contains two integers: the numbers $u_j$ and $v_j$ of the rooms this passage connects.
• The $i$-th of the next $N$ lines describes the painting in the $i$-th room: the number $k_i$ of colors it needs, followed by $k_i$ distinct colors $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$.

Output

For the $t$-th test case, output a line containing “Case #t:”, followed by a space and an integer equal to the minimum number of times Stofl needs to carry a bucket of paint along a passage in order to apply all required colors to each painting and then bring each bucket to its original location.

Limits

• $T=100$.
• $2 \le N \le 1000$.
• $0 \le k_i \le 1$ for all $0\le i<N$.
• $a_{i1} = 0$ for all $0\le i<N$ such that $k_i = 1$.

Example

1
3
0 1
1 2
1 0
1 0
0

Case #0: 2

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

Input/Output

Same as subtask 1.

Limits

• $T=100$.
• $2 \le N \le 1000$.
• $0 \le k_i \le N$ for all $0\le i<N$.
• The sum $\sum k_i \le 1000$.

Example

1
3
0 1
0 2
0
2 2 1
2 2 0

Case #0: 6

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 of the following format:

• The first line contains two integers $N$ and $M$, the number of rooms and colors, and the number of apprentices.
• The $j$-th of the next $N-1$ lines describes the $j$-th passage and contains two integers: the numbers $u_j$ and $v_j$ of the rooms this passage connects
• The $i$-th of the next $N$ lines describes the painting in the $i$-th room: the number $k_i$ of colors it needs, followed by $k_i$ distinct colors $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$.

Output

For the $t$-th test case, output a line containing “Case #t:”, followed by a space and an integer equal to the minimum number of times Stofl needs to carry a bucket of paint himself along a passage in order to apply all required colors to each painting and then bring each bucket to its original location.

Limits

• $T=100$.
• $2 \le N \le 1000$.
• $0 \le M \le 1000$.
• $0 \le k_i \le N$ for all $0\le i<N$.
• The sum $\sum k_i \le 1000$.

Example

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

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/Output

Same as subtask 3.

Limits

• $T=100$.
• $2 \le N \le 3 \cdot 10^{5}$.
• $0 \le M \le 3 \cdot 10^{5}$.
• $0 \le k_i \le N$ for all $0\le i<N$.
• The sum $\sum k_i \le 3 \cdot 10^{5}$.

Note that all but at most $10$ test cases in this subtask also satisfy the limits of the previous subtask.

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