XXVIII Spain Olympiad in Informatics, Online Qualifier
Statement is not available in English language
B. Beauty
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We define the beauty of a list of $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ as the sum of the terms with odd indices minus the sum of the terms with even indices, that is, $$$a_1 - a_2 + a_3 - \ldots + (-1)^{n+1}a_n = \sum_{i=1}^n (-1)^{i+1}a_i$$$.

You are given a list of $$$n$$$ numbers and an integer $$$k$$$, and you must determine the maximum beauty you can obtain after performing the following operation exactly $$$k$$$ times: you choose two different indices $$$1 \leq i \lt j \leq n$$$ and exchange the values of $$$a_i$$$ and $$$a_j$$$.

Input

The input begins with a number $$$T$$$ — the number of test cases.

Each test case starts with a line with two integers $$$n$$$ and $$$k$$$: the length of the list and the number of exchanges to be performed.

Next, there is a line with $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

Output

For each test case, you must print a line with the maximum beauty that can be obtained by performing exactly $$$k$$$ exchanges.

Scoring
  1. (17 points) $$$k = 0$$$.
  2. (20 points) $$$n = 2$$$.
  3. (24 points) $$$n \leq 100$$$.
  4. (39 points) No additional restrictions.
Example
Input
4
5 1
1 4 2 3 7
2 1
1 2
2 2
1 2
9 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
Output
9
1
-1
5000000000
Note

$$$1 \leq T \leq 2000$$$.

$$$2 \leq n \leq 2 \cdot 10^5$$$.

The sum of $$$n$$$ for all cases is at most $$$2 \cdot 10^5$$$.

$$$0 \leq k \leq 10^9$$$.

$$$0 \leq a_i \leq 10^9$$$ for all $$$i = 1, \ldots, n$$$.

C. Equipartition
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Herminia wants to divide her lands among her four children. Herminia's estate consists of $$$n$$$ possessions, the $$$i$$$-th of which is located at the point $$$(x_i, y_i)$$$ in the plane (where $$$x_i$$$, $$$y_i$$$ are integer coordinates) and has a value $$$v_i$$$.

Herminia will divide her lands as follows: she will choose a point $$$(a, b)$$$ and give each child the possessions contained in one of the four quadrants defined by the point. That is:

  • One of the children will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \leq a$$$ and $$$y \leq b$$$.
  • Another will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \gt a$$$ and $$$y \leq b$$$.
  • Another will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \leq a$$$ and $$$y \gt b$$$.
  • The last child will receive the possessions with coordinates $$$(x, y)$$$ such that $$$x \gt a$$$ and $$$y \gt b$$$.

Herminia wants each child to receive the same total value in possessions. Help Herminia find the number of points $$$(a, b)$$$ with integer coordinates such that the sum of the values of the possessions in each of the quadrants is equal.

Input

The input begins with a number $$$T$$$ — the number of test cases.

Each test case starts with a line with an integer $$$n$$$, the number of possessions. Next, there are $$$n$$$ lines, the $$$i$$$-th of which has three integers $$$x_i$$$, $$$y_i$$$, and $$$v_i$$$: the coordinates and the value of the $$$i$$$-th possession.

Output

For each test case, your program should print a line with the number of points with integer coordinates $$$(a, b)$$$ such that the values of the possessions in each of the four quadrants defined by those points add up to the same total.

Scoring
  1. (17 points) $$$n = 4$$$.
  2. (23 points) $$$n \leq 30$$$.
  3. (19 points) $$$n \leq 500$$$.
  4. (21 points) $$$0 \leq x_i, y_i \lt \min(3\cdot 10^4, n)$$$, $$$v_i = 1$$$ for all $$$i = 1, \ldots, n$$$.
  5. (20 points) No additional restrictions.
Example
Input
3
5
-1 -2 1
3 4 2
2 -5 2
-2 -1 1
-4 3 2
1
0 0 1
4
-1000000000 -1000000000 1
1000000000 -1000000000 1
-1000000000 1000000000 1
1000000000 1000000000 1
Output
12
0
4000000000000000000
Note

$$$1 \leq T \leq 1000$$$.

$$$1 \leq n \leq 2 \cdot 10^5$$$.

The sum of $$$n$$$ for all cases will be at most $$$2 \cdot 10^5$$$.

$$$-10^9 \leq x_i, y_i \leq 10^9$$$.

There are no repeated pairs $$$(x_i, y_i)$$$.

$$$1 \leq v_i \leq 10^9$$$.

D. Changes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two lists $$$X = (x_1, \ldots, x_n)$$$ and $$$Y = (y_1, \ldots, y_n)$$$ of $$$n$$$ integers, we say that $$$X$$$ is dominated by $$$Y$$$ if $$$x_i \leq y_i$$$ for all $$$i = 1, 2, \ldots, n$$$. We say that $$$X$$$ is dominated by a reordering of $$$Y$$$ if $$$Y$$$ can be rearranged in such a way that $$$X$$$ is dominated by $$$Y$$$: formally, if there exists a permutation $$$\sigma$$$ such that $$$x_i \leq y_{\sigma(i)}$$$ for all $$$i = 1, 2, \ldots, n$$$.

Three lists $$$A$$$, $$$B$$$, $$$C$$$ of $$$n$$$ integers are given. The following operation can be performed: exchange the element $$$a_i$$$ with the element $$$b_i$$$, for $$$1 \leq i \leq n$$$.

Find the minimum number of operations necessary so that, after performing the operations, $$$A$$$ is dominated by a reordering of $$$C$$$. If this is not possible, print $$$-1$$$.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

Each case begins with a line containing $$$n$$$, the size of the lists $$$A$$$, $$$B$$$, and $$$C$$$.

The next line of each case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

The next line of each case contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$.

The next line of each case contains $$$n$$$ integers $$$c_1, \ldots, c_n$$$.

Output

For each case, print an integer, the minimum number of operations or $$$-1$$$ if it is not possible to make $$$A$$$ dominated by a reordering of $$$C$$$.

Scoring
  1. (22 points) $$$a_i, b_i, c_i \le 2$$$ for all $$$1 \leq i \leq n$$$.
  2. (23 points) $$$b_i = a_i - 1$$$ for all $$$1 \leq i \leq n$$$.
  3. (24 points) The sum of $$$n$$$ over all cases will be less than or equal to $$$10^3$$$.
  4. (31 points) Without additional restrictions.
Example
Input
3
3
1 2 3
3 3 3
1 2 2
3
1 3 2
1 1 1
2 1 1
2
2 3
4 3
4 2
Output
-1
1
0
Note

$$$1 \le T \le 10^5$$$.

$$$1 \le n \le 10^5$$$.

The sum of $$$n$$$ over all cases will be less than or equal to $$$10^5$$$.

$$$1 \le a_i, b_i, c_i \le 10^9$$$.

E. To Play or Not to Play, That is the Question
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Huize and Jacobo are playing a conquest video game. In the game, there are $$$N$$$ cities and $$$M$$$ bidirectional roads between pairs of cities. Initially, Huize occupies $$$H$$$ cities, and Jacobo occupies $$$J$$$ cities with some soldiers. They have already placed the soldiers, and now it's time to see who wins. The soldiers can be divided into any number of groups and march through all the roads incident to the cities they occupy. Each city is conquered by the first group of soldiers that reaches the city. If multiple groups arrive at the same time, Jacobo's soldiers will conquer the city. Once a city is conquered, the opponent cannot enter it.

The roads can have different lengths, so each road is specifically associated with the travel time between cities. Additionally, some roads are blocked and require a code to open, which can be obtained in exactly one city (not necessarily one of the cities at the ends of the road). The player who conquers that city can use the road from the moment they conquer the city, and the other player cannot use it.

The objective of this game is to occupy more cities than the opponent. Jacobo, who wants to spend more time with his daughter, is only willing to play if he knows he will win. Help Jacobo: if Jacobo is going to win, print two lines, the first with the text "La hora de juego" (without quotes), and the second with the difference between the number of cities Jacobo will occupy and the number of cities Huize will occupy. If Jacobo is going to tie or lose, print in a single line "Hasta luego Huize, es la hora de Olivia" (without quotes).

Input

The input begins with an integer $$$T$$$, the number of test cases.

Each case begins with two integers on a line: $$$N$$$, $$$M$$$.

The following $$$M$$$ lines contain four integers each: $$$u_i$$$, $$$v_i$$$, $$$w_i$$$, $$$c_i$$$, indicating that there is a road connecting cities $$$u_i$$$ and $$$v_i$$$, it takes $$$w_i$$$ minutes to travel, and the secret code is located in city $$$c_i$$$ (if $$$c_i = 0$$$, no code is needed to travel).

The next line contains an integer $$$H$$$.

In the following line, there are $$$H$$$ integers $$$h_i$$$, representing the cities initially occupied by Huize.

The next line contains an integer $$$J$$$.

In the following line, there are $$$J$$$ integers $$$j_i$$$, representing the cities initially occupied by Jacobo.

Output

For each test case, if Jacobo is going to win, write "La hora de juego" and, on a new line, how many more cities than Huize he will occupy. Otherwise, write "Hasta luego Huize, es la hora de Olivia" on a single line.

Scoring
  1. (13 points) $$$M = N-1$$$ and for all $$$1 \leq i \lt N$$$, $$$u_i = i$$$ and $$$v_i = i+1$$$; in other words, the cities form a path. Also, $$$H = J = 1$$$, $$$2 \leq N$$$, and Jacobo and Huize will occupy the two ends of the path.
  2. (9 points) There is no path that requires a code.
  3. (14 points) $$$w_i = 1$$$ for all $$$1 \leq i \leq M$$$.
  4. (24 points) $$$1 \leq N, M \leq 2000$$$, $$$1 \leq T \leq 100$$$, the sum of $$$N$$$ in all cases is less than $$$2000$$$, and the sum of $$$M$$$ in all cases is less than $$$2000$$$.
  5. (21 points) $$$M = N-1$$$ and for all $$$1 \leq i \lt N$$$, $$$u_i = i$$$ and $$$v_i = i+1$$$; in other words, the cities form a path.
  6. (19 points) No additional restrictions.
Example
Input
3
7 8
1 2 2 0
1 4 1 0
2 4 1 1
2 3 1 1
3 7 3 7
3 5 1 6
7 6 3 0
6 5 100 6
2
7 4
1
1
7 8
1 2 2 0
1 4 1 0
2 4 1 1
2 3 1 1
3 7 3 7
3 5 1 3
7 6 3 0
6 5 100 6
2
7 4
1
1
5 4
3 1 116 3
1 4 14 4
4 2 100 2
2 5 2 0
1
3
1
5
Output
Hasta luego Huize, es la hora de Olivia
La hora de juego
1
La hora de juego
3
Note

$$$1 \leq H, J, h_i, j_i, c_i \leq N \leq 2 \times 10^5$$$, $$$H+J \leq N$$$.

$$$0 \leq M \leq \min\left(\frac{N \cdot (N-1)}{2}, 2 \times 10^5\right)$$$.

$$$1 \leq w_i \leq 10^9$$$.

$$$1 \leq T \leq 10000$$$; The sum of $$$N$$$ in all cases is less than $$$2 \times 10^5$$$; The sum of $$$M$$$ in all cases is less than $$$2 \times 10^5$$$.

F. Erdős-Straus Conjecture
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given that IOI 2023 was in Hungary and IOI 2024 will be in Egypt, what better than a problem about a conjecture of Hungarian mathematicians about Egyptian fractions!

The Erdős-Straus conjecture states that for every integer $$$n \geq 2$$$, there exist positive integers $$$x$$$, $$$y$$$, $$$z$$$ such that

$$$$$$\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}.$$$$$$

Since this problem is very difficult, you are asked to solve a variant in which $$$z=xy$$$. That is, given $$$n \geq 1$$$, you must find a pair of positive integers $$$x$$$, $$$y$$$ such that

$$$$$$\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{xy}$$$$$$

if they exist.

Input

The input begins with an integer $$$T$$$, the number of test cases. Then follow $$$T$$$ lines, each with an integer $$$n$$$.

Output

For each test case, you should print a line with the two positive integers $$$x$$$, $$$y$$$ separated by spaces, or with a single $$$0$$$ in case those numbers do not exist. If there are multiple valid pairs of integers $$$x$$$, $$$y$$$, you can print any of them.

Scoring
  1. (8 points) $$$n \leq 10$$$.
  2. (7 points) $$$n \leq 100$$$.
  3. (10 points) The sum of $$$n$$$ for all cases is at most $$$5 \cdot 10^6$$$.
  4. (20 points) $$$n$$$ is even.
  5. (55 points) No additional constraints.
Example
Input
4
2
1
5
6
Output
2 1
0
2 5
3 4
Note

$$$1 \leq T \leq 100$$$. $$$1 \leq n \leq 10^9$$$.