XXIV Spain Olympiad in Informatics, Day 2
A. Baq and the Distances Between Cities
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baq works for a mobility company in a country with $$$n$$$ cities. His job consists of programming Dijkstra's algorithm to find the shortest distance between two cities through a network of roads, which is modeled as an undirected graph. Unfortunately, Baq's code has many bugs.

Baq thinks it would be much easier if the minimum distance between two cities were equal to the length of the road that connects them. To avoid worrying about whether there is a direct road between two cities, Baq imagines a network of roads where there is a direct road between every pair of cities, that is, a *complete graph*. Additionally, Baq thinks it would look nice if the lengths of the $$$\frac{n(n-1)}{2}$$$ roads were $$$1, 2, \ldots, \frac{n(n-1)}{2}$$$ in some order.

Can you help Baq design his ideal road plan? That is, a network of roads with roads between each pair of cities, such that the lengths of the roads are a permutation of $$$1, 2, \ldots, \frac{n(n-1)}{2}$$$ and that for every pair of cities, the minimum distance between them is equal to the length of the road that connects them.

Baq can settle for not all pairs of cities satisfying the property, but in that case, he will not give you the full $$$100$$$ points for the problem.

Input

A positive integer $$$n$$$, the number of cities.

Output

For each case, write $$$n-1$$$ lines. In the $$$i$$$-th line, write $$$n-i$$$ integers: the $$$j$$$-th integer should be the length of the road between the $$$i$$$-th city and the $$$(i+j)$$$-th city. Each number between $$$1$$$ and $$$\frac{n(n-1)}{2}$$$ must be written exactly once.

Scoring

There are $$$50$$$ cases, with $$$n$$$ between $$$3$$$ and $$$52$$$. Each one is worth $$$2$$$ points.

Let $$$P$$$ be the number of pairs of vertices $$$u, v$$$ in the graph generated by your program such that the minimum distance between $$$u$$$ and $$$v$$$ is equal to the weight of the edge from $$$u$$$ to $$$v$$$. If $$$P = \frac{n(n-1)}{2}$$$, then your submission receives the $$$2$$$ points for that case. If not, your submission receives $$$\frac{3P}{n(n-1)}$$$ points for that case.

Example
Input
5
Output
1 2 4 9
3 5 8
6 10
7

B. Expensive Transport
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Barcelona, a new anti-Baq tax has been approved. This tax means that every time Baq moves using public transport, he has to pay not only the cost of going from one stop to the next at each stop but also the total cost of the journey he has already made from the origin to the current stop (defined as the sum of the "normal" costs of each transport between stops, not what Baq has actually paid).

For example, if he makes a journey of five stops (let's say $$$A, B, C, D, E$$$) and the costs of the journeys between stops are $$$AB = 1, BC = 2, CD = 1, DE = 3$$$, then the total cost for Baq will be $$$15$$$: at $$$A$$$ he will pay $$$1$$$ to go to $$$B$$$; at $$$B$$$ he will pay $$$2$$$ to go to $$$C$$$ plus $$$1$$$, which is the cost of the journey $$$AB$$$; at $$$C$$$ he will pay $$$1$$$ to go to $$$D$$$ plus $$$3$$$, which is the cost of the journey $$$ABC$$$ ($$$1+2$$$); at $$$D$$$ he will pay $$$3$$$ to go to $$$E$$$ plus $$$4$$$, which is the cost of the journey $$$ABCD$$$ ($$$1+2+1$$$).

Baq does not like this tax, but he will not give up the transport service. Baq asks you to help him find the minimum cost of a journey between stop $$$0$$$ and each of the other $$$n-1$$$ stops.

Input

The input starts with an integer $$$T$$$, the number of cases. Each case begins with two integers $$$n$$$ and $$$m$$$, the number of stops and the number of connections between stops. This is followed by $$$m$$$ lines with three integers $$$u_i, v_i, w_i$$$, indicating that there is a connection from stop $$$u_i$$$ to stop $$$v_i$$$ with a price of $$$w_i$$$. The stops are numbered from $$$0$$$ to $$$n-1$$$. The connections between stops are directed, meaning that the connection from $$$u$$$ to $$$v$$$ is not the same as the connection from $$$v$$$ to $$$u$$$.

Output

For each case, write on a line with $$$n-1$$$ integers, the $$$i$$$-th (starting from $$$1$$$) of which is the cost for Baq of the journey between station $$$0$$$ and station $$$i$$$. If he cannot reach station $$$i$$$, write $$$-1$$$.

Scoring

$$$1 \leq T \leq 100$$$

$$$3 \leq n, m \leq 1000$$$. The sum of $$$n+m$$$ for all cases is less than $$$3 \cdot 10^4$$$.

$$$0 \leq u_i, v_i \leq n-1, 1 \leq w_i \leq 1000$$$

22 points: $$$n \leq 10, m \leq 20$$$, the sum of $$$n+m$$$ for all cases is less than $$$800$$$.

11 points: $$$w_i = 1$$$ for $$$i = 1, \ldots, m$$$

14 points: Each stop is only connected to the previous and the next (cyclically). Formally, $$$m = 2n$$$ and $$$u_{2i} = u_{2i-1} = i-1, v_{2i} = i-2, v_{2i-1} = i$$$ for all $$$i$$$ except edges $$$2$$$ and $$$2n-1$$$, which are $$$u_2 = 0, v_2 = n-1$$$ and $$$u_{2n-1} = n-1, v_{2n-1} = 0$$$.

29 points: $$$n, m \leq 80$$$, the sum of $$$n+m$$$ for all cases is less than $$$2500$$$.

24 points: No additional restrictions.

Example
Input
4
4 4
0 1 1
1 2 1
2 3 1
0 3 5
4 4
0 1 1
1 2 1
2 3 1
0 3 7
5 5
0 1 1
1 2 2
2 4 1
0 3 2
3 4 3
5 6
0 2 7
1 3 9
2 1 3
3 0 1
3 1 1
4 3 4
Output
1 3 5 
1 3 6 
1 4 2 7 
17 7 36 -1 

C. Brothers
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cesc is quietly playing with his $$$n$$$ domino pieces, placing them one behind the other in a vertical position, so that when he pushes the first one, it knocks down other pieces, which in turn knock down more pieces, and so on. His goal is for the first piece to fall and cause the last piece to fall as well.

Each piece has a position $$$p_i$$$ and a height $$$h_i$$$, and it holds that $$$p_i \lt p_{i+1}$$$. The domino pieces follow a simple physical law: when piece $$$i$$$ falls, it knocks down all pieces with $$$j \gt i$$$ that satisfy $$$(p_i + h_i) \gt p_j$$$.

Cesc places the pieces in such a way that he believes he will achieve his goal, although his brothers might remove one piece.

His brother Pep has told him that he believes that, as the pieces are currently placed, he will not achieve his goal.

In the end, his sister Ivet tells them that, as they are now, Cesc will indeed achieve his goal, but if she removes one piece, he will not.

Neither the first nor the last piece can be removed.

Which of the three siblings is correct?

Input

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

Each case starts with an integer $$$n$$$ followed by $$$n$$$ lines with the integers $$$p_i$$$ and $$$h_i$$$.

Output

For each case, write a line with "Cesc", "Pep", or "Ivet" without quotes, depending on which sibling is correct.

Scoring

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

$$$3 \leq n \leq 20000$$$

$$$1 \leq p_i,h_i \leq 10^9$$$

25 Points: $$$n \leq 100$$$

15 Points: $$$p_i,h_i,n \leq 1000$$$

20 Points: $$$n \leq 1000$$$

40 Points: No additional restrictions.

Example
Input
3
5
1 5
3 5
5 5
7 5
9 5
5
1 3
3 4
7 5
8 2
10 1
5
1 5
2 5
6 6
7 5
8 3
Output
Cesc
Pep
Ivet

D. Jordan's Castles
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jordan has recently received a game that contains many cubic-shaped blocks. By stacking them, he can build towers of great height, and by placing the towers next to each other, he can create what he calls castles. However, he only likes castles that satisfy the condition that the number of blocks in a tower is always less than or equal to that of the tower immediately to its left. Additionally, he likes to describe these castles with a sequence of integers $$$(a_i)$$$ such that each $$$a_i$$$ corresponds to the number of blocks in the $$$i$$$-th tower. After playing with this type of castle, he has realized that he can also describe them with a sequence $$$(b_i)$$$ such that each $$$b_i$$$ corresponds to the number of blocks on the $$$i$$$-th floor of the castles. Thus, for the castle:

XX

XX

the sequence $$$(a_i)$$$ would be $$$a_1 = 3, a_2 = 2$$$ and the sequence $$$(b_i)$$$ would be $$$b_1 = 2, b_2 = 2, b_3 = 1$$$.

Jordan says that a castle is pretty if the two sequences match, as happens with the castle:

XXX

Given a castle described by the sequence $$$(a_i)$$$, determine the minimum number of blocks that need to be removed to convert it into a pretty castle.

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 towers in the castle. Following this, there are $$$n$$$ integers $$$(a_i)$$$ on one line, representing the number of blocks in each of the $$$n$$$ towers.

Output

For each case, print a single integer, the minimum number of blocks that need to be removed for the castle to be pretty.

Scoring

$$$t \leq 40$$$, $$$n \leq 100000$$$, $$$a_i \geq a_{i+1}$$$ and $$$a_i \leq 10^9$$$.

12 points: $$$n \leq 8$$$, $$$a_i \leq 8$$$.

19 points: $$$n \leq 1000$$$, $$$a_i \leq 1000$$$.

31 points: $$$a_i \leq 100000$$$.

38 points: No additional restrictions.

Example
Input
3
3
5 2 1
2
3 2
4
8 4 2 1
Output
2
1
5

E. Game on a Graph
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ana and Baq are playing a game. The game consists of the following: initially, there is a graph $$$G$$$ that is not necessarily connected, with its $$$n$$$ vertices numbered from $$$0$$$ to $$$n-1$$$. One of the vertices is marked as the *winning vertex*. The players take turns (starting with Ana), and on each turn, the player selects a connected component of the graph and removes the vertex with the smallest number from the component (also removing all edges incident to it). The first player to remove the winning vertex wins.

Given the graph $$$G$$$, Ana wonders which vertices she can win with (even if Baq plays optimally) if they are marked as winners.

Input

The input begins with the number of cases $$$T$$$. This is followed by $$$T$$$ cases, each describing the graph $$$G$$$ with a line containing the integers $$$n$$$, $$$m$$$, followed by $$$m$$$ lines, each with two integers $$$u, v$$$, indicating that there is an edge between vertices $$$u$$$ and $$$v$$$.

Output

For each case, write in one line the numbers of the vertices for which Ana wins, sorted in ascending order.

Scoring

$$$1 \leq T \leq 100$$$, $$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$. The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^6$$$.

9 points: $$$n \leq 10, m \leq 20$$$, sum of $$$n+m$$$ for all cases less than $$$700$$$.

28 points: $$$n \leq 1000, m \leq 1000$$$, sum of $$$n+m$$$ for all cases less than $$$25000$$$.

8 points: $$$G$$$ is a tree (connected graph without cycles) that has the property that a path from node $$$0$$$ to any other node visits nodes in ascending order of numbers.

25 points: $$$G$$$ is a path (tree with only two vertices of degree 1).

30 points: No additional restrictions.

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