First Round SOI 2023/2024

Input

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

Output

For the $i$-th test case, output a line “Case #i: YES” if it’s possible to swap the items in the baskets so that everyone has the same amount of items in their baskets, or “Case #i: NO” otherwise.

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le n \le 1000$
• $0 \le a_i \le 1000$

Example

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

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

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 test case, output a line “Case #i: x” where $x$ is the minimum number of items Binna has to move.

In this and all following subtasks, it is guaranteed that Binna can distribute the items to the baskets equally (in particular that means for all the following cases the answer in Subtask 1 would be yes).

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le n \le 1000$
• $0 \le a_{0}\le 1000$
• $a_i = 1$ for all $i>0$

Example

3
5
6 1 1 1 1
2
15 1
1
4

Case #0: 4
Case #1: 7
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 & Output

Same as subtask 2.

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le n \le 1000$
• $0 \le a_{0}\le 1000$
• $|a_i - a_j| \le 2$ for all $i,j$

Example

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

Case #0: 1
Case #1: 1
Case #2: 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 & Output

Same as subtask 3.

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le n \le 1000$
• $0 \le a_i \le 1000$.

Example

4
4
3 1 3 1
2
2 2
5
14 8 4 3 6
3
20 3 1

Case #0: 2
Case #1: 0
Case #2: 8
Case #3: 12

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

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le n \le 10^{5}$
• $0 \le a_i \le 10^{10}$.

Attention: The numbers in this subtask will get very large. If you use integers (e.g. in C++) then you should switch to a larger datatype (e.g. long long) instead to avoid overflows.

Example

2
4
3 1 3 1
2
0 10000000000

Case #0: 2
Case #1: 5000000000

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 $K$ and $N$, the number of painters, and the total number of paintings.
• Each of the $K$ following lines contains a number $N_i$, followed by $N_i$ numbers $v_{i, 0},v_{i, 1},{\dots},v_{i, N_i-1}$, the values in Egyptian pounds of all the $N_i$ paintings of painter $i$.

In this subtask, we always have $K=1$.

Output

For the $t$-th test case print a line “Case #t:” followed by $N-1$ numbers, where the $i$-th number ($0 \le i < N-1$) is the total value of all paintings of the most expensive exhibition with $i+2$ paintings, and where no painter has exactly one painting in the exhibition. It is guaranteed that such an exhibition exists for each $i$.

Limits

• $T=100$
• $K=1$
• $2 \le N_i$ for all $0\le i<N$
• $N = \sum_i N_i$
• $N \le 1000$
• $1 \le v_{i, j} \le 10^{5}$ for all $0\le i<N$, $0\le j<N_i$

Example

3
1 2
2 4 3
1 3
3 8 5 7
1 4
4 3 3 3 3

Case #0: 7
Case #1: 15 20
Case #2: 6 9 12

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 in subtask 1.

In this subtask, we always have $K=2$.

Limits

• $T=100$
• $K=2$
• $2 \le N_i$ for all $0\le i<N$
• $N = \sum_i N_i$
• $N \le 5000$
• $1 \le v_j \le 10^{5}$ for all $0\le j<N_i$

Example

2
2 5
3 6 5 6
2 1 2
2 7
3 5 5 6
4 1 7 6 2

Case #0: 12 17 15 20
Case #1: 13 16 24 29 31 32

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 in subtask 1.

Limits

• $T=100$
• $1 \le K \le 500$
• $2 \le N_i$ for all $0\le i<N$
• $N = \sum_i N_i$
• $N \le 1000$
• $1 \le v_j \le 10^{5}$ for all $0\le j<N_i$

Example

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

Case #0: 14 17 26 29 36 39 41 42
Case #1: 14 18 28 32 38 42 46 49 52 55 58 60 61 62

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 in subtask 1.

Limits

• $T=100$
• $1 \le K \le 40000$
• $2 \le N_i$ for all $0\le i<N$
• $N = \sum_i N_i$
• $N \le 80000$
• $1 \le v_j \le 10^{5}$ for all $0\le j<N_i$

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$. The $T$ test cases follow in the following format:

• The first line contains two integers $N$ and $M$, the number of rows and columns of the grid respectively.
• The next $N$ lines will contain $M$ characters either “#” or “.”. “#” indicates the cell contains an island, “.” indicates you can travel freely from and to this cell.

A valid trip from the top row to the bottom one is guaranteed to exist.

Output

For the $t$-th test case, output a line “Case #t:”, followed by the number $L$, the maximum possible length of a trip.

Limits

• $T=100$
• $M=2$
• $1 \le N \le 10^{6}$

Example

2
3 2
..
.#
.#
5 2
#.
#.
..
..
.#

Case #0: 4
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.

Limits

• $T=100$
• $2 \le M \le 20$
• $1 \le N \le 5\cdot 10^{5}$

Example

2
3 5
...#.
.#.#.
...#.
5 6
...#..
..##..
...#..
.#....
.#.#..

Case #0: 7
Case #1: 13

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 in the previous subtasks. Additionally, in this subtask it is guaranteed that there exists a valid trip from the top row to the bottom row which only requires Stofl to move down and to the right. You need to output the longest possible length of such a trip.

Limits

• $T=100$
• $2 \le N \cdot M \le 5\cdot 10^{6}$

Example

2
5 6
...#..
..##..
...#..
.#..#.
.#.#..
7 8
.##.#.#.
#..#..#.
.#......
...##.##
##.##..#
...#.#.#
.#...#.#

Case #0: 7
Case #1: 8

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 \cdot M \le 5 \cdot 10^{6}$

Example

Same as Subtask $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

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

Output

For the $i$-th test case, output a line "Case #i: " followed by single integer number $s$ — the maximum total productivity score Binna can get for all events.

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le n \le 1000$
• $0 \le m \le 1000$
• $k = 0$
• $0 = l_i \le r_i < n$ for all $0 \le i \le m-1$.

Example

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

Case #0: 14
Case #1: 9
Case #2: 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 & Output

Same as subtask 1.

Limits

Same as subtask 1, except that for $l_i$ we have $0 \le l_i < n$.

Example

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

Case #0: 9
Case #1: 8
Case #2: 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 & Output

Same as subtask 2.

Limits

Same as subtask 2, but $n \le 10^{5}$ and $m \le 10^{5}$.

Example

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

Case #0: 9
Case #1: 8
Case #2: 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 & Output

Same as subtask 2.

Limits

Same as subtask 2, but $0 \le k \le n$.

Example

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

Case #0: 14
Case #1: 11
Case #2: 8

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

Limits

Same as subtask 4, but $n \le 10^{5}$ and $m \le 10^{5}$.

Example

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

Case #0: 47
Case #1: 1
Case #2: 0
Case #3: 56

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$. This is followed by $T$ test cases in the following format: The first line of the test case contains $N$, the number of chambers in the labyrinth.

$N$ lines follow, each line has two characters $m_i$ $t_i$, either “0” or “1”, separated by a space. The first character represents the number of torches that should be present in the chamber at the end. The second character represents the number of torches in the chamber at the beginning. The total number of torches that should be in the end is the same as the number of torches in the beginning.

Then $N-1$ more lines follow, describing the structure of the labyrinth. Each line with two integers $v_i$ $u_i$, separated by a space, representing a corridor between the chamber $v_i$ and $u_i$.

Output

For the $i$-th test case, output single line “Case #i:”, followed by a single integer, the minimal amount of time a torch moves through a corridor.

For every input, it is guaranteed that there is a sequence of torch moves that places a torch in each chamber according to the map.

Note for Recursion and Python

You might hit recursion limit, memory limit, stack limit or similar, if you are using recursive functions in python. See this wiki article on possible solutions for these problems.

Limits

There are $T=100$ test cases. In every test case:

• $1 \le N \le 100\,000$
• $u_i = 0$

Example

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

Case #0: 2
Case #1: 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

There are $T=100$ test cases. In every test case:

• $1 \le N \le 100\,000$
• $c_i = 1$ for one $i$ and $c_i = 0$ for all else
• $t_i = 1$ for one $i$ and $t_i = 0$ for all else

Example

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

Case #0: 3
Case #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.

Limits

There are $T=100$ test cases. In every test case:

• $1 \le N \le 1\,000\,000$
• $u_i = v_i - 1$ for $1 \le u_i \le N-1$

Example

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

Case #0: 3
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.

Limits

There are $T=100$ test cases. In every test case:

• $1 \le N \le 1\,000$

Example

2
15
0 0
1 1
1 0
0 0
1 1
1 0
0 1
0 0
1 1
1 0
0 0
0 0
0 1
0 1
0 0
0 1
0 2
1 3
1 4
2 5
3 6
3 7
4 8
5 9
6 10
6 11
7 12
8 13
9 14
6
0 0
0 0
0 1
0 1
1 0
1 0
0 1
0 2
1 3
1 4
2 5

Case #0: 17
Case #1: 3

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

Limits

There are $T=100$ test cases. In every test case:

• $1 \le N \le 1\,000\,000$

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 number contains the number of test cases $T$. The $T$ test cases follow in the following format:

The first line of each test case contains three numbers $N,K,M$ which represent the number of stones, the number of stable patches (including the ones the stones are currently lying on) and the number of instructions Stofl gives you.

The next $K$ lines will describe the piles of stone. Each of these lines starts with a number $r$ with $0\le r\le N$, the number of stones on this pile, followed by $r$ numbers $s_{0},s_{1},{\dots}s_{r-1}$ where $0 \le s_i\le N-1$ indicating the size of the $i$-th stone on this pile from the bottom to the top (that is, $s_{0}$ is the size of the bottom most stone and $s_{r-1}$ is the size of the stone on top of the pile).

The next $M$ lines will each contain two numbers, $a$ and $b$ with $0\le a,b\le K-1$, that represent that we moved the top element from stack $a$ to stack $b$. It is guaranteed that this is a legal move (this is, that stack $a$ is not empty).

It is guaranteed that every stone size from $0$ to $N-1$ appears exactly once.

Output

For the $t$-th test case, on the first line print “Case #t:”. This should be followed by $K$ lines, where the $i$-th line first contains a number $r_i$ indicating the number of stones on the $i$-th pile after you executed all of Stofl instruction, followed by $r_i$ numbers $s_{0},s_{1},{\dots},s_{r_i-1}$ separated by spaces, describing the size of the stones on the $i$-th pile starting with the lowest stone.

Limits

There are $T=100$ test cases. In each testcase we have:

• $1 \le N \le 1000$,
• $2\le K\le 10$,
• $1\le M\le 10000$.

Example

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

Case #0:
2 2 1
1 0
Case #1:
2 0 1
2 3 2
1 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 number contains the number of test cases $T$. The $T$ test cases follow in the following format:

The first line of each test case contains two numbers $N,K$ which represent the number of stones and the number of stable patches (including the one the stones are currently lying on). The next line describes the order of stones on the first pile. There are $N$ numbers, separated by spaces, $s_{0},s_{1},{\dots},s_{N-1}$ where $0 \le s_i\le N-1$ indicating the size of the $i$-th stone on the first pile from the bottom to the top (that is, $s_{0}$ is the size of the bottom most stone and $s_{N-1}$ is the size of the stone on top of the pile).

It is guaranteed that every stone size from $0$ to $N-1$ appears exactly once, in particular, the stones on pile $0$ form a permutation of the numbers from $0$ to $N-1$.

Output

For the $t$-th test case, on the first line print “Case #t: M” where $M$ is the number of moves you make to build the pyramid on pile $0$. This should be followed by $M$ lines, each containing two numbers $a$ and $b$ such that $0\le a,b \le N-1$ indicating you move the top stone from pile $a$ to pile $b$.

The moves you output must result in a pyramid on pile $0$ for your program to get points on this subtask.

Limits

There are $T=100$ test cases. In each testcase we have:

• $1 \le N \le 10$,
• $K=3$.
• $M\le 27\,000$: Your solution must use at most 27000 moves.

Example

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

Case #0: 6
0 1
0 2
0 2
1 0
2 0
2 0
Case #1: 9
0 1
0 1
0 2
0 1
2 0
1 2
1 0
2 0
1 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

Same as Subtask 2

Output

Same as Subtask 2

Limits

There are $T=100$ test cases. In each testcase we have:

• $1\le N \le 500$,
• $K=3$.
• $M\le 27\,000$: Your solution must use at most 27000 moves.

Scoring

If you need $4500$ or less moves you get 30 points. If you use more than $4500$ moves, the number of points you get will be

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 2

Output

Same as Subtask 2

Limits

There are $T=100$ test cases. In each testcase we have:

• $1 \le N \le 500$,
• $K=5$.
• $M\le 27\,000$: Your solution must use at most 27000 moves.

Scoring

If you need $2500$ or less moves you get 40 points. If you use more than $2500$ moves, the number of points you get will be

Example

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

Case #0: 10
0 1
0 2
0 2
0 3
0 3
1 0
3 0
3 0
2 0
2 0
Case #1: 12
0 1
0 2
0 3
0 4
0 1
0 3
4 0
3 0
3 0
1 0
1 0
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 of the following format:

• The first line contains three integers $N$ — the number of junctions, $M$ — the number of canals, and $K$ — the number of junctions that are water sources.
• The next $M$ lines contain two junction numbers each, denoting two junctions connected by a canal. The junctions are numbered from $0$ to $N-1$.
• The next line contains $K$ distinct junction numbers that are water sources.

Output

For the $t$-th test case, output a line containing “Case #t:”, followed by two integers $S$ and $P$: the number of junctions that you have managed to connect to at least one water source through the canals (directly or indirectly), and the number of improvements that you have made to do so. In the $i$-th of the following $P$ lines, print three integers $a_i$, $b_i$, and $c_i$: the number of the pivot junction, the number of the junction that the canal being destroyed connects the pivot junction to, and the number of the junction that the canal being built connects the pivot junction to.

In case there are multiple solutions that lead to the maximum amount of junctions connected to at least one water source, you may output any such solution.

Limits

• $T=100$.
• $1 \le N \le 3$.
• $0 \le M \le N-1$.
• $K=1$.

Example

1
3 1 1
0 2
1

Case #0: 2 1
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.

Limits

• $T=100$.
• $1 \le N \le 7$.
• $0 \le M \le N-1$.
• $K=1$.

Example

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

Case #0: 2 1
0 2 1
Case #1: 4 2
2 1 5
4 3 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$.
• $1 \le N \le 100$.
• $0 \le M \le N-1$.
• $K=1$.

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$.
• $1 \le N \le 100$.
• $0 \le M \le N-1$.
• $1 \le K \le N$.
• There is no sequence of canals connecting one water source to another.

Example

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

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

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$.
• $1 \le N \le 100$.
• $0 \le M \le N-1$.
• $1 \le K \le N$.

Example

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

Case #0: 2 1
0 2 1
Case #1: 4 2
2 1 5
4 3 0
Case #2: 5 1
2 3 1
Case #3: 5 2
0 1 2
4 5 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

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

Output

For the $i$-th test case, output a line “Case #i: YES” if it’s possible to send the donkeys from $A$ to $B$ or “Case #i: NO” if not.

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le N \le 100$
• $0 \le a \le 100$
• $b = 0$
• $0 \le d_i \le 100$ for all $0 \le i \le N-1$.

Example

3
1 3 0
5
1 3 0
6
3 4 0
4 5 4

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

A           O
W-----------+-----------
v<= <= <= <=| donkey 1
|=>v        | d_1=5
|--W--------|-----------
|  v<= <= <=| donkey 2
|   =>v     | d_2=4
|-----W-----|-----------
|     v<= <=| donkey 2
|      => =>v d_0=4
+-----------W-----------

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

Same as subtask 1, except that for $b$ we have $0 \le b \le 100$.

Example

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

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

5  4  3  2  1  0 ... 9
+--------------|         d0=6
+-->           |
   +-----------|         d1=5
   +-->        |
      +--------|         d3=4
      +-->     |
         +-----|         d2=4
         +---->|
               |--...->  d4=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

Output

For the $i$-th test case, output a line “Case #i: b”, where $b$ is the largest possible distance such that it there exists a trade route from A to B and back.

Your answer is accepted if the absolute error is below $10^{-6}$. In other words, if your output is $x$ and the correct solution is $y$, your output is correct if and only if $|x-y| \le 10^{-6}$.

Limits

There are $T=100$ test cases. In each test case we have:

• $1 \le N \le 100$
• $0 \le d_i \le 100$ for all $0 \le i \le N-1$.

Example

3
1
5
2
3 3
16
7 6 6 5 1 4 3 1 1 1 1 1 1 1 1 4

Case #0: 2.5
Case #1: 2.25
Case #2: 6.2812347

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