XXIV Spain Olympiad in Informatics, Online Qualifier 2
A. No More Ties!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the first contest, there was a problem: 7 contestants were classified, and there was a tie in scores among 14 participants in the seventh position! The organizers do not like having to break ties based on accumulated time, but with so many contestants tied, we had no other option.

Now we want to know if this will happen in the second qualifying round. In this qualifying round, $$$n$$$ contestants will participate, and the top $$$k$$$ will be classified, with $$$1 \leq k \lt n$$$. We have the $$$n$$$ scores of the participants, and we want to know if there will be ties in scores that prevent us from separating the top $$$k$$$ participants from the others without having to resort to penalty time.

Input

The input starts with an integer $$$t$$$ indicating the number of cases.

Each case begins with a pair of integers $$$n$$$ and $$$k$$$, with $$$1 \leq k \lt n$$$.

The following line contains $$$n$$$ integers indicating the scores of the participants, $$$p_i$$$.

Output

For each case, output "EMPATE" or "BIEN" depending on whether there are ties that prevent separating the top $$$k$$$ contestants from the others without looking at the penalty time.

Scoring

$$$1 \leq t \leq 100$$$

$$$0 \leq p_i \leq 10^6$$$

$$$1 \leq k \lt n$$$

33 Points: $$$n \leq 100$$$

33 Points: $$$n \leq 1000$$$

34 Points: $$$n \leq 10000$$$

Example
Input
5
2 1
1 1
10 5
5 8 0 9 2 0 3 0 1 1
5 1
8 13 10 14 1
3 1
0 1 1
10 8
5 7 4 2 3 2 2 7 7 3
Output
EMPATE
BIEN
BIEN
EMPATE
EMPATE

B. Dividing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ integers, is there any one of them that divides all the others?

Input

The input starts with an integer $$$t$$$ indicating the number of test cases.

Each test case begins with an integer $$$n$$$ followed by $$$n$$$ integers $$$a_i$$$.

Output

For each test case, output "SI" or "NO" depending on whether the indicated integer exists or not.

Scoring

$$$1 \leq t \leq 100$$$

$$$1 \leq a_i \leq 10^9$$$

$$$2 \leq n$$$

14 Points: $$$n = 2$$$

43 Points: $$$n \leq 100$$$

43 Points: $$$n \leq 10000$$$

Example
Input
4
2
10 18
6
2 7 3 7 8 7
6
4 6 1 3 4 1
6
4 2 4 6 8 4
Output
NO
NO
SI
SI

C. Games with Queta
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In 2005, with the aim of promoting and encouraging the use of Catalan in the daily lives of Catalans, the Generalitat of Catalonia created a campaign called "Dóna corda al Català". This campaign had a mascot, Queta, which was a mouth with legs that, when wound up, would move forward by opening and closing its mouth.

Fifteen years later, the Generalitat no longer has space to store more materials from past campaigns, so they have decided to sell all the remaining Quetas they had to an English family that is involved in illegal betting.

They have created a game to make money from the bets. The game consists of the following:

A line is drawn on the ground, and two marks are made on this line. $$$n$$$ Quetas are placed on the line between the two marks, all in different positions, with each Queta facing one of the two marks. They are wound up and start running at the same speed. When two Quetas collide head-on, both are destroyed. The game ends when there are no Quetas left between the two marks. The objective of the game is to guess how many Quetas will remain at the end of the game.

Given the positions of the marks and the Quetas at the start of the game, determine how many Quetas will remain at the end.

Input

The input begins with an integer $$$t$$$ indicating the number of cases.

Each case starts with an integer $$$n$$$ and two integers $$$m_1$$$ and $$$m_2$$$, with $$$m_1 \lt m_2$$$, indicating the two marks.

The second line contains $$$n$$$ integers $$$q_i$$$ with $$$m_1 \lt q_i \lt m_2$$$, indicating the initial positions of the Quetas.

The third line contains $$$n$$$ integers $$$d_i$$$, where if $$$d_i = 1$$$, the i-th Queta is pointing to mark 1, and if $$$d_i = 2$$$, it is pointing to mark 2.

Output

For each case, write a line with the answer.

Scoring

$$$1 \leq t \leq 100$$$

13 Points: All $$$d_i$$$ are the same.

24 Points: $$$1 \leq n \leq 100$$$, $$$1 \leq m_i \leq 200$$$

25 Points: $$$1 \leq n \leq 1000$$$, $$$1 \leq m_i \leq 2000$$$

26 Points: $$$1 \leq n \leq 10000$$$, $$$1 \leq m_i \leq 20000$$$

12 Points: $$$1 \leq n \leq 10000$$$, $$$1 \leq m_i \leq 10^9$$$

Example
Input
4
6 2 16
14 4 11 8 6 9
1 1 2 1 1 2
6 1 20
14 4 5 9 7 10
2 2 1 2 2 2
5 1 19
11 16 8 7 4
2 1 1 2 2
4 1 20
3 15 10 12
1 1 1 1
Output
4
4
1
4
Note

For the first case, initially, the positions of the Quetas are as follows:

After some time, the Quetas that were originally in positions 11 and 14 collide and are destroyed:

The remaining Quetas manage to reach the marks safe and sound.

D. Coins 3
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pedro has $$$n$$$ coins, each with a value $$$m_i$$$. Pedro wants to pay exactly $$$k$$$ euros to the shopkeeper; to do this, he follows the following algorithm:

  • Sort the coins from highest to lowest value.
  • He takes out the coins in the specified order.
  • Each time he takes out a coin, he does the following: if the value is less than or equal to what he still needs to pay, he gives the coin to the shopkeeper; if it is greater, he keeps it in his pocket.

This algorithm does not always work, and sometimes Pedro cannot manage to pay $$$k$$$ euros. He believes it is because he is missing coins, which is why he asks you for money.

Knowing what coins Pedro has, the amount he wants to pay, and the algorithm he uses to pay, what is the minimum amount of euros you need to give him so that he can pay? You can give it to him in more than one coin.

Input

The input starts with an integer $$$t$$$ indicating the number of cases.

Each case consists of two integers $$$n$$$ and $$$k$$$, followed by a line with $$$n$$$ integers $$$m_i$$$.

Output

For each case, write a line with the answer.

Scoring

$$$1 \leq t \leq 100$$$

33 Points: $$$1 \leq n,k,m_i \leq 100$$$

33 Points: $$$1 \leq n \leq 10^3$$$, $$$1 \leq m_i \leq 10^4$$$, $$$1 \leq k \leq 10^7$$$

34 Points: $$$1 \leq n \leq 10^4$$$, $$$1 \leq m_i \leq 10^9$$$, $$$1 \leq k \leq 10^{13}$$$

Example
Input
5
6 74
49 3 13 61 13 4
10 22
62 9 10 30 50 56 7 11 1 42
3 32
38 53 68
5 18
45 14 69 57 5
3 82
41 51 33
Output
0
0
32
4
31

E. Separated Cells
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The prison of Nlogonia has been recently remodeled. It has $$$n$$$ cells, each with the capacity for a single inmate. Some cells are connected to each other in such a way that it is possible to go from any cell to any other in a unique way (without revisiting cells). In other words, the graph of the cells and their connections is a tree. Three very dangerous inmates have arrived at the prison and need to be assigned to different cells with one restriction: no two of them can be in connected cells, as they could devise a plan to escape. Count the number of ways to select their 3 cells while satisfying the restriction.

Note: The permutations of cells count only once (1, 2, 3 and 2, 3, 1 are considered the same). Two ways are considered distinct if any of the cells is different.

Input

Each case starts with an integer $$$t$$$, the number of cases. Each of the $$$t$$$ cases starts with an integer $$$n$$$, the number of cells in the prison. This is followed by $$$n-1$$$ lines, each with a pair of integers $$$u, v$$$ indicating that cells $$$u$$$ and $$$v$$$ are connected.

Output

For each case, print a single integer, the number of ways to select the 3 cells while satisfying the restriction.

Scoring

For all cases, it holds that $$$n \geq 3$$$, $$$0 \leq u, v \leq n-1$$$, and $$$t \leq 40$$$.

13 Points: $$$n \leq 20$$$

26 Points: $$$n \leq 300$$$

14 Points: $$$n \leq 2000$$$

11 Points: $$$n \leq 100000$$$ and the edges are of the form $$$(i, i+1)$$$, $$$0 \leq i \leq n-2$$$

6 Points: $$$n \leq 100000$$$ and the edges are of the form $$$(0, i)$$$, $$$1 \leq i \leq n-1$$$

30 Points: $$$n \leq 100000$$$

Example
Input
3
5
0 1
1 2
2 3
3 4
5
0 1
0 2
0 3
3 4
7
0 1
0 2
1 3
1 4
2 5
2 6
Output
1
2
12

F. Painting Squares
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Aniol has a grid of white squares with dimensions $$$n \times m$$$. He can paint some of these squares black, but he can only perform two types of operations to paint the squares: paint an entire row black or paint an entire column black.

His three little cousins want to play a game. Each of them, including Aniol, thinks of an integer $$$a_i$$$, between $$$2$$$ and $$$2^{15}$$$. They then calculate $$$k = a_1 \cdot a_2 \cdot a_3 \cdot a_4$$$. Aniol wins if he can ensure that exactly $$$k$$$ white squares remain by only using the previous operations.

Input

The input starts with an integer $$$t$$$ indicating the number of test cases.

Each case consists of three integers $$$n$$$, $$$m$$$, and $$$k$$$.

Output

For each case, write a line with "SI" if it is possible to achieve this or "NO" otherwise. In both cases, you must write the answer without quotes.

Scoring

$$$1 \leq t \leq 30000$$$

$$$8 \leq k \leq n \cdot m$$$

$$$k = a_1 \cdot a_2 \cdot a_3 \cdot a_4$$$ with $$$2 \leq a_i \leq 2^{15}$$$

4 Points: $$$1 \leq n,m \leq 2^{c}$$$

There are 25 test files, each test file gives 4 points. For each file, $$$c$$$ takes a different value, ranging from 6 to 30.

Example
Input
3
2 50 81
29 22 546
27 13 168
Output
NO
SI
SI