Of course, you do.
Don't even try to resist it—you can already feel it deep inside: the primal urge to build a Christmas tree. Right here, right now.
But beware: an ordinary Christmas tree will not do. You must build a Special Christmas Tree.
For the purposes of this problem, a Christmas Tree is simply a binary tree— that is, a connected, acyclic graph where each node has degree at most three.
So, what makes it Special?
You are given three integers $$$P$$$, $$$Q$$$, and $$$R$$$.
Suppose your Christmas Tree has $$$N$$$ nodes, labeled $$$1$$$ through $$$N$$$.
The following conditions must hold:
Here, the distance between two nodes means the number of edges on the unique simple path between them.
Your task is to construct such a Special Christmas Tree, or declare that it is impossible.
The input consists of multiple test cases.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 1000$$$)— the number of test cases.
Each of the next $$$T$$$ lines contains three integers $$$P$$$, $$$Q$$$, and $$$R$$$ ($$$1 \le P \le 10^5$$$, $$$0 \le Q, R \le 10^6$$$) — the designated counts of pairs of nodes at distances $$$1$$$, $$$2$$$, and $$$3$$$, respectively.
The sum of $$$P$$$ over all test cases does not exceed $$$10^5$$$.
For each test case:
Print a line with a single integer $$$N$$$ — the number of nodes in your tree.
Then print $$$N-1$$$ lines, each with two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$), denoting an edge between nodes $$$u$$$ and $$$v$$$.
If there are multiple possible trees, output any of them.
If no Special Christmas Tree exists, output $$$-1$$$.
32 1 05 6 43 7 1
3 1 2 2 3 6 1 2 2 3 2 4 1 5 1 6 -1
The Special Christmas Tree for the second test case can be visualized as:
Figure D.1: Example of the Christmas tree for the second test case. There are $$$5$$$ node pairs with distance $$$1$$$: $$$(1,2)$$$, $$$(2,3)$$$, $$$(2,4)$$$, $$$(1,5)$$$, and $$$(1,6)$$$.
There are $$$6$$$ node pairs with distance $$$2$$$: $$$(1,3)$$$, $$$(1,4)$$$, $$$(2,5)$$$, $$$(2,6)$$$, $$$(3,4)$$$, and $$$(5,6)$$$.
There are $$$4$$$ node pairs with distance $$$3$$$: $$$(3,5)$$$, $$$(3,6)$$$, $$$(4,5)$$$, and $$$(4,6)$$$.
The Intergalactic Cosmic Phenomenon Containment (ICPC) has reported a surge in Breach-Level Unstable Events (BLUEs) — rare extradimensional disturbances that manifest as rift points in local spacetime. If left unchecked, these anomalies may cascade into a full-scale reality fracture, erasing the timeline of the entire universe.
To address this crisis, the ICPC has deployed $$$N$$$ Anomaly Regulation Centers (ARCs). Each ARC must be assigned a set of BLUEs to stabilize, under the following conditions:
Each BLUE must be assigned entirely to exactly one ARC (no splitting or sharing). An ARC may stabilize multiple BLUEs, but the total required energy for its assigned anomalies must be drawn from its own reservoir.
To maintain synchronization across containment protocols, the ICPC mandates that the energy loads be distributed as evenly as possible among the ARCs.
Your task is to determine the minimum possible energy imbalance, defined as the difference between the maximum energy assigned to any ARC and the minimum energy assigned to any ARC.
The first line contains a single integer $$$T$$$ — the number of test cases. ($$$1 \le T \le 1000$$$)
The next $$$T$$$ lines each contain three integers $$$X, Y, N$$$. ($$$0 \le X, Y \le 10^9$$$, $$$2 \le N \le 10^6$$$) — the number of Type-Alpha BLUEs, the number of Type-Omega BLUEs, and the number of Anomaly Regulation Centers (ARCs).
For each test case, output a single integer — the minimum possible difference between the maximum energy assigned to any ARC and the minimum energy assigned to any ARC.
52 2 31 4 33 2 30 5 33 0 3
0 2 1 2 0
In the first case, the distribution can be as follows:
In the second case, the distribution can be as follows:
A certain high school requires students to read several selected books. Among those books, there is one outstanding book titled "Flying Pig".
There are $$$N$$$ students, numbered from $$$1$$$ to $$$N$$$, who are planning to read this book. There are $$$M$$$ days in a semester. The library opens every day for the entire semester, and the book is available from the beginning of the semester. The $$$i$$$-th student will visit the library the first time on day $$$b_i$$$ and will visit again on day $$$b_i + a_i, b_i + 2 \cdot a_i,\dots,b_i + x \cdot a_i$$$ where $$$1 \leq x$$$ and $$$b_i + x \cdot a_i \leq M$$$.
On day $$$d$$$, if a student visits the library and the book is available and the student has not read it before, the student borrows it and returns it exactly $$$c_i$$$ days later; that is, if the $$$i$$$-th student borrows the book on day $$$d$$$, it becomes available again on day $$$d + c_i$$$. If multiple students visit on the same day, the book is given to the student with the smallest number. A student may also borrow the book even if $$$d + c_i \gt M$$$, in which case the return is considered to happen after the $$$M$$$-th day.
For each student, print the day the student gets to borrow the book, or $$$-1$$$ if the student will not be able to borrow the book until the end of the semester.
The first line contains two integers, $$$N$$$ and $$$M$$$ — the number of students and the number of days in the semester. $$$(1 \leq N, M \leq 100,000)$$$
The next $$$N$$$ lines contain three integers, $$$a_i, b_i,$$$ and $$$c_i$$$ — the numbers for the $$$i$$$-th student visitation pattern stated in the problem statement, and the duration of the $$$i$$$-th student borrowing. $$$(1 \leq a_i, b_i, c_i \leq M)$$$.
Output one line with $$$N$$$ integers – the day student $$$1,2,3,\dots,N$$$ gets to borrow the book, or $$$-1$$$ if the student will not be able to borrow the book until the end of the semester.
3 104 2 33 4 15 2 1
2 7 -1
Sample Explanation
Student $$$1$$$ visited the library on days $$$2$$$, $$$6$$$, and $$$10$$$.
Student $$$2$$$ visited the library on days $$$4$$$, $$$7$$$, and $$$10$$$.
Student $$$3$$$ visited the library on days $$$2$$$ and $$$7$$$.
On day $$$2$$$, students $$$1$$$ and $$$3$$$ visited the library, but student $$$1$$$ had a lower number, so the book was borrowed by student $$$1$$$.
On day $$$4$$$, student $$$2$$$ visited, but the book was not available.
On day $$$5$$$, student $$$1$$$ returned the book. The book became available again, but it was not borrowed since no one visited the library that day.
On day $$$7$$$, students $$$2$$$ and $$$3$$$ visited the library, but student $$$2$$$ had a lower number, so the book was borrowed by student $$$2$$$.
On day $$$8$$$, student $$$2$$$ returned the book. The book became available again, but it was not borrowed since no one visited the library that day.
On day $$$10$$$, students $$$1$$$ and $$$2$$$ visited the library, but both of them had already read the book, so it was not borrowed.
After spending a long time collecting data and training his AI, Daeng confidently predicts that his mom will assign him $$$N$$$ household tasks to complete during the day.
Task $$$i$$$ is scheduled to take place during a specific time interval, starting at second $$$l_i$$$ and ending at second $$$r_i$$$ (inclusive). The task also has a karma value $$$k_i$$$. It is guaranteed that no two task intervals overlap with each other.
At the start of the day, Daeng's karma score is $$$0$$$. When the clock reaches the start time $$$l_i$$$ of a task, Daeng must make a choice:
In addition to household tasks, Daeng wants to enjoy his favorite game as many times as possible throughout the day. Each game session lasts exactly $$$M$$$ seconds. While Daeng is playing, he cannot work on tasks and must be continuous once started. Also, he can only have one gaming session at a time.
Time during the day is measured from second $$$0$$$ up to second $$$86{,}399$$$, making exactly one full day. Since each task interval includes both its starting and ending seconds, if a task ends at time $$$r$$$, Daeng is free to begin another activity at time $$$r+1$$$. For example, if a game begins at second $$$0$$$, it will finish at second $$$M-1$$$.
Find the maximum number of game sessions Daeng can have on the day.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10{,}000$$$, $$$1 \leq M \leq 86{,}400$$$) — the number of tasks and the duration of one game session in seconds.
Each of the next $$$N$$$ lines contains three integers $$$l_i,\; r_i,\; k_i$$$ ($$$0 \leq l_i \leq r_i \lt 86{,}400$$$, $$$1 \leq k_i \leq 20{,}000$$$) — the start time, end time, and karma value of the $$$i$$$-th task.
It is guaranteed that no task intervals overlap. That is, for any integer $$$i$$$ and $$$j$$$ between $$$1$$$ to $$$N$$$, if $$$i \neq j$$$, then $$$min(r_i, r_j) \lt max(l_i, l_j)$$$.
Also, $$$\sum_{i=1}^{N} k_i \leq 20{,}000$$$.
Print a single integer — the maximum number of game sessions Daeng can play during the day without violating the rules.
3 10 1 12 4 16 10 1
86395
10 71 2 23 7 110 11 312 13 315 16 318 21 523 23 124 25 526 30 531 33 2
12341
Sample explanation
In the first example, Daeng must do task 1 since he initially has no karma points. Then he can choose whether or not to do task 2. The optimal choice is to do task 2 and skip task 3.
A permutation of size $$$m$$$ is a sequence of $$$m$$$ positive integers containing each number from $$$1$$$ to $$$m$$$ exactly once. For example, $$$[1,4,5,3,2]$$$ is a permutation of size $$$5$$$, while $$$[1,1,4,3,5]$$$ and $$$[1,6,2,3,4]$$$ are not.
For an even-length sequence $$$[A_1, A_2, \ldots, A_{2t}]$$$, we define its power-product value ($$$\Lambda(A)$$$) as the product of terms obtained by taking each consecutive pair $$$(A_{2i-1}, A_{2i})$$$, raising the first element to the power of the second, and multiplying all such results together. Formally,
$$$$$$ \Lambda(A) = \prod_{i=1}^{t} A_{2i-1}^{\,A_{2i}} = (A_1^{A_2}) \cdot (A_3^{A_4}) \cdot (A_5^{A_6}) \cdot \ldots \cdot (A_{2t-1}^{A_{2t}}). $$$$$$
For example, if $$$A = (3,2,5,6,4,1)$$$, then $$$\Lambda(A) = 3^2 \cdot 5^6 \cdot 4^1 = 562500$$$
Next, we define a halting zero value of a number as equal to how many trailing zeros an integer has. For a positive integer $$$x$$$, let the halting zero function $$$\mho_0(x)$$$ be the number of zeros at the end of its decimal representation. Formally:
$$$$$$ \mho_0(x) = \max \{ k \in \mathbb{Z}_{\geq 0} : 10^k \mid x \}. $$$$$$
For example, $$$\mho_0(12000) = 3, \mho_0(907) = 0$$$
Your task is to find $$$ \max_{P} \mho_0(\Lambda(P))$$$ when $$$P$$$ is a permutation of size $$$2N$$$. Because the answer may be extremely large, output the result modulo $$$10^9+7$$$.
The first line contains a single integer $$$T$$$ — the number of test cases. $$$(1 \le T \le 1000)$$$
Each of the next $$$T$$$ lines contains a single integer $$$N$$$. $$$(1 \le N \le 10^{12})$$$
For each test case, output a single integer — the maximum value of $$$\mho_0(\Lambda(P))$$$ modulo $$$10^9+7$$$.
423513
0 6 17 142
For $$$N = 3$$$ : Let $$$P = (5,6,4,3,2,1)$$$, then $$$\mho_0(\Lambda(P)) = \mho_0(5^6 \cdot 4^3 \cdot 2^1) = \mho_0(2,000,000) = 6$$$, which is the maximum value.
For $$$N = 5$$$ : Let $$$P = (4,2,3,6,5,9,1,7,10,8)$$$, then $$$\mho_0(\Lambda(P)) = \mho_0(4^2 \cdot 3^6 \cdot 5^9 \cdot 1^7 \cdot 10^8)$$$ $$$= \mho_0(2,332,800,000,000,000,000,000) = 17$$$, which is the maximum value.
The lord has vanished without a trace.
Inside a secluded castle, the royal family gathered to claim his inheritance. One by one, they perished—locked rooms, vanished alibis, headless corpses—until only two remained: Ange and Beatrice.
The lord's will was sealed within an epitaph. It was said that whoever deciphered it would become the rightful heir. Ange solved the riddle... but only a moment too late. At the end of the path, Beatrice was already waiting with a smile.
The inheritance is the family estate: a convex polygon within which stand two ancient landmarks. Yet Beatrice, in her magnanimity, offered Ange a chance to share the rule. The land will be divided by the following ritual:
Beatrice, having arrived first, always claims the larger half. Ange receives the smaller one.
Your task is to compute the expected difference in area between Beatrice's region and Ange's region.
Let $$$P = 10\,000\,000\,019$$$. P is a prime number. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0 \pmod P$$$. Output the integer equal to $$$x\cdot y^{-1} \pmod P$$$. In other words, output such an integer $$$a$$$ that $$$0 \le a \lt P$$$ and $$$a\cdot y=x \pmod P$$$.
The first line contains a single integer $$$N$$$ — the number of vertices of the polygon $$$(3 \leq N \leq 10^5)$$$.
Each of the next $$$N$$$ lines contains two integers $$$x_i, y_i$$$ $$$(-10^9 \leq x_i, y_i \leq 10^9)$$$, representing the coordinates of the polygon's vertices, given in clockwise order. The polygon is guaranteed to be convex , and no three consecutive vertices are collinear.
The last line contains four integers $$$x_p, y_p, x_q ,y_q$$$ $$$(-10^9 \leq x_p, y_p, x_q ,y_q \leq 10^9)$$$, representing the coordinates of the two landmarks, one at $$$(x_p,y_p)$$$ and another at $$$(x_q,y_q)$$$, which both are guaranteed to lie strictly inside the polygon.
Print the answer modulo $$$10\,000\,000\,019$$$ in a single line. If it is impossible to select the chord to fit the criteria, print $$$-1$$$.
70 0-1 21 55 46 15 -12 -23 4 3 1
11
60 54 36 02 -10 0-1 31 0 0 1
5000000010
310 00 05 103 1 7 3
-1
The polygon in the first test case can be visualized as follows:
Figure L.1: The polygon showing the two landmarks (inside points) and all chords that successfully separate them. Depending on the language, the expected difference or other intermediate values can exceed the range of 32-bit or even 64-bit integers in worst cases. To avoid overflow: