Rogelio has a board of dimensions $$$n \times m$$$, with $$$n \leq 3$$$. The board is very ugly, and he wants to cover it. To cover it, he has three types of pieces:
The pieces can be rotated and flipped in any direction. Rogelio wants to cover the board with the pieces but under the following conditions: the board must be completely covered, there cannot be more than one piece covering the same point on the board, all pieces must be completely within the board, and the total cost must be minimized.
For example, here are three different ways to cover a $$$3 \times 5$$$ board. The one on the right has the minimum possible cost.
The input starts with an integer $$$t$$$ indicating the number of cases.
Each case consists of a line with the integers $$$n$$$ and $$$m$$$.
For each case, write a line with the minimum price that needs to be paid.
$$$1 \leq t \leq 10^4$$$
$$$1 \leq n \leq 3$$$
$$$1 \leq m \leq 10^6$$$
11 Points: $$$1 \leq n,m \leq 3$$$
11 Points: $$$n = 1$$$ and $$$m$$$ is a multiple of $$$3$$$
11 Points: $$$n = 1$$$
11 Points: $$$n = 2$$$ and $$$m$$$ is a multiple of $$$3$$$
11 Points: $$$n = 2$$$
11 Points: $$$n = 3$$$ and $$$m$$$ is a multiple of $$$3$$$
11 Points: $$$n = 3$$$
23 Points: No additional restrictions
3 1 3 2 4 3 5
1 4 5
Arturo and Benito are competing in a programming contest consisting of $$$N$$$ problems. For each problem, they earn a number of points. The winner of each problem is the one who scores more points. Additionally, there are never ties because Arturo always scores an even number of points and Benito an odd number. We know the $$$N$$$ numbers of points that Arturo has scored on the problems $$$(a_i)$$$ and the $$$N$$$ numbers of points that Benito has scored $$$(b_i)$$$, but we do not know which score corresponds to which problem, so it is not possible to determine how many problems each has won. Your goal is to determine the maximum number of problems that Arturo could have won.
Each case starts with an integer $$$t$$$, the number of cases. Each of the $$$t$$$ cases starts with an integer $$$N$$$, the number of problems. This is followed by a line with $$$N$$$ integers $$$a_i$$$ indicating Arturo's points and another line with $$$N$$$ integers $$$b_i$$$ indicating Benito's points.
For each case, print a single integer, the maximum number of problems that Arturo can win.
For all cases, it holds that $$$t \leq 40$$$, $$$1 \leq a_i, b_i \leq 100000$$$, and the $$$a_i$$$ are even and the $$$b_i$$$ are odd.
25 Points: $$$N \leq 10$$$
15 Points: $$$N \leq 100$$$
20 Points: $$$N \leq 1000$$$
40 Points: $$$N \leq 50000$$$
3 3 2 4 6 3 5 7 2 2 2 3 1 5 2 4 8 10 18 5 7 9 11 13
2 1 3
Pedro has $$$n$$$ stones arranged in a row and wants to paint them with $$$c$$$ different colors in such a way that no two consecutive stones are of the same color.
He has already painted some of the stones and now he wonders how many ways he can paint the remaining stones to achieve his goal.
The input starts with a line containing an integer $$$t$$$ indicating the number of cases.
Each case starts with two integers $$$n$$$ and $$$c$$$. The second line of each case contains $$$n$$$ integers $$$x_i$$$ with $$$0 \leq x_i \leq c$$$, where each positive integer represents a color and $$$0$$$ indicates that the stone has not been painted.
The answer can be very large, so write the result modulo $$$10^9+7$$$.
For each case, write a line with the result modulo $$$10^9+7$$$.
$$$1 \leq t \leq 100$$$
11 Points: $$$1 \leq n,c \leq 10$$$, $$$c^n \leq 10^4$$$
20 Points: $$$1 \leq n,c \leq 100$$$
20 Points: $$$1 \leq n,c \leq 1000$$$
32 Points: $$$1 \leq n,c \leq 10^4$$$
17 Points: $$$1 \leq n \leq 10^4$$$, $$$1 \leq c \leq 10^9$$$
4 3 4 1 0 1 3 4 2 0 3 5 6 0 0 1 0 2 4 3 0 1 1 2
3 2 100 0
The Route of the 12 Lakes is a small mountain trail in France, very close to the border with Andorra. It consists of a circular route that can be walked or cycled, where along the way you can see 12 lakes.
Laura wanted to take this route but took the wrong road and ended up on the route of the $$$n$$$ lakes. This route is very similar to the one with 12 lakes but much longer. There are $$$n$$$ lakes, and between the $$$i$$$-th lake and the $$$(i+1)$$$-th lake, there is a path of $$$c_i$$$ kilometers. Between the $$$n$$$-th lake and the first, there is a path of $$$c_n$$$ kilometers.
Since this route is too long, there are different bus lines; each line goes from lake $$$l_1$$$ to lake $$$l_2$$$ via the shortest path (according to the circular route). There is a bus line for each pair of lakes, and each line operates in both directions.
Having gotten confused, Laura has lost her desire to walk. However, she still has the desire to see the area and take photographs, so she has decided to take advantage of the bus lines to enjoy the scenery. She wants to plan a route that meets the following conditions:
Given these conditions, what is the maximum number of kilometers Laura can travel without walking?
The input starts with an integer $$$t$$$ indicating the number of cases.
Each case begins with an integer $$$n$$$, and the following line contains the $$$n$$$ integers $$$c_i$$$.
For each case, write a line with the result.
$$$1 \leq t \leq 100$$$
$$$1 \leq c_i \leq 10^5$$$
8 Points: $$$2 \leq n \leq 7$$$
18 Points: $$$2 \leq n \leq 100$$$
28 Points: $$$2 \leq n \leq 1000$$$
46 Points: $$$2 \leq n \leq 10^4$$$
4 4 1 10 1 1 5 2 4 1 5 3 10 1 1 1 1 1 1 1 1 1 1 2 1 4
20 88 250 2
In Grafolandia, there are $$$n$$$ cities connected by $$$m$$$ bidirectional roads, such that it is possible to reach any city from any other by passing through one or more roads. To reduce traffic, the government has decided to make $$$k$$$ roads one-way, but they want to ensure that it is still possible to reach all other cities from each city.
Help the Grafolandian rulers determine if this is possible, and if so, specify which roads to select and the direction each road should take.
The input begins with the number of cases $$$T$$$. Following this are $$$T$$$ cases, each consisting of a line with the integers $$$n$$$, $$$m$$$, and $$$k$$$, followed by $$$m$$$ lines, each containing two cities $$$u, v$$$, indicating that there is a road between cities $$$u$$$ and $$$v$$$. The cities are numbered from $$$0$$$ to $$$n-1$$$.
If it is not possible, write "NO" (without quotes). If it is possible, write "SI" (without quotes), followed by $$$k$$$ lines. In each of the following $$$k$$$ lines, write two integers $$$u, v$$$ for which there was a road between the $$$u$$$-th and $$$v$$$-th cities, indicating that the road will go from city $$$u$$$ to city $$$v$$$. If there are multiple possible solutions, write any of them.
$$$1 \leq T \leq 100$$$, $$$2 \leq n \leq 20000$$$, $$$1 \leq k \leq m \leq 10^5$$$. The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^6$$$.
19 points $$$n \leq 10, m \leq 20, k = m$$$. The sum of $$$n+m$$$ for all cases is less than $$$250$$$.
10 points $$$k = 2$$$.
21 points $$$n \leq 1000, m \leq 2000, k = m$$$. The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^4$$$.
13 points $$$n \leq 1000, m \leq 2000$$$. The sum of $$$n+m$$$ for all cases is less than $$$2 \cdot 10^4$$$.
14 points $$$k = m$$$.
23 points No additional restrictions.
2 6 6 4 0 1 1 2 1 4 2 3 3 4 3 5 6 6 5 0 1 1 2 1 4 2 3 3 4 3 5
SI 1 2 4 1 2 3 3 4 NO