Let's review some knowledge of graph theory. In this problem, all the graphs discussed are undirected graphs.
- Connected graph: A graph is said to be connected if there exists a path between every pair of different nodes.
- Bridge: A bridge is an edge of a connected graph whose deletion makes the graph not connected.
- 2-edge-connected: A 2-edge-connected graph is a connected graph that does not have any bridges.
- 3-cycle: Nodes $$$(u,v,w)$$$ are said to be a 3-cycle if $$$(u,v)$$$, $$$(v,w)$$$, and $$$(u,w)$$$ are all directly connected by an edge.
Now given an undirected acyclic graph with $$$n$$$ nodes and $$$m$$$ edges (i.e., a forest), you need to add some edges to make the graph 2-edge-connected and have no 3-cycle. Please output the minimum number of edges to add and how to add them.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), indicating the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5,0\le m\le n-1$$$), indicating the number of nodes and edges in the graph.
Each of the following $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), indicating an undirected edge connecting $$$u$$$ and $$$v$$$. It's guaranteed that there are no self-loops or multiple edges in the graph. It's also guaranteed that any two vertices in the graph are connected by at most one path.
It's guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$10^5$$$.
For each test case, output an integer $$$k$$$ in the first line indicating the minimum number of edges to add. Then each of the following $$$k$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), indicating an undirected edge connecting $$$u$$$ and $$$v$$$. You need to ensure that there are no self-loops or multiple edges in the graph after adding edges.
If there are multiple solutions with the minimum $$$k$$$, output any. If there are no possible solutions, output $$$-1$$$ in a single line.
35 05 41 21 32 42 55 41 21 31 41 5
5 1 2 1 3 2 4 3 5 5 4 2 3 4 3 5 -1
Given a circle with radius $$$r$$$, there are five points $$$A_i$$$ ($$$i=1,2,\ldots,5$$$) arranged counterclockwise on the circle, and connecting them in the order of $$$A_1-A_3-A_5-A_2-A_4-A_1$$$ forms a pentagram. We call the above connection order the pentagram order. By slightly adjusting the arrangement, a reversed pentagram, which is the symbol of the devil, can be obtained.
However, the devil thinks this pattern is too rigid. It believes that each vertex of this pentagram should be movable in order to summon the devil. Therefore, the devil will let $$$A_i$$$ move on the circumference of a certain circle. Formally, consider the following five sets of points:
$$$$$$S_i=\{(x,y)\mid x=r \cos\theta,y=r \sin\theta,\theta_{s_i}\le \theta\le \theta_{t_i})\},i=1,2,\ldots,5$$$$$$
where $$$\theta_{s_i}$$$, $$$\theta_{t_i}$$$ are the left and right endpoints of the range of polar angles in which the point $$$A_i$$$ can move. Selecting $$$A_i$$$ from $$$S_i$$$ (it's guaranteed that there is no intersection between $$$S_i$$$ and they are arranged counterclockwise), and connecting them in the pentagram order forms a pentagram. For a point $$$P$$$ on the two-dimensional plane, if there exists a point $$$A_i$$$ in $$$S_i$$$, and $$$P$$$ is inside the pentagram formed by these five points, it is called a devil seal point. What is the area of the set of points formed by all devil seal points? The pentagram formed by the five points refers to the pentagram formed by connecting them in the pentagram order.
The devil has $$$T$$$ such questions to ask you. If you cannot answer quickly, it will curse you to draw the devil card the next time you draw a tarot card.
The first line contains an integer $$$T$$$ ($$$1\le T \le 10^4$$$) representing the number of test cases.
Each test case consists of three lines. The first line contains an integer $$$r$$$ ($$$1\le r \le 10^3$$$), the second line contains five integers, where the $$$i$$$-th integer represents $$$\theta_{s_i}$$$ ($$$0\le \theta_{s_i}\le 359$$$), and the third line contains five integers, where the $$$i$$$-th integer represents $$$\theta_{t_i}$$$ ($$$0\le \theta_{t_i}\le 359$$$). The angles above are in degree form and represent the five sets of points mentioned in the problem.
It is guaranteed that there is no intersection between the sets of points, and they are arranged counterclockwise, i.e., $$$\theta_{s_i}\le\theta_{t_i}$$$ ($$$i=1,2,\ldots,5$$$), and $$$\theta_{t_i} \lt \theta_{s_{i+1}}$$$ ($$$i=1,2,\ldots,4$$$).
For each test case, output a real number representing the area of all possible locations where the devil seal point $$$P$$$ may appear. Your answer will be considered correct only if the relative or absolute error between your answer and the correct answer does not exceed $$$10^{-6}$$$.
21054 126 198 270 34254 126 198 270 3421054 126 198 270 34264 136 208 280 352
112.256994145 168.007261527
The first example gives the area of the inscribed regular pentagon with a radius of $$$10$$$. The image following shows a possible pentagram of the second example, where the five solid line arcs are the five sets of points for example two.
Please note that reading in a large number of floating-point numbers will cause an I/O slowdown.
This is an interactive problem.
Radio direction finding, also known as radio orienteering or radio fox hunting, is a sport that combines radio technology with outdoor navigation. Participants use specialized receivers to locate hidden radio transmitters, testing their sense of direction and radio operation skills.
A university offers a PE course in radio direction finding. During the final exam, the teacher takes the students to a local tourist attraction. The map of the attraction can be considered as a cycle of $$$n$$$ points ($$$n$$$ is an odd number), numbered clockwise as $$$1,2,\ldots,n$$$. The teacher has previously buried two transmitters at two different points and given you a radio receiver.
This receiver is special; each time it receives a signal, you need to manually press a button on the receiver, and then the receiver will tell you the sum of the shortest distances from these two transmitters to your current location (distance is defined as the number of edges traversed). The passing criterion for the final exam is to find the positions of these two transmitters using the receiver no more than $$$40$$$ times.
Now, please write an interactive program to successfully pass the final exam.
First, read a positive integer $$$T$$$ ($$$1 \le T \le 10^3$$$) from the standard input, indicating the number of test cases.
For each test case, first read a positive integer $$$n$$$ ($$$3 \le n \le 10^9$$$, and $$$n$$$ is odd) from the standard input, indicating the number of points in the cycle.
Then, start the interaction process. Each time you interact, you can output the following two types of data to the standard output:
- ? x: Indicates that you are using the receiver at point $$$x$$$, and then your program needs to read an integer $$$dist$$$ from the standard input, indicating the sum of the shortest distances from the two transmitters to point $$$x$$$. You need to ensure that $$$1 \le x \le n$$$.
- For each set of data, the ? x operation should not exceed $$$40$$$ times. If you inquire more than the specified number of times, the interactor will immediately end and you will receive a "Wrong Answer" verdict.
- ! x y: Indicates your answer, i.e., the points where the two transmitters are located (order does not matter) are at $$$x$$$ and $$$y$$$. In this case:
- If your output format is correct and the answer is correct, the interactor will immediately move on to the next test case;
- Otherwise, if your output format is incorrect or the answer is incorrect, the interactor will immediately end and you will receive a "Wrong Answer" verdict.
Note: Each output needs to include a line break and flush the buffer, otherwise you may get unexpected results other than the correct answer. To flush the buffer, you can:
- For C or C++, use fflush(stdout) or cout.flush().
- For Java, use System.out.flush().
- For Python, use stdout.flush().
2 3 1 1 2 5 4 3
? 1 ? 2 ? 3 ! 1 2 ? 5 ? 1 ! 2 3
The first sample is as shown in the following figure, with hidden points at $$$1$$$ and $$$2$$$:
- Inquire ? 1, the corresponding sum of shortest distances is $$$0+1=1$$$;
- Inquire ? 2, the corresponding sum of shortest distances is $$$1+0=1$$$;
- Inquire ? 3, the corresponding sum of shortest distances is $$$1+1=2$$$;
- Finally, output ! 1 2, the answer is correct.
You recently dug out your old Nokia phone and turned it on! At this moment, you remember that you have never completed the game City Bloxx, so you decided to finish it today.
The game can be abstracted as follows: given a grid with $$$n$$$ rows and $$$n$$$ columns, with rows numbered from $$$1$$$ to $$$n$$$ from top to bottom, and columns numbered from $$$1$$$ to $$$n$$$ from left to right. Initially, each cell contains the value $$$-1$$$. You need to assign values to the cells. In each round, you can choose a cell and consider the set $$$S$$$ composed of the values of the cells (exclude the cell you choose) that share an edge with it (up, down, left, right). Then, you can reassign the value of this cell to an integer in the range $$$[0,\text{mex}(S)]$$$. Values in cells can be reassigned multiple times. Please construct a reassignment plan such that the number of cells with a final value of $$$3$$$ is not less than $$$\lfloor \frac{2(n-1)^2}{3}\rfloor$$$.
For a set $$$S$$$, $$$\text{mex}(S)$$$ represents the smallest natural number that does not appear in the set. For example, $$$\text{mex}(\{-1\})=0$$$, $$$\text{mex}(\{1,3\})=0$$$, $$$\text{mex}(\{0,1,2\})=3$$$.
The first line contains an integer $$$T$$$ ($$$1\le T\le 5$$$), indicating the number of test cases.
For each test case, there is a single line containing an integer $$$n$$$ ($$$3\le n\le 100$$$), representing the size of the grid.
For each test case, first output a line with an integer $$$k$$$ ($$$1\le k\le 10^5$$$), representing the number of operations.
Then, output $$$k$$$ lines, each containing three integers $$$x,y,w$$$ ($$$1\le x,y\le n,0\le w\le 3$$$), indicating the assignment of the cell in the $$$x$$$-th row and $$$y$$$-th column to the value $$$w$$$.
In this problem, you do not need to minimize the number of operations; you only need to provide a solution that satisfies the conditions.
235
(Please refer to the Contest material)
Given an integer sequence $$$a_1,a_2,\ldots,a_n$$$ of length $$$n$$$. For an interval $$$a_l,\ldots,a_r$$$ in this sequence, a Reduce operation divides the maximum value of the interval by $$$2$$$ (rounding down). If there are multiple maximum values, choose the one with the smallest index. There are $$$q$$$ queries. Given three integers $$$l,r,k$$$ each time, query the maximum value of the interval after performing $$$k$$$ Reduce operations on the $$$a_l,\ldots,a_r$$$ interval. The queries are independent of each other. That is to say, each time the query starts from the initially given sequence.
The two integers $$$n,q$$$ ($$$1\le n,q\le 10^5$$$) in the first line represent the sequence length and the number of queries.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10^5$$$).
The next $$$q$$$ lines each have three integers $$$l,r,k$$$ ($$$1\le l\le r\le n,0\le k\le 10^9$$$), representing a query.
For each query, output an integer in one line, representing the maximum value of the interval since the operation started from the initial sequence.
3 22 0 22 3 01 3 0
2 2
6 69 5 0 3 6 71 4 73 3 2336 6 03 4 44 5 151 1 0
1 0 7 0 0 9
You are currently downloading something from a cloud storage, but the download speed is very disappointing. Staring at the download speed monitor will make you feel a little more comfortable.
The download speed monitor works as follows: from the first to the $$$(k-1)$$$-th second, the download speed monitor will always display "loading", but from the $$$k$$$-th second, the monitor will display the average download speed from the $$$(i-k+1)$$$-th second to the $$$i$$$-th second on the $$$i$$$-th second. However, due to the small size of the monitor, when the average download speed is greater than or equal to $$$1024$$$KiBps, the download speed monitor will display the result in MiBps.
Your download task will last for $$$n$$$ seconds. Given the calculation interval $$$k$$$ for the average speed, you want to know what will be displayed on the monitor from the $$$k$$$-th second to the $$$n$$$-th second.
Note: $$$1$$$MiBps$$$=1024$$$KiBps.
The first line contains two positive integers $$$n, k$$$ ($$$2\le n,k \le 10^5,n \gt k$$$).
The next line contains $$$n$$$ positive integers $$$a_i$$$ ($$$1\le a_i\le 10^5$$$), where the $$$i$$$-th positive integer represents $$$a_i$$$KiB data downloaded in the $$$i$$$-th second.
Output $$$n-k+1$$$ lines, where the $$$i$$$-th line outputs the content displayed on the screen from the $$$i$$$-th second to the $$$(i+k-1)$$$-th second. Each line outputs a real number and a string, separated by a space. First output the average download speed, and then output the unit, as KiBps or MiBps. Refer to the sample output for the specific format. Your average download speed will be considered correct only if the relative or absolute error between your answer and the correct answer does not exceed $$$10^{-4}$$$.
5 21 1024 2048 3 5
512.500000 KiBps 1.500000 MiBps 1.001465 MiBps 4.000000 KiBps
Please note that reading in a large number of floating-point numbers will cause an I/O slowdown.
You are currently downloading something from a cloud storage, but the download speed is very disappointing. You feel that only monitoring the download speed is not enough to relieve your anxiety, so you start calculating the download time.
The network bandwidth you are using is $$$B$$$MiBps, and now you have two large files to download. The first file starts downloading at $$$t_1$$$ second and has a size of $$$a_1$$$MiB, while the second file starts downloading at $$$t_2$$$ second and has a size of $$$a_2$$$MiB. Due to your use of the most advanced congestion control algorithm, when only one file is downloading at any given time, the download rate will remain constant at $$$B$$$MiBps. When two files are downloading, the download rates of both files will remain constant at $$$\frac{B}{2}$$$MiBps. When a file starts or finishes downloading, the download rates of all files will instantly adjust to the target value.
Now you want to know how long it will take for each of the two files to finish downloading.
The first line contains an integer $$$T$$$ ($$$1\le T\le 10^5$$$), indicating the number of test cases.
For each test case, one line with five integers $$$B,t_1,a_1,t_2,a_2$$$ ($$$1\le B,a_1,a_2\le 10^5$$$,$$$0\le t_1,t_2\le 10^5$$$,$$$t_1\le t_2$$$), as described in the statement.
For each set of data, output a line with two real numbers, representing the time it takes for the first and second files to finish downloading. Your answer will be considered correct only if the relative or absolute error between your answer and the correct answer does not exceed $$$10^{-6}$$$.
35 0 10 10 43 2 7 2 13 2 7 3 7
2.000000000 0.800000000 2.666666667 0.666666667 3.666666667 3.666666667
Please note that reading in a large number of floating-point numbers will cause an I/O slowdown.
Many people have much money and expect to buy houses, but you are the opposite. You have a lot of houses but not much money. Fortunately, you can predict the future real estate speculation accurately, and you have three "smart" assistants. You can delegate the houses to them and have them help you sell the houses to make a profit.
Your predictions include two types, arranged in chronological order. The following explains the two types of predictions:
- Delegate opportunity: you need to specify an assistant and delegate a house worth $$$a_i$$$ to him;
- Real estate speculation: the assistants with houses delegated to them will each select a house to sell, and bring you the corresponding profit (note that the profit and the original value of the house may not be the same).
Here are your three "smart" assistants:
| Little Red | Little Green | Little Blue | |
| House to sell | Earliest delegated house | Highest value house | Lowest value house |
| Profit given to you after selling a house worth $$$a_i$$$ | $$$a_i-1$$$ | $$$a_i-\lceil \frac{a_i}{10} \rceil$$$ | $$$a_i$$$ |
Given a prediction sequence of length $$$n$$$ arranged in chronological order, please select the appropriate assistant for all the first type of predictions, so as to maximize the total profit obtained from the second type of predictions, and output this total profit. Please note that after the predictions end, any unsold houses will be wasted and will not bring any profit.
The first line contains an integer $$$T$$$ ($$$1\le T\le 10^4$$$), indicating the number of test cases.
For each test case, the first line contains an integer $$$n$$$ ($$$1\le n\le 200$$$) representing the number of predictions, followed by $$$n$$$ lines, each describing a prediction in chronological order, in the following format:
- 1 $$$a_i$$$ ($$$1\le a_i\le 10^6$$$), representing the first type of prediction;
- 2, representing the second type of prediction.
It is guaranteed that $$$\sum n\le 10^4$$$.
For each test case, output a single integer on a new line, representing the maximum profit you can obtain.
271 4021 301 201 151 1271 401 301 201 151 122
102 103
For the first test case, first, delegate the house worth $$$40$$$ to Little Blue, then a real estate speculation occurs, and assistant Little Blue sells the house and brings you a profit of $$$40$$$. After that, you delegate the house worth $$$30$$$ to Little Blue, the house worth $$$20$$$ to Little Red, the house worth $$$15$$$ to Little Green, and the house worth $$$1$$$ to Little Red. In the final real estate speculation, assistant Little Red selects the earliest delegated house worth $$$20$$$, sells it, and brings you a profit of $$$19$$$, Little Blue brings you a profit of $$$30$$$, and Little Green brings you a profit of $$$13$$$, for a total profit of $$$102$$$. It can be proved that this is the most profitable allocation method.
For the second test case, one way to obtain the maximum profit is to delegate the house worth $$$40$$$ to Little Red, $$$30$$$ to Little Red, $$$20$$$ to Little Blue, $$$15$$$ to Little Blue, and $$$1$$$ to Little Blue.
There is a sequence of $$$n$$$ integers, numbered from $$$1$$$ to $$$n$$$ from left to right. These integers come in two colors, $$$0$$$ and $$$1$$$, with each integer having exactly one color. These integers enter a multiset $$$S_1$$$ in the order of their numbering from $$$1$$$ to $$$n$$$.
Whenever a new integer $$$x$$$ enters $$$S_1$$$, you must choose an integer $$$y$$$ in $$$S_1$$$ whose color is different from $$$x$$$ to react with $$$x$$$, causing $$$x$$$ and $$$y$$$ to disappear and the reaction product $$$x+y$$$ to be inserted into another set $$$S_2$$$. If no such $$$y$$$ exists, no reaction occurs and only $$$x$$$ will be inserted into $$$S_1$$$.
Given the sequence of integers and the color of each integer, find the maximum possible value of the smallest element in $$$S_2$$$ after processing the last element.
The first line contains an integer $$$n$$$ ($$$2\le n\le 10^5$$$), representing the number of integers.
The second line contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^8$$$), representing the sequence of integers.
The third line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$c_i\in \{0,1\}$$$), where $$$c_i$$$ represents the color of the $$$i$$$-th integer.
It is guaranteed that there is at least one $$$i$$$ such that $$$c_i=0$$$, and at least one $$$j$$$ such that $$$c_j=1$$$.
Output a single integer, representing the answer.
4 1 3 2 4 0 0 1 1
5
6 1 3 4 2 5 6 0 1 0 1 0 1
4
7 3 3 4 4 5 3 1 0 0 1 1 1 0 0
7
There is a grid with $$$n$$$ rows and $$$m$$$ columns, where the rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right. The value of the cell in the $$$i$$$-th row and $$$j$$$-th column is $$$w_{i,j}$$$.
Now you can use any number (include zero) of tiles of size $$$1\times k$$$ to cover this grid. The tiles can be rotated, and $$$k$$$ can be any positive integer, but cannot exceed the grid boundaries. Each tile can have a different $$$k$$$. When covering, make sure that these tiles do not overlap and do not have adjacent edges. Find the maximum sum of the values of the covered cells.
The first line contains two integers $$$n,m$$$ ($$$1\le n,m\le 18$$$), representing the size of the grid.
For next $$$n$$$ lines, the $$$i$$$-th line contain $$$m$$$ integers $$$w_{i,1},w_{i,2},\ldots,w_{i,m}$$$ ($$$|w_{i,j}|\le 10^6$$$), representing the values of the cells.
Output a single integer on a new line, representing the maximum sum of the values of the covered cells.
2 2 2 1 1 1
3
4 4 -1 2 1 -2 3 2 0 -2 -3 -2 0 3 2 3 0 1
15
Alice and Bob are playing a number deletion game.
At the beginning, there are $$$n$$$ integers $$$a_1,a_2, \ldots ,a_n$$$. Alice and Bob take turns to delete numbers, with Alice going first. Each person can delete the largest number $$$x$$$ (if there are multiple largest numbers, delete one of them), choose a non-negative integer $$$y$$$ that is smaller than $$$x$$$, and add the numbers $$$1,2,\ldots, y$$$. In particular, it is possible to choose $$$y=0$$$, in which case no numbers will be added. This means that when deleting $$$1$$$, no numbers can be added. The person who deletes the last number wins.
Both players use the optimal strategy. Determine who wins, Alice or Bob.
The first line contains a positive integer $$$n$$$ ($$$1\le n\le 10^3$$$), indicating the initial number of integers.
The second line contains $$$n$$$ positive integers $$$a_1,a_2\dots a_n$$$ ($$$1\le a_i\le 10^9$$$).
Output one line. If Alice wins, output Alice. Otherwise, output Bob.
23 3
Bob
22 3
Alice