Chess is a strategic game that involves different phases: opening, middlegame and endgame. Each of the phases requires specific preparation. Many players prioritize the opening: "If I lose in the opening I will never reach an endgame". Others, on the other hand, play openings with very simple plans and their efforts are devoted to studying chess endgame patterns. There are many endgame maneuvers, each with specific concepts, either to win the game or to make a draw.
Some of the most complicated endgames are pawn endgames. It is true that there are not many pieces, but there are too many possible combinations for humans. This problem focuses on the endgame of a pawn and kings (for simplicity, we will assume that the pawn will always be white and there will be no white king).
Given a specific position on a chessboard, your task is to determine if the black king can capture the white pawn. White will try to promote before it is captured (see below for some simplified chess rules).
It is guaranteed that all positions are legal, the white pawn plays optimally and the moves must be legal according to the rules of chess.
There will be several test cases, represented by a number $$$N$$$ given in the first line. For each test case a line is shown containing a positive integer, representing the size of the chessboard ($$$T$$$), and immediately following the character, "B" or "N", indicating the player making the next move ("B", for "Blanco" in Spanish, represents that it is the white pawn's turn, while "N", for "Negro" in Spanish, represents that it is the black king's turn). The next and last line of each case contains four integers separated by spaces: the $$$C_b$$$ column and $$$F_b$$$ row of the white pawn, followed by the $$$C_n$$$ column and $$$F_n$$$ row of the black king.
For each test case, print "SI", if the black king can capture the white pawn, and "NO" otherwise.
2 8 N 1 3 6 2 8 B 1 3 6 2
SI NO
Some chess rules relevant to this problem:
- A piece is captured when the square on which it is located is occupied by an opponent's piece.
- The king can only move one square in any direction: up, down, sideways or diagonally. In no case can the king move to a square where it would be in check, i.e. where it could be captured.
- Pawns have the peculiarity that they move and capture in different ways: they move forward, but capture diagonally forward. Pawns can only advance one square in each move, except when they are on rank 2 (initial position in chess games) when they can advance two squares. Pawns can only capture a square located diagonally. They can never move back, not even to capture a piece. Pawns cannot move if on their way they encounter a piece that occupies the square directly in front of them, nor can they capture it. That is, if the pawn is on the square, $$$(F, C)$$$ the only possible moves are:
- move to the square $$$(F+1, C)$$$ if the square is empty,
- move to the square $$$(F+1, C-1)$$$ or $$$(F+1, C+1)$$$ if the squares are occupied by an opponent's piece,
- if $$$F = 2$$$ it can also move to the square $$$(F+2, C)$$$ if the squares $$$(F+1, C)$$$ y $$$(F+2, C)$$$ are empty.
- A pawn is said to be promoted when it reaches the last row of the board. At this point it can become another piece of your choice (except king or pawn). Note that if it reaches the last row and promotes, the next turn belongs to the opponent, who can immediately capture if it is next to it.
In the midst of a protest over the difficult conditions faced by farmers, it has been decided to block some roads as a measure of pressure. As the son of a farmer, you have been given the task of developing an algorithm to determine, given an origin city and a destination city, the minimum number of roads to block to make it impossible to get from one city to the other.
Each farmer is able to block one road, so the goal is requiring the minimum number of farmers, allowing the rest to continue working and providing basic resources to the population.
The input consists of a single test case. Each case starts with two integers $$$N$$$ and $$$M$$$, representing the number of cities and roads in the city, respectively. Then follow $$$M$$$ lines, each with two integers $$$A_i$$$ and $$$B_i$$$ between $$$0$$$ and $$$N-1$$$, indicating that there is one road connecting city $$$A_i$$$ to $$$B_i$$$ (and not vice versa). It is guaranteed that there will be at most one road connecting two cities in the same direction. The origin city is city $$$0$$$ and the destination city is city $$$N-1$$$.
- $$$1 \leq N \leq 160$$$ $$$1 \leq 1,000 \leq M$$$
- $$$0 \leq A, B \leq N-1$$$
- $$$A_i \neq B_i$$$ $$$(A_i, B_i) \neq (A_j, B_j)$$$
In the first line you must print a single integer, the minimum number of farmers $$$X$$$ necessary to block the circulation between city $$$0$$$ and city $$$N-1$$$. Next, you must print $$$X$$$ lines, with two integers separated by a space on each line, the two cities $$$A_i$$$ and $$$B_i$$$ joining the road that a farmer will occupy, in the direction from $$$A_i$$$ to $$$B_i$$$. If there are several possible answers, anyone will be accepted. Also, the order in which the roads are printed does not matter.
6 8 0 1 0 2 1 2 2 3 3 4 4 1 3 5 4 5
1 2 3
Isidra likes to travel between galaxies in her free time. After years of study, the "Facultad de Fomento del Turismo" provides a map that includes the distances between galaxies. Perhaps because the funds dedicated to research were not enough to obtain more data, or perhaps because of fear of finding inconsistencies in the results and because no one really understands the laws of physics, the map provided is a bit special, in such a way that between any two galaxies, there is only one way to measure the distance between them.
Isidra is one of those people who say that the journey is the actual path and not the destination, so the longer the journey, the more she enjoys it. She is also aware that as time passes, galaxies always move further away from each other. To make things easier, the map provides, on one hand, the initial distance between galaxies, and on the other hand, how much that distance will increase with each passing year. Isidra is very inquisitive, so she would like to know for two different galaxies, what is the minimum whole number of years that must pass for these two galaxies to be at a distance greater than or equal to whatever value she wants.
More formally, $$$n$$$ galaxies and $$$n-1$$$ distance measures between pairs of galaxies are given. The measurement $$$i$$$ between galaxies $$$u_i$$$ and $$$v_i$$$ consists of two integers $$$a_i, b_i$$$, such that after $$$t$$$ years, the distance between $$$u_i$$$ and $$$v_i$$$ is $$$d_i = a_i$$$ + $$$t \cdot b_i$$$. A question from Isidra is of the form $$$(u, v, w)$$$, which means "what is the minimum integer number of years that must pass for the distance between $$$u$$$ and $$$v$$$ to be greater than or equal to $$$w$$$?"
Of course, Isidra won't be satisfied with just one question, so be prepared to answer many of them.
The first line contains a single integer $$$n$$$ — the number of galaxies.
The following $$$n-1$$$ lines each include four integers $$$(u_i, v_i, a_i, b_i)$$$ — the two galaxies $$$u_i, v_i$$$ that make up the $$$i$$$-th measurement, the initial distance $$$a_i$$$ between them and the extra distance $$$b_i$$$ that they separate each year. The distances are independent of the direction in which you travel between the two galaxies.
The next line contains a single integer $$$q$$$ — the number of questions.
Next will come $$$q$$$ lines, each containing three integers $$$(u_i, v_i, w_i)$$$ — the two galaxies $$$(u_i, v_i)$$$ ($$$u_i \neq v_i$$$) for which to compute the minimum time so that the distance is greater than or equal to $$$w_i$$$.
- $$$2 \le n \le 10^5$$$
- $$$1 \le u_i, v_i \le n$$$
- $$$1 \le a_i, b_i \le 10^4$$$
- $$$1 \le q \le 10^5$$$
- $$$1 \le w \le 10^9$$$
Print $$$q$$$ integers separated by spaces, the answers to each question, in the given order. If they are already at a distance greater than or equal to that requested at the initial moment, the response will be $$$0$$$.
3 1 2 1 2 1 3 1 1 3 2 1 4 2 3 5 1 3 1
2 1 0
After so many years of competition your friend Marcos has decided to quit competitive programming, he is tired of solving problems. In this radical change of life he has decided to open a little newsstand in the park where he can enjoy a quieter life.
The problem is that the park where he wants to work has 3 fountains that are active all afternoons. Marcos doesn't want his customers to become wet while chatting with them as they choose their newspaper, so he's looking for the perfect place to set up his store.
The amount of water that reaches each point of the park is defined by the fountain closest to it. It is true that the rest of the fountains also wet, but it is so little that it can be ignored. Therefore, Mark's objective is to place his tent in such a way as to maximize the distance to the nearest fountain, i.e., to maximize the value of $$$\texttt{DRYNESS}$$$ described by: $$$$$$\texttt{DRYNESS}(p) =\min \{ d(p,F_1), d(p,F_2), d(p,F_3) \}$$$$$$ where $$$F_1$$$,$$$F_2$$$ y $$$F_3$$$ represent the positions of the fountains and the function $$$d(p, q)$$$ represents the Euclidean distance in the plane between two points $$$p$$$ and $$$q$$$, that is, the usual distance in a straight line.
Knowing that the park enclosure is a perfect square of side $$$100$$$ and its lower left corner is at the point $$$(0,0)$$$, can you indicate what is the largest value of $$$\texttt{DRYNESS}$$$ that Marcos will be able to achieve by placing his new store?
The input starts with a number $$$N$$$, the number of test cases to be processed. Each test case is composed of 3 lines, each indicating a pair of numbers $$$(F_x,F_y)$$$, the position of one of the fountains. All these values will be indicated with 3 decimal places, using the point as decimal separator.
- $$$ 1 \le N \le 10^4$$$
- $$$0 \le F_{1x},F_{2x},F_{3x},F_{1y},F_{2y},F_{3y} \le 100$$$
- $$$(F_{1x},F_{1y}) \neq (F_{2x},F_{2y})$$$
- $$$(F_{1x},F_{1y}) \neq (F_{3x},F_{3y})$$$
- $$$(F_{2x},F_{2y}) \neq (F_{3x},F_{3y})$$$
The output for each case will indicate a three digits rounded number (using the point as decimal separator), the maximum value of DRYNESS that Marcos can achieve by placing his tent in the park.
1 19.000 13.000 10.000 81.000 73.000 44.000
62.169
To print a number $$$x$$$ with 3 decimal digits, you can use:
- C++
std::cout « std::fixed « std::setprecision(3) « x « std::endl;
- Java
double round = Math.round(x * 1000.0) / 1000.0;
String numberRounded = String.format(" System.out.println(numberRounded);
- Python
print(f'{x:.3f}')
A supermarket has two checkouts to collect the products purchased by its customers and, for that reason, there are always two queues, which, however, progress at different speeds, resulting in anger among some customers. Fed up with the situation, the supermarket has decided to implement an algorithm to determine which queue each customer should be placed in, taking into account the estimated time it takes to serve them at the checkout, so that the total time to serve all customers is as short as possible.
There will be several test cases, represented by a number $$$C$$$ on the first line. For each test case, on a single line, the number of customers in total, $$$N$$$, is indicated first, followed by $$$N$$$ numbers indicating the time $$$T$$$ each one takes to be served.
- $$$1 \leq C \leq 3000$$$
- $$$1 \leq T \leq 8000$$$
- $$$1 \leq N \leq 3000$$$
- The sum of all times $$$T$$$ over all test cases will not exceed $$$8000$$$
- The sum of $$$N$$$ over all test cases will not exceed $$$3000$$$
For each test case it is necessary to indicate the time taken by the first and second cashier, respectively, to serve the customers assigned to each of them, so that the difference between the two times is as small as possible. If it does not take the same time, the second cashier will take the longest.
3 3 1 3 1 4 1 3 6 2 6 2 2 3 4 8 11
2 3 6 6 15 15
The company "Bailes S.A." is interested in making a new domestic cleaning robot. As there is very strong competition in this sector, it has decided to make a robot that has something new and has decided to incorporate a Lidar (a sensor that measures distances by laser). Although, as Lidar sensors are quite expensive, he has opted for a single beam Lidar that allows him to measure the free distance in front of the robot. It has done very well, has already built it and is eager to test it, so it has contacted you to make a software prototype.
Your program must control the movement of the robot on a map defined by a grid of cells using 3 basic commands: move forward, turn left and turn right. When moving forward, it only advances a single cell. The turns are 90 degrees. Each time one of these commands is executed, the number of free cells in front of the robot is received. Each cell of the grid can only be free or occupied. The robot cannot leave the grid and, in fact, the measurement of the number of free cells will be zero if measured from the boundary and outwards.
The robot always starts in the cell at the lower left boundary of the grid and must reach the cell at the opposite end, i.e., if the grid has size $$$N \times N$$$ and we take the lower left cell as the cell whose coordinates are $$$(1,1)$$$, the destination would be the cell whose coordinates are $$$(N,N)$$$. The robot always starts oriented upward, i.e., if its first move is a forward move then it would move to the cell $$$(1,2)$$$. It is guaranteed that $$$N$$$ is at most $$$20$$$.
It is not necessary to find the optimal solution, that is, solutions where the path can be longer than optimal are admitted, but due to battery constraints, the forward movements are limited to $$$4 \cdot N^2$$$. Of course, the solution is not unique, the robot can go through many different paths, in the end it doesn't matter, the important thing is that it cleans.
A possible cell map is shown in the figure. The coordinates of the start and end cell are shown, as well as the coordinates of a couple of additional cells. Cells with an "X" are not free. A "layer" of cells outside the grid, also marked with an "X", is also shown.
The entry consists of a single test case.
On the first line there is a number $$$N$$$, which indicates the size in cells of the problem's grid. Next, you can read, on one line, the number of free cells initially in front of the robot, a positive integer between $$$0$$$ and $$$N-1$$$.
Then, each time the program produces an output (a movement command), the number of free cells in front of the robot will be written on a new line, or END if the robot has reached its destination, that is, if it has reached the cell of coordinates $$$(N, N)$$$.
If the robot is placed on the edge of the grid and facing outward the number of free cells will be $$$0$$$.
Commands are coded with three letters, "A" for "forward" ("Avanzar" in Spanish), "D" for "turn right" ("Derecha" in Spanish) and "I" for "turn left" ("Izquierda" in Spanish). They must be written without quotation marks and a newline must be written after the command. Immediately after writing the command you can read the number of free cells.
If the command to move forward is given and the robot cannot do so because there is no free cell, a wrong result will be automatically produced (Wrong Answer).
Remember that it is convenient to flush the output channel. In C/C++ this is done with: fflush(stdout);, in Java with System.out.fflush(); and in Python with print([...], flush=True);.
5 4 3 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 4 3 2 1 0 4 3 2 1 END
A A A A D A A D A A D A A I A A I A A A A I A A A A
The sequence in which the input/output occurs for the first steps is: the 5 ($$$N$$$) and the 4 (free cells) are written to the input, the program then writes A (advance), and immediately afterwards it will have the $$$3$$$ in the input.
- The example output corresponds to the diagram in the figure.
- Important: The solution shown as output has been done manually knowing the cell map. It cannot be used as a basis for developing the algorithm.
- The algorithm has a limit number of forward movements, but there is no limit for turns.
- Of course, the usual time limit does exist and it overlaps the forward movements limit.
- An example about turns: if the robot is pointing up (increasing "y" coordinates) and turns to the right, it remains pointing to the right (increasing "x" coordinates) and respectively if it turns to the left it remains pointing to the left (decreasing "x" coordinates).
Furtis is tired of programming. He now devotes his free time to thinking about problems, preferably without having to code his solutions, because he is very lazy. He spends his days making up operations, asking himself questions about them and trying to come up with a satisfying solution. It seems it is the only way to explain how he came up with this problem...
Furtis defines a game on a $$$2 \times M$$$ grid ($$$2$$$ rows and $$$M$$$ columns). In each square you start with the value $$$0$$$. In an operation you can choose a square, subtract $$$1$$$ from it and add $$$1$$$ to its two diagonal neighbors. This can only be done if the two neighbors are within the grid.
Example of two types of allowed operations 
Example of two types of operations not allowed More formally:
- If the square $$$a_{1, x}$$$ is chosen and the squares $$$a_{2, x-1}$$$ and $$$a_{2, x+1}$$$ are inside the grid, you assign:
- $$$a_{1, x} \leftarrow (a_{1, x}-1)$$$
- $$$a_{2, x-1} \leftarrow (a_{2, x-1}+1)$$$
- $$$a_{2, x+1} \leftarrow (a_{2, x+1}+1)$$$
- If the square $$$a_{2, x}$$$ is chosen and the squares $$$a_{1, x-1}$$$ and $$$a_{1, x+1}$$$ are inside the grid, you assign:
- $$$a_{2, x} \leftarrow (a_{2, x}-1)$$$
- $$$a_{1, x-1} \leftarrow (a_{1, x-1}+1)$$$
- $$$a_{1, x+1} \leftarrow (a_{1, x+1}+1)$$$
Furtis wants to know if it is possible to make all the squares at the same time equal to a given integer value $$$V$$$ and if so, the minimum number of operations necessary to do so.
Naturally, you are not Furtis and you are in a competitive programming contest, so you will have to code the solution...
The first line contains a single integer $$$t$$$ — the number of test cases.
The following $$$t$$$ lines each include two integers ($$$M, V$$$) — the number of columns for a $$$2 \times M$$$ grid and the value $$$V$$$ that you want to obtain in all the cells at the same time.
- $$$1 \le t \le 2 \cdot 10^5$$$
- $$$1 \le M \le 10^9$$$
- $$$1 \le V \le 10^9$$$
For each test case, print on a new line a single integer — the minimum number of operations necessary for all cells to have the same value $$$V$$$ at once. If it is impossible for that case, print -1.
2 3 1 6 3
-1 36
Tetris is probably the most famous video game in the world. A few months ago an achievement that seemed impossible was achieved, a 13 year old kid nicknamed "BlueScuti" managed to reach the game's kill screen, a moment where the memory of the original game fails and it is assumed that you have reached the "end". Actually this happens in the NES version of the game which is considered the most realistic version of Tetris, current computers can easily beat the game.
You are going to play a similar game, you have to create a tower of $$$2\times1$$$ blocks very similar to those of Tetris, which will be placed in the typical grid of the game. As in Tetris, they will fall from above and will land when they come into contact (at their base) with the ground or with another block.
At some squares of the grid there will be coins of different values that will make up the score of the game: if a block is on top of a coin at the end of the game, the player will get a score equal to its value.
The blocks can be placed vertically or horizontally. However, with the exception of the first block, they must always be placed on top of the last one placed, i.e., at least one square of the new block must be on top of a square occupied by the previous block. In other words, they must form a "tower". In addition, the width of the playing area must be delimited, and blocks may not be placed beyond this limit. The game ends when the maximum height of the playing area is exceeded.
Are you able to determine the highest possible score in Tower Tetris?
The input will form a single test case. The first line will contain two values $$$W,H$$$, which will be the width and height of the board respectively.
Subsequently a number $$$N$$$ will appear, the number of coins in the grid. Finally $$$N$$$ lines with three values $$$X_i, Y_i, V_i$$$, the position where the coin will be described by its coordinates $$$(X_i, Y_i)$$$, and its value $$$V_i$$$. The position is computed assuming that the lower left square is $$$(0, 0)$$$ and the values grow upward and to the right.
- $$$2 \leq W,H \leq 1,000$$$
- $$$0 \leq N \leq W\cdot H$$$
- $$$0\leq V_i \leq 100$$$
- $$$0 \leq X_i \lt W$$$
- $$$0 \leq Y_i \lt H$$$
- Two coins will never be at the same square.
For each case a single $$$D$$$ value must be printed, the maximum number of points that can be obtained in the game, until the upper limit of the playing area is reached.
5 6 6 2 0 5 1 1 5 0 2 5 0 3 5 0 4 5 2 5 5
30
5 6 6 0 0 5 0 1 5 0 2 30 0 3 5 0 4 5 4 2 60
60
In a fantastic world there exists a special magic sock, and in this world live two mischievous elves, Dobby and Winky, who love creating and playing with magical objects.
Full of creativity, Dobby and Winky work together to bring new magical objects to life. Inspired by their fascination, they create a shimmering bridge of light, connecting each new object to another. This connection can be made with the special magic sock or with any other magical object that is already connected through the existing light bridges to the magic sock. It's like they weave a magic web with their own hands! In this way, they shape their "magic tree", a reflection of their imagination and spirit.
After creating their masterpiece, Dobby and Winky embark on the competitive part of the game. Instead of adding more objects, they take turns removing light bridges. Each turn, a player removes a single light bridge, causing magical objects, and the light bridges connecting them, that are no longer linked to the magic sock to vanish into thin air. Whoever gets to play when only the magic sock is left loses, as they cannot eliminate any bridge.
Dobby and Winky have repeated this game numerous times, creating magical trees and then destroying them, so they have become experts at the game, but are already a little tired of playing. For the next magic trees they had in mind, they want you to tell them whether the first or second player wins, taking into account that both of them play optimally.
The input consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Each test case is made up of two lines.
The first line of each case contains a single integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the number of objects in the magic tree.
Each object is represented by a number from $$$1$$$ to $$$n$$$, with the magic sock being represented by the number $$$1$$$.
The second line of each case contains $$$n-1$$$ integers $$$o_2, o_3, \dots, o_n$$$ ($$$1 \le o_i \lt i$$$) — the object to which each non-special object in the tree was connected.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print $$$1$$$ if the first player has a winning strategy or $$$2$$$ if the second player has a winning strategy.
4 3 1 2 3 1 1 4 1 1 1 7 1 2 2 1 5 5
1 2 1 2
(a) Magic tree created by Dobby and Winky.(b) Magic tree after the first player removes the bridge between object 1 and object 2.
(a) Magic tree created by Dobby and Winky.(b) Magic tree after the first player eliminates the bridge between object 1 and object 2
(c) Magic tree after the second player eliminates the bridge between object 1 and object 3.
Regardless of the first player's initial move, the second player has a winning strategy. If the first player removes the bridge connecting object 2 to object 1, object 2 disappears. On the second player's turn, only objects 1 and 3 connected by a bridge remain (see Fig. 2(b)). The second player can eliminate the only bridge causing object 3 to disappear. Then, when it is the first player's turn again, only object 1 will remain (see Fig. 2 (c)), he will not be able to play and, therefore, will lose the game. With an analogous analysis it can be shown that if the first player eliminates in his first turn the bridge connecting object 3 with 1, in the second turn of the first player there will again only be object 1 and, therefore, also the first player will lose the game in this case.
In preparation for the party, you have been filling water balloons with such enthusiasm that you have not realized that almost none of them have the same amount of water. Instead of starting from scratch, you've decided to continue with your frenetic method, filling the balloons with an arbitrary amount of water, then discarding (and popping) those that are too big or too small.
For example, if you have inflated balloons with quantities of 16, 10, 9, 12 and 11 units of water, and you decide to discard the largest balloon and the two smallest ones, you will discard the balloons with quantities 9, 10 and 16, which will make you waste 35 units of water.
There will be several test cases, represented by a number $$$C$$$ in the first line. Each test case contains the values $$$E$$$, $$$A$$$, and $$$B$$$. The number $$$E$$$ of events that will take place, and the values $$$A$$$ and $$$B$$$, representing the number of smallest and largest balloons to pop, respectively ($$$0\leq A+B \lt E$$$). $$$E$$$ lines appear below, each describing an event in chronological order with two possible formats:
- H $$$x$$$: Indicating that a new balloon is inflated with an amount $$$x$$$ of water.
- Q: Indicating that you are asking yourself the question of how much water would be wasted if you decided to stop inflating balloons at that moment. Remember that you are only asking yourself the question, you are not getting to pop any balloon.
All test cases start with at least $$$A+B$$$ events of type H, and contain at least one event of type Q.
- $$$1 \leq C \leq 10.000$$$
- $$$1\leq x\leq 10^{18}$$$
- $$$A+B+1\leq E$$$
- The total number of events, $$$E$$$, is less than or equal to $$$2 \cdot 10^{5}$$$
For each event of type Q, write on a separate line the sum of the water that would be spent if the balloons were popped at that moment. As the sum can be very large, the result will be written modulo 1,000,000,009.
At the end of each test case write three dashes '—'.
2 8 1 1 H 1 H 2 H 3 P H 4 P H 5 P 8 2 3 H 1 H 1 H 1 H 1 H 2 P H 100 P
4 5 6 --- 6 105 ---
Goldbach's conjecture states that any even number greater than 2 can be written as the sum of two prime numbers. For example:
| 4 = | 2 + | 2 |
| 6 = | 3 + | 3 |
| 8 = | 3 + | 5 |
| ... | ||
| 9 = | 2 + | 7 |
| 15 = | 2 + | 13 |
| 21 = | 2 + | 19 |
| ... | ||
Given an index $$$i$$$, you are asked to compute the number at that position in $$$\mathcal{G}$$$, the Goddbach sequence, $$$\mathcal{G}_i$$$.
There will be several test cases, represented by a number $$$C$$$ given in the first line of the input. Each test case consists of exactly one line, each of which contains a single index $$$i$$$, counted from position 1.
- $$$1 \leq C \leq 500.000$$$
- $$$1 \leq i \leq 500.000$$$
The output should consist of as many lines as there are test cases defined in the input, $$$C$$$, so that each line should show the number of the Goddbach sequence occupying the position specified in the corresponding test case.
3 1 3 103
9 21 759
In Next Digital we are 105 employees ( "nexters") and thanks to the fact that we are a 100% remote company we are spread all over the Spanish geography, or living as digital nomads abroad. The average age is 27 years old, and we like to see each other, have a cold beer and eat in an Asturian restaurant. Since we have more than a hundred nexters, it is more difficult to coincide, so we have planned to have multiple coworking spaces distributed in such a way that all nexters have at least one space less than an hour away by one or more means of transport, directly or passing through other cities. We don't want to waste time traveling, and since we are remote, it doesn't make sense to buy offices that will be empty most of the time.
We have asked for a budget from different coworking companies that offer us several flexible workspaces on demand. We have already discarded those companies that either did not have coffee included or were not in cities with any nexter living there. Now we have to rule out those that don't have workspaces close enough to each and every nexter. We don't want to hire multiple companies, we just want sufficiently distributed locations.
To reach a conclusion we have divided the work among several teams. The "Hormigas" team has made a list of the cities where there are one or more nexters, the "Vacas" team has obtained through an API the travel times between these cities, the '"Koalas" team has processed all the information previously generated and obtained the minimum distance between each city connected directly or through intermediate cities without nexters living. Everything was ready for "Mapaches" team to verify the list of coworking spaces, but the constant errors in one of their applications have left this task in their backlog.
The entry begins with the numbers $$$N$$$, $$$E$$$, $$$X$$$ and $$$T$$$ on a single line. Being:
- $$$N$$$ ($$$0 \lt N \le 200$$$) an integer indicating how many different cities the 105 nexters are in,
- $$$E$$$ ($$$0 \le E \le 20,000$$$) the number of roads connecting two different cities,
- $$$X$$$ ($$$0 \le X \le 50$$$) the number of coworking companies filtered by the "Hormigas" team, and
- $$$T$$$ ($$$1 \lt T \le 200$$$) the maximum minutes a nexter is willing to travel in total; if it takes $$$T$$$ minutes or more on the way there or back, they will no longer want to go. There is no waiting time on transfers.
- $$$1 \le c \lt T$$$
- The following conditions are guaranteed:
- The sum of N over all test cases will not exceed $$$200$$$.
- The sum of E over all test cases will not exceed $$$20,000$$$.
- The sum of X over all test cases will not exceed $$$50$$$.
Finally, $$$X$$$ rows will appear, one for each coworking company. Each row will start with the number $$$o$$$ ($$$1 \le o \le N$$$) indicating in how many cities they offer us an office, followed by $$$o$$$ numbers where each number is the index of a city.
We are asked to write one line for each test case, with the index list of companies separated by spaces in ascending order that have enough coworking spaces distributed so that nexters have at least one location closer than $$$T$$$ minutes. If none of the companies meet this constraint, "NO HAY EMPRESAS" will be written. The index of a company will be its position in the list of $$$X$$$ companies starting with $$$1$$$ and ending with $$$X$$$.
The program will terminate when it receives the input "$$$N=E=X=T=0$$$" without displaying anything in the output.
4 4 4 60 1 2 20 2 3 20 4 3 50 1 4 40 1 2 1 3 1 4 2 1 2 5 5 4 60 1 2 20 2 3 20 4 3 50 1 4 40 5 1 55 1 2 1 3 1 4 2 2 3 0 0 0 0
2 4 NO HAY EMPRESAS