Alchemy has long struggled in its most basic objective of turning lead into gold. This changed when Pyoorfan Dahlai Lahm, while working in her laboratory in Behl, discovered a catalytic element that made this transmutation much easier. This was a great accomplishment, so this element was named Dahnium in honor of Dahlai. To this day, we commemorate Dahlai even in the name of our country, Lahm Dah.
As a first-class citizen of Lahm Dah, you are of course familiar with the ten basic elements, or the ten different Tai. There are the classical Tai, which are Air, Water, Earth, and Fire. Then there are the metallic Tai, which consist of Copper, Mercury, Gold, Iron, Iodine, and Dahnium. We refer to these Tai by the first letter of their Alchemical Names, which are Aqua (Water), Breath (Air), Copper, Dahnium, Earth, Fire, Gold, Hydrargyrum (Mercury), Iron, and Jodium (Iodine).
This is the second week of your internship at Behl Labs. Like many alchemical companies, Behl Labs is situated in a classroom in the Lahm Dah Institute of Technology. Your job is to transform Tai into other Tai by applying a series of Kshons. In her time, Dahlai discovered two kinds of Kshons, which are named Pyoorfan Kshons in her honor:
1. Ankoray. In the process of Ankoraying, one Tai is turned into two of the same kind of Tai. For example, the Kshon C -> CC takes a single Copper as input, and turns it into two Coppers.
2. Pkast. One Tai can be converted into any kind of Tai through a process called Tai Pkasting. For example, the Kshon E -> * takes a single Earth as input, and turns it into any single Tai, including Earth itself.
A Kshon is extremely fragile, which is why it takes training to use them. Even with extreme care, a Kshon can only be used once, and once a Kshon is used, it cannot be used again. Because they are needed in large supply throughout the nation of Lahm Dah, special factories construct these Kshons and deliver the results to classes everywhere.
Today, your boss is unable to provide you with your usual supply of Kshons, which you suppose is a side effect of some higher-order unresolved arguments. So you need to plan the sequence of Kshons you want to use very carefully, if you do not want to be garbage collected.
You know how many of each Tai you have, and which Kshons are available. You now wonder: what is the maximum number of each Tai you can make? Since you are too lazy to evaluate this by hand, please write a program to answer this question.
The first line of input contains ten space-separated integers, $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$, $$$E$$$, $$$F$$$, $$$G$$$, $$$H$$$, $$$I$$$, and $$$J$$$ which are the number of Tai you have of Aqua, Breath, Copper, Dahnium, Earth, Fire, Gold, Hydrargyrum, Iron, and Jodium you have, respectively.
The second line of input contains one integer, $$$K$$$, the number of distinct Kshons you have.
The next $$$K$$$ lines of input each contain a positive integer $$$N$$$, followed by a space, followed by a Kshon, written in the form "x -> y" (without quotes). This represents $$$N$$$ Kshons, each that take x as input, and turns it into y. Here,
Output one line of ten space-separated integers, which are the maximum number of Aqua, Breath, Copper, Dahnium, Earth, Fire, Gold, Hydrargyrum, Iron, and Jodium you can make with your Kshons. Each number is independent of all the other ones.
For all subtasks
$$$0 \le A, B, \ldots, J, K, N \le 10^{12}$$$
$$$N$$$ is positive.
No two of the $$$K$$$ distinct Kshons are the same.
Subtask 1 (10 points): All Kshons are Ankoray.
Subtask 2 (10 points): All Kshons are Pkast.
Subtask 3 (16 points): The sum of all $$$N$$$s in the file is at most $$$10$$$.
Subtask 4 (11 points): No Kshon has D, E, F, G, H, I, or J as input.
Subtask 5 (9 points): No Kshon has E, F, G, H, I, or J as input.
Subtask 6 (16 points): No Kshon has G, H, I, or J as input.
Subtask 7 (12 points): No Kshon has I or J as input.
Subtask 8 (16 points): No additional restrictions.
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 3 2 A -> * 2 B -> * 1 B -> BB
4 3 3 3 3 3 3 3 3 3
The first sample case is valid for all subtasks. The second sample case is not valid for the first two subtasks, and valid for the remaining subtasks.
In the first sample case, we have no Tai and no Kshons, so we can't produce anything. (Alchemy is yet to discover how to produce something out of nothing.)
In the second sample case, we can produce four Aqua through the following process:
The two Aqua in the last step, combined with the two remaining original Aqua, are four Aqua in total. There is one remaining A -> * Kshon that we did not use.
Similarly, this process produces three Dahnium:
At the end of the process, there is one Aqua and three Dahnium, but only the number of Dahnium matters. Similarly, we can produce three Breath, Copper, Earth, Fire, Gold, Hydrargyrum, Iron, and Jodium.
Note that the process "resets" for different Tai. Each process is independent of the other ones. It can also be shown that these are the maximum number of each Tai that can be made by any series of Kshons.
Society would have you believe that being good at the sciences and being good at the arts are mutually exclusive. The "left-brained" and "right-brained" myth is still spread in many schools throughout the world. They would have you think that each person is either good at science and bad at art or good at art and bad at science. This is not true! In reality, a majority of the people in this world are bad at science and bad at art. But that's okay! The real takeaway is that whether or not you are objectively good at something, there is inherent value to pursuing what you are passionate in. Ding Ding is one such person who is neither good at science nor art. Still, he wants to combine both together to create a super cool science-art project!
Ding Ding has three transparent sheets of acrylic, each of which can be divided into a grid with $$$r$$$ rows and $$$c$$$ columns. All types of light pass through this material with no effect. Ding Ding plans to paint some of the cells in each sheet with a special kind of paint that acts as a light filter. When normal light passes through a painted cell, it becomes polarized; when polarized light passes through a painted cell, it becomes normal light again. For his art project, Ding Ding will layer the three sheets of acrylic, one on top of another. Ding Ding shines parallel rays of light at the sheets, and each ray of light passes through the corresponding overlaid cells in the first, then second, then third sheet, before exiting. Ding Ding plans to paint the cells in such a way that if all light that enters the sheets is normal, then all light that exits should be normal as well.
Ding Ding understands that there are many ways to paint the three sheets such that this condition holds. He devises the following formula for computing the beauty of a given project.
Ding Ding measures the beauty of the project in terms of the maximum number of regions that each sheet can be partitioned into. A region is simply a nonempty set of unpainted cells. A partition of a given sheet into regions is considered valid if (and only if) all of the following are satisfied:
The size of a partition is simply the number of regions in it.
Let $$$x_1$$$ be the maximum size of any valid partition of the first sheet into regions; define $$$x_2$$$ and $$$x_3$$$ similarly for the second and third sheets, respectively.
Ding Ding now defines the beauty of a given project as $$$\max(0, \min(2, S))$$$, where $$$S$$$ is computed using the following formula: $$$$$$S = \frac{8\min(x_1, x_2, x_3) - 2\max(x_1, x_2, x_3)}{rc - 3}$$$$$$
Ding Ding has already finished this project $$$50$$$ different times with different values of $$$r$$$ and $$$c$$$ for his exhibit. Now, it's your turn—Ding Ding challenges you to make an exhibit with the same $$$50$$$ values of $$$r$$$ and $$$c$$$ and to make it as beautiful as possible.
The first line of input contains a single integer $$$t$$$. The following $$$t$$$ lines describe the test cases.
Each test case consists of a single line containing two space-separated integers $$$r$$$ and $$$c$$$.
For each test case, output $$$3r+3$$$ lines.
Each of the first $$$r$$$ lines must contain exactly $$$c$$$ characters representing a row of the first sheet. The $$$j$$$th character of the $$$i$$$th row represents the state of the cell at the $$$i$$$th row and $$$j$$$th column and must be either:
After the said $$$r$$$ lines, output a single line containing a single dash character, -.
The next $$$r+1$$$ lines must describe the second sheet and must be in the same format as the first sheet. Then the $$$r+1$$$ lines after that must describe the third sheet and must be in the same format as the first sheet.
$$$t = 50$$$.
The test cases are all distinct.
For each pair $$$(r, c)$$$, exactly one of the following is true:
Your score will be the sum of the beauties of your outputs across all cases. Since the maximum beauty is $$$2$$$, the maximum possible score is $$$100$$$ points.
If your output is invalid for a case, then it is considered to be an output with $$$0$$$ beauty. If your output cannot be interpreted properly as a list of answers for $$$t$$$ test cases, then your score will be $$$0$$$ overall.
Note that your score is rounded down to the nearest integer, so in particular, you can only get a score of $$$100$$$ if you obtain a beauty of $$$2$$$ for all $$$50$$$ cases.
1 5 6
..#... ..#... ###... ...... ...... - ...... ...... ...### ...#.. ...#.. - ..#... ..#... ###### ...#.. ...#.. -
Note: This sample I/O doesn't follow the constraints and so will not appear in the input.
Note that:
Therefore, $$$$$$S = \frac{8\cdot 2 - 2\cdot 4}{5\cdot 6 - 3} = 0.296296\ldots$$$$$$
so the beauty is $$$\max(0, \min(S, 2)) = 0.296296\ldots$$$ Note that a line containing a single dash (-) must be printed after each sheet, including the last one.
A Filipino proverb says: Kapag may tiyaga, may nilaga. Researchers and scholars have tried to find meaning in this proverb. Finally, they all agreed:
If one works hard to explore the forests north of Havana, one can find the Shrine of The Nilagang Saging.
A bunch of people tried to discredit their research by claiming that the researchers were going bananas, it was later found out that the scholars were correct. A shrine devoted to bananas really did exist!
In the Shrine of The Nilagang Saging, there are $$$n$$$ banana pieces indexed from $$$1$$$ to $$$n$$$. The $$$i$$$th banana piece has length $$$a_i$$$ centimeters. The number $$$a_i$$$ is a positive integer.
Legend has it that chopping the banana pieces in the correct way can earn you a fortune. However, chopping them in another way can cost you a fortune. Before chopping, one must first insert their bank card in the appropriate slot. The game then begins.
Let $$$c$$$ be a fixed integer. During the game, one can perform the following action a non-negative number of times:
Choose one of the banana pieces. Chop it into exactly two banana pieces, both having positive integer lengths of your choice. If the two banana pieces have lengths $$$b_1$$$ and $$$b_2$$$, respectively, then you earn $$$b_1b_2(b_1 + b_2 − c)$$$ pesos for doing this. Note that the sum $$$b_1 + b_2$$$ should be equal to the length $$$b$$$ of the original banana piece. If this value is negative, then its absolute value is deducted from your bank account instead.
You can quit the game at any time by removing your bank card from the slot. Of course, if there are no more valid moves, you must quit the game. What is the maximum number of pesos you can earn from this game?
The first line of input contains a single integer $$$t$$$, the number of test cases. Each test case is described with two lines.
The first line of each test case contains two space-separated integers $$$n$$$ and $$$c$$$, the number of banana pieces and the constant $$$c$$$ for this game.
The second line of each test case contains $$$n$$$ space-separated integers $$$a_1, a_2 \dots a_n$$$, the lengths of each of the banana pieces.
For each test case, output a line containing a single integer, the answer for that test case. Since it can be quite large, output it modulo $$$10^9+7$$$.
Let $$$A$$$ be the max value of $$$a_i$$$ for a particular test case.
For all subtasks
$$$1 \le t \le 10^5$$$
$$$1 \le n \le 10^5$$$
$$$1 \le c \le 10^6$$$
$$$1 \le a_i \le 10^{18}$$$
$$$1 \le a_i \cdot c^2 \le 10^{18}$$$
The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
Subtask 1 (7 points):
$$$a_i \leq 10$$$
$$$t \leq 20$$$
Subtask 2 (25 points):
The sum of $$$A$$$ over all test cases is $$$\leq 1000$$$.
Subtask 3 (12 points):
The sum of $$$A$$$ over all test cases is $$$\leq 10^5$$$.
Subtask 4 (10 points):
The sum of $$$n$$$ over all test cases does not exceed $$$400$$$.
$$$a_i \leq 10^9$$$
Subtask 5 (10 points):
$$$c \leq 2$$$
Subtask 6 (8 points):
The sum of $$$n$$$ over all test cases does not exceed $$$400$$$.
The sum of $$$c$$$ over all test cases does not exceed $$$10^4$$$.
Subtask 7 (8 points):
The sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.
Subtask 8 (10 points):
$$$a_i \leq 10^6$$$
Subtask 9 (10 points):
No further constraints.
2 3 4 5 7 2 1 1 3
42 5
Kenya North is running for president! The country needs change, and Kenya insists that music will make this happen. However, the elections are coming up, and he needs to solidify his campaign and gain support.
To increase his chances of winning, Kenya composed two presidential songs. The songs $$$A$$$ and $$$B$$$ are $$$n$$$ and $$$m$$$ seconds long, respectively. Each second of these songs has a single note, denoted by $$$A_1, ..., A_n$$$ and $$$B_1, ..., B_m$$$. We label notes with positive integers.
Kenya plans on parading the streets while playing both songs at the same time on infinite loop. They are initially played from the start at the same time. In other words, we extend the sequences $$$A$$$ and $$$B$$$ into the following infinite (periodic) sequences:
In other words, for all positive integers $$$i$$$, $$$A_i = A_{i+n}$$$ and $$$B_i = B_{i+m}$$$.
Of course, $$$n$$$ and $$$m$$$ could be different, so the songs don't necessarily align after the first playing. For example, if song $$$A$$$ has length 4 and contains the notes $$$101, 192, 103, 259$$$ and song $$$B$$$ has length $$$6$$$ and contains the notes $$$134, 77, 66, 141, 52, 78$$$, then the song notes align in the following way: $$$$$$\begin{array}{rrrrrrrrrrrrrr} \text{Song $1$:}& 101 & 192 & 103 & 259 & 101 & 192 & 103 & 259 & 101 & 192 & 103 & 259 & \ldots \\ \text{Song $2$:}& 134 & 77 & 66 & 141 & 52 & 78 & 134 & 77 & 66 & 141 & 52 & 78 & \ldots \\ \end{array}$$$$$$
Your campaign manager and DJ, Musky Melon, notices that there are certain times when more people are listening. It's at times like those that you need to drop the beat! Define the level of the beat drop of a certain segment of time to be the sum of the absolute differences between the corresponding notes of $$$A$$$ and $$$B$$$ during the duration of the beat drop. More formally, if the beat drop lasts from time $$$s$$$ to time $$$t$$$, then the level of the beat drop is: $$$$$$|A_s - B_s| + \ldots + |A_t - B_t|.$$$$$$
For this measure, the lower the better! You want the beat drop level to be as low as you can. To do this, Kenya can use his specialty—autotuning—to adjust the notes of each song. For each beat drop, he chooses an integer $$$x$$$ and then he either increases or decreases all notes of $$$A$$$ by $$$x$$$. Similarly, he also chooses an integer $$$y$$$ and then he either increases or decreases all notes of $$$B$$$ by $$$y$$$. He does this so that the level of the beat drop is minimized. Note that $$$x$$$ and $$$y$$$ must be chosen so that all of the notes of $$$A$$$ and $$$B$$$ after autotuning are still positive integers.
You are given the notes of the songs $$$A$$$ and $$$B$$$. For each time duration Musky Melon drops the beat, determine the lowest beat drop level.
The first line contains a single integer $$$t$$$ denoting the number of test cases.
The first line of each test case contains a single integer $$$n$$$ followed by a line with $$$n$$$ space-seperated integers $$$A_1, A_2, ..., A_n$$$. Similarly, the third line contains a single integer $$$m$$$ followed by a line with $$$m$$$ space-seperated integers $$$B_1, B_2, ..., B_m$$$.
The next line contains $$$q$$$, the number of time segments Musky Melon wants to drop the beat. $$$q$$$ lines follow, the $$$i$$$th line describing a query containing two space-seperated integers, $$$s_i$$$ and $$$t_i$$$, denoting the start and end time of the beat drop, inclusive.
For each time duration, output a single line containing the minimum beat drop level for that time duration.
Here, let
For all subtasks
$$$1 \le t \le 30$$$
$$$1 \le n, m, N, M \le 60000$$$
$$$1 \le q \le 3$$$
$$$1 \le s_i \le t_i \le 10^{12}$$$
$$$1 \le A_k, B_k \le 10^6$$$
Subtask 1 (11 points):
$$$1 \le n, m, N, M \le 400$$$
$$$1 \le s_i \le t_i \le 10^3$$$
Subtask 2 (10 points):
$$$1 \le s_i \le t_i \le 75000$$$
Subtask 3 (26 points):
$$$1 \le n, m, N, M \le 400$$$
Subtask 4 (31 points):
$$$1 \le n, m, N, M \le 30000$$$
$$$n$$$ and $$$m$$$ do not have any common factors other than $$$1$$$
Subtask 5 (9 points):
$$$n$$$ and $$$m$$$ do not have any common factors other than $$$1$$$
Subtask 6 (8 points):
$$$1 \le n, m, N, M \le 30000$$$
Subtask 7 (5 points):
No further restrictions.
2 4 101 192 103 259 6 134 77 66 141 52 78 3 1 3 2 7 129 129 10 201 119 47 175 90 12 253 82 179 8 9 236 128 175 152 68 167 55 182 199 3 176 195 73 258 26 227
148 292 0 1635 15081 16486
3 4 101 192 103 259 6 134 77 66 141 52 78 2 53 1271 3 12 10 201 119 47 175 90 12 253 82 179 8 9 236 128 175 152 68 167 55 182 199 3 103 202 45 95 49 77 10 201 119 47 175 90 12 253 82 179 8 9 236 128 175 152 68 167 55 182 199 2 72 181 52 158
66247 505 7822 4077 2395 8825 8692
The first sample case is valid for subtasks $$$1$$$, $$$2$$$, $$$3$$$, $$$6$$$ and $$$7$$$.
The second sample case is valid for subtasks $$$2$$$, $$$3$$$, $$$6$$$ and $$$7$$$.
The following content describes a haunting future that may yet come to pass. Reader's discretion is advised.
It is the year 20XX. You have sold your soul to Big Corporation (BgC). It has been decades since you have seen a whimsical, silly problem statement from NOI.PH. Gone are the days of dancing spaghetti and magic zapping pineapples. Now, all you do is make spreadsheets about monthly expenses and file financial reports to your manager. The only programming language you remember using in recent memory is Excel (though sometimes you make a macro in Visual Basic, just to feel alive again).
This is the darkest timeline.
There are $$$n$$$ departments in the company you work for, creatively labeled $$$1, 2, \dots, n$$$. It is very rare for anyone to do their own paperwork in this company. If a form is sent to department $$$i$$$, it will be redirected and sent to department $$$p_i$$$ in the following morning. Of course, then that department will redirect the paperwork again the morning after that, and so on. Nothing ever gets done around here—such is the nature of bureaucracy. Also, note that each $$$p_i$$$ is fixed and will never change, since large corporations love preserving the status quo. On occasion, it is possible that $$$p_i = i$$$, but the paperwork never actually gets done; it just gets endlessly redirected back to the same department, day after day.
Is this... starting to sound like a programming problem...?
The most interesting thing to have happened in the office lately is that your boss was mad that a very important piece of paperwork was sent to one of the departments, and rather than being sent directly to him, it got bounced around and forwarded between different departments until someone realized it was actually important. It was something about tax exemptions? In any case, whichever department first received that paperwork is going to be put on the firing squad. Luckily for them, all the redirecting has made it somewhat hard to track the paperwork's original recipient. Office gossip is vague, so you could only gleam the following details.
This sounds like it could be an interesting algorithmic puzzle... You feel... something stirring from within...
You realize it might be an interesting question to ask: Given $$$s_1, s_2, \dots s_d$$$, and $$$r_1$$$ and $$$r_2$$$, what is the set of all possible departments where the important paperwork could have originally been sent to? Since that could possibly be a lot, output the sum of the squares of their labels, instead. Also, you wonder if it is possible to answer $$$q$$$ different queries of this type.
This is your chance to change a future that does not have to be. Answer this problem correctly and you will reignite the spark of passion that competitive programming once brought you. Fail, and you will succumb to life as a corporate drone, forever wondering about a life that could have been.
The first line of input contains $$$t$$$, the number of test cases.
The first line of each test case contains two space-separated integers $$$n$$$ and $$$q$$$.
The second line of each test case contains $$$n$$$ space-separated integers $$$p_1, p_2, \ldots, p_n$$$.
The next $$$2q$$$ lines describe the queries. Each query is described by two lines. The first line of the $$$k$$$th query contains three space-separated integers $$$r_1$$$, $$$r_2$$$ and $$$d$$$. The second line contains $$$d$$$ space-separated integers $$$s_1, s_2, \ldots, s_d$$$.
For each query, output a single line containing a single integer denoting the answer for that query, which is the sum of the squares of the labels of the possible departments where the important paperwork could have originally been sent to.
For all subtasks
$$$1 \le t \le 10$$$
$$$1 \le n, q \le 250000$$$
The sum of all $$$n$$$s across all cases in a single file is $$$\le 250000$$$.
The sum of all $$$q$$$s across all cases in a single file is $$$\le 250000$$$.
The sum of all $$$d$$$s across all cases in a single file is $$$\le 250000$$$.
$$$0 \le r_1 \le r_2 \le 10^9$$$
$$$1 \le d \le n$$$
$$$1 \le p_i \le n$$$
$$$1 \le s_i \le n$$$
The $$$s_i$$$s are distinct for each query.
Subtask 1 (10 points):
$$$n, q \le 300$$$
$$$r_2 \le 300$$$
The sum of the $$$d$$$s across a single test case is $$$\le 300$$$.
Subtask 2 (15 points):
$$$n, q \le 300$$$
The sum of the $$$d$$$s across a single test case is $$$\le 300$$$.
Subtask 3 (15 points):
$$$n, q \le 3000$$$
The sum of the $$$d$$$s across a single test case is $$$\le 3000$$$.
Subtask 4 (16 points):
$$$r_1 = r_2$$$
$$$d = 1$$$
Subtask 5 (15 points):
$$$r_1 = r_2$$$
Subtask 6 (9 points):
$$$d = 1$$$
Subtask 7 (20 points):
No additional constraints.
1 4 4 3 1 1 4 3 3 1 1 3 3 2 1 2 2 3 2 1 3 2 3 4 1 2 3 4
13 13 14 30