On National Chunky Turnip day, Ian Zhang has decided to bless some of his $$$n$$$ fanclubs around the country with his presence. The $$$i$$$-th fanclub is located at $$$x_i$$$ and has $$$m_i$$$ members ($$$1 \le m_i \le 2$$$). The location of each fanclub is distinct from all other fanclubs.
Ian is only able to teleport in the positive direction. In addition, since he is busy doing great geniosity things, after he visits a fanclub with two members, he can only visit fanclubs with two members from then on.
Ian starts off his journey at the Lexington High School Chunky Turnips Fanclub, which is located at point $$$0$$$ and has $$$1\,000\,000\,000$$$ members. Please help him find the maximum number of fanclub members he can visit.
The first line contains $$$n$$$ ($$$1 \le n \le 10^3$$$).
The following $$$n$$$ lines each contain $$$2$$$ integers $$$x_i$$$ and $$$y_i$$$, the position of each fanclub and the number of members ($$$1 \le x_i \le 10^5$$$, $$$1 \le y_i \le 2$$$).
Output a single integer that is the maximum number of fanclub members that Ian can visit.
5 3 1 4 1 5 1 2 2 6 2
1000000005
In the first test, it is better to skip the first fanclub with two members at point $$$2$$$, and instead aim for the three fanclubs with one member at $$$3, 4$$$ and $$$5$$$ before visiting the fanclub at point $$$6$$$. This reaches a total of $$$5$$$ members in addition to the $$$1\,000\,000\,000$$$ members at point $$$0$$$.
Farmer John is going to lunch with his six favorite cows: Alfred, Bessie, Codetigerorz, Dennis, Elsie, and Fran!
The meal cost $$$n$$$ dollars in total. FJ brought along several coins to pay. Specifically, for all $$$1 \le x \le 5$$$, he has $$$a_x$$$ coins which are worth $$$x$$$ dollars each.
The cows want to practice their English, so FJ needs to find a way to distribute coins to the cows in a way such that:
- Each cow receives exactly one coin.
- The sum of values of the coins the cows have is exactly $$$n$$$ dollars.
Note that FJ may have coins left over, or that it may be impossible to distribute coins in a way satisfying the conditions (for example, if FJ only has a single $$$1$$$-dollar coin, and the meal costs $$$5$$$ dollars).
Help FJ count the number of ways to distribute coins to the cows! Two ways are considered different if at least one of the cows is given a coin of a different value.
The first line contains $$$n$$$, the total amount Farmer John needs to pay ($$$6 \le n \le 30$$$).
The second line contains $$$5$$$ integers describing how many coins of each type FJ has ($$$0 \le a_i \le 6$$$).
Print the number of ways that the cows can pay $$$n$$$ dollars in total.
8 6 2 3 4 1
21
In the first test:
- There are $$$6$$$ ways to give one of the cows a $$$3$$$-dollar coin and the rest $$$1$$$-dollar coins.
- There are $$$15$$$ ways to give two of the cows a $$$2$$$-dollar coin and the rest $$$1$$$-dollar coins.
We can show that these are the only possible ways to make $$$8$$$ dollars with the given coins, so we output $$$6+15=21$$$.
After giving a super kind shout out to LIT and the Tetris game night during the Berkeley CALICO Fall 2022 contest, Spiralsim forgot to mention that he himself is ranked 65 in the entire US on TETR.IO! Engorged by envy of Spiralsim's greatness, CodeTiger machinates a devilish plan — proposing another game night for LIT to stop Spiralsim from winning. He conspired with Berkeley's long-time rival, the Stanford tree mascot, and created a brand new game called tree folding. Inspired by the popular game (2048), CodeTiger recreates it on a tree.
A tree is an undirected unweighted connected graph with $$$n$$$ vertices and $$$n-1$$$ edges.
Consider a Stanford tree with $$$n$$$ vertices. For all $$$1 \le i \le n$$$, the $$$i$$$-th vertex has a number written on it, denoted $$$a_i$$$. Initially, all $$$a_i$$$ are $$$0$$$. You are allowed to perform the following fold operation:
- Choose an edge $$$(u,v)$$$ such that $$$a_u = a_v$$$. Delete this edge, and combine $$$u$$$ and $$$v$$$ into a single new vertex $$$x$$$, with $$$a_x = a_u + 1$$$. All vertices that were connected by an edge to either $$$u$$$ or $$$v$$$ are now connected to $$$x$$$.
Informally, you can think of it like playing 2048 on a tree.
A tree is called good if it is possible to perform this operation repeatedly and end up with a single node. For example, a line graph on $$$4$$$ vertices is good because you can perform these operations:
Now, you are given a tree which initially consists of a single node, and $$$q$$$ queries. In the $$$i$$$-th query ($$$1 \le i \le q$$$), you are given an integer $$$x_i \le i$$$, meaning you should create a new node labeled $$$i+1$$$, and connect it with an undirected edge to node $$$x_i$$$. After each update, determine if the resulting tree is good.
Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 3 \cdot 10^5$$$).
The first line of each test contains $$$q$$$, the number of queries ($$$1 \le q \le 3 \cdot 10^5$$$).
The second line contains $$$q$$$ integers $$$x_1, x_2, \ldots, x_q$$$ ($$$1 \le x_i \le i$$$).
It is guaranteed the sum of $$$q$$$ over all tests does not exceed $$$3 \cdot 10^5$$$.
For each query, output either YES or NO.
- In tests worth $$$30$$$ points, it is guaranteed that the sum of $$$q$$$ over all tests does not exceed $$$300$$$.
- In tests worth a further $$$20$$$ points, it is guaranteed that the sum of $$$q$$$ over all tests does not exceed $$$5\,000$$$.
431 2 31171 1 3 2 2 1 531 1 1
YES NO YES YES YES NO YES NO NO NO YES YES NO NO
In the first test, we build a line graph of size $$$4$$$, like shown in the statement. We can show that line graphs of size $$$2$$$ and $$$4$$$ are good, while those of size $$$3$$$ are not.
Similarly, in the second test, we construct a line of size $$$2$$$.
In the third test, here is a picture of the final graph (which turns out to be good):
Yalikesi just took a trip to Hillington, a city so hilly that you're either walking uphill or downhill, with no in-between! Being an avid land surveying fan, Yalikesi brought his equipment to create an elevation map of the city, but limited time meant he was only able to calculate the elevation at a few locations.
Hillington can be represented by a $$$n$$$-by-$$$n$$$ grid. The tile in the $$$i$$$-th row and $$$j$$$-th column of the grid has an integer height, denoted $$$h_{i,j}$$$. For each cell, Yalikesi either knows the exact value of its height, or has not measured it yet.
A valid completion of Yalikesi's observations is a $$$n$$$-by-$$$n$$$ grid, denoted $$$a$$$, satisfying both the following:
- The heights of any two adjacent cells in $$$a$$$ differs by exactly $$$1$$$.
- For all $$$h_{i,j}$$$ which have been measured, $$$a_{i,j} = h_{i,j}$$$.
Note that $$$a_{i,j}$$$ does not necessarily have to be positive.
A cell $$$(i,j)$$$ is said to be uniquely determined if the integer in it is the same across all valid completions.
You need to find all uniquely determined cells in $$$h$$$, and report the integers in them.
Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).
The first line of each test contains $$$n$$$, the size of the grid ($$$1 \le n \le 500$$$).
The next $$$n$$$ lines contain $$$n$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line, which we denote $$$b_{i,j}$$$, represents the value of $$$h_{i,j}$$$.
- If the height of cell $$$(i,j)$$$ is unknown, then $$$b_{i,j} = 0$$$.
- Otherwise, $$$b_{i,j}$$$ will be a positive integer, the height of that cell ($$$1 \le b_{i,j} \le 10^9$$$).
Note that $$$h_{i,j}$$$ for unmeasured cells do not have to be positive, and may be greater than $$$10^9$$$.
It is guaranteed the sum of $$$n^2$$$ over all tests does not exceed $$$250\,000$$$.
It is guaranteed that at least one valid completion exists, and that the height of at least one cell is known.
For each test, output $$$n$$$ lines containing $$$n$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line represents the cell $$$(i,j)$$$. If it is uniquely determined, output its height. Otherwise, output 0.
We can show that under the constraints of the problem, any uniquely determined cell will have a nonzero value.
Note that in the sample tests, a newline is printed between test cases. This is only for ease of reading, and you do not need it in your solution.
550 0 0 0 00 0 0 6 00 0 0 0 03 0 0 0 00 1 0 0 0199932 1 21 0 12 1 260 8 9 8 7 88 7 8 9 8 79 8 0 8 0 88 7 6 7 8 90 6 7 8 9 00 7 6 7 8 02999999999 10000000001000000000 0
0 0 0 0 0 0 4 5 6 0 0 3 4 5 0 3 2 3 4 0 2 1 2 3 0 999 2 1 2 1 0 1 2 1 2 0 8 9 8 7 8 8 7 8 9 8 7 9 8 7 8 0 8 8 7 6 7 8 9 7 6 7 8 9 0 0 7 6 7 8 0 999999999 1000000000 1000000000 0
In the first test, here are two possible valid completions of the grid:
Note that the cells in red are all different between the two grids, therefore they cannot be uniquely determined.
In this case, it also happens that the rest of the cells are the same across all valid completions, so they are uniquely determined.
In the second case, note that the grid may already have all heights measured.
In the third case, the square in the center can be either $$$0$$$ or $$$2$$$. $$$a_{i,j}$$$ does not necessarily have to be positive, so this square is not uniquely determined.
Bessie's grades this year are... questionable.
The school year is divided into two semesters. Bessie's scores on assignments in each semester can be represented as integer sequences $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_m$$$ of length $$$n$$$ and $$$m$$$ respectively.
Bessie's grade for a semester is the average of all her scores in that semester. Her overall grade is the average of her semester grades. Here, the average of an integer sequence $$$x_1, x_2, \ldots, x_l$$$ of length $$$l$$$, is $$$\frac{x_1+x_2+\ldots+x_l}{l}$$$. Note that this value may not necessarily be integer.
Bessie has hacked into the school's computers, and can do the following operation at most $$$k$$$ times without raising suspicion:
- Choose a single score from one of the semesters, and move it to the other.
At the end, both semesters should have at least one score. Help Bessie find the maximum overall grade she can achieve!
Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).
The first line of each test contains $$$n$$$, $$$m$$$, and $$$k$$$ — the number of scores in each semester, and the maximum number of operations ($$$1 \le n, m \le 10^5$$$, $$$0 \le k \le n+m$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, Bessie's scores in the first semester ($$$1 \le a_i \le 10^9$$$).
The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$, Bessie's scores in the second semester ($$$1 \le b_i \le 10^9$$$).
It is guaranteed the sum of $$$n + m$$$ over all tests does not exceed $$$2 \cdot 10^5$$$.
For each test, output a floating-point number, the maximum overall grade Bessie can achieve.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
In tests worth $$$50$$$ points, it is guaranteed that $$$1 \le n, m \le 100$$$.
32 5 06 11 1 1 1 12 5 16 11 1 1 1 16 9 49 2 15 1 13 1110 3 4 7 5 8 6 14 12
2.25 3.5 10.538461538461538
In the first test, Bessie can't do anything. So her grade for the first semester is $$$\frac{6+1}{2}=3.5$$$, and her grade for the second semester is $$$\frac{1+1+1+1+1}{5} = 1$$$. Averaging these gives an overall grade of $$$\frac{1+3.5}{2}=2.25$$$.
In the second test, it is optimal to move the score of $$$1$$$ in the first semester to the second semester. Then, the averages for each semester become $$$6$$$ and $$$1$$$, resulting in an overall grade of $$$\frac{6+1}{2}=3.5$$$.
This is the easy version of the problem. The problems differ in their constraints and input formats. A solution to one may not work for the other.
Kanako-chan loves Hime-chan secretly, so she wants to give her as much coffee as possible (Hime is a caffeine addict). There are $$$n$$$ types of coffee numbered from $$$1$$$ to $$$n$$$, but Hime is only interested in type $$$1$$$.
Kanako was offered help by Sumika-senpai. Sumika has an unlimited supply of certain types of coffee. Specifically, you are given a binary string $$$s$$$ of length $$$n$$$, where $$$s_i = 1$$$ if and only if Sumika has coffee of type $$$i$$$. Kanako can ask for any non-negative real amount of coffee of each type that Sumika has, as long as the total volume of coffee she requests is at most $$$v$$$.
After getting some coffee from Sumika, Kanako can then trade with other customers at Cafe Liebe. In particular, there are $$$m$$$ customers willing to trade. To trade with the $$$i$$$-th customer, Kanako must do the following:
- Choose a non-negative real number $$$k$$$.
- Give the customer $$$ka_i$$$ cups of coffee $$$x_i$$$ and $$$kb_i$$$ cups of coffee $$$y_i$$$.
- In return, the customer will give Kanako $$$kc_i$$$ cups of coffee $$$z_i$$$.
Kanako can trade with customers as many times as she wants. What is the maximum amount of coffee of type $$$1$$$ she can obtain?
Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 50$$$).
The first line of each test contains $$$n$$$, $$$m$$$, and $$$v$$$ — the number of coffee types, the number of customers, and the maximum amount of starting coffee ($$$1 \le n \le 50$$$, $$$0 \le m \le 10^3$$$, $$$1 \le v \le 10^{18}$$$).
The second line contains a string $$$s$$$ of length $$$n$$$ consisting of 0s and 1s. The $$$i$$$-th character is 1 if and only if Sumika has coffee of type $$$i$$$.
The next $$$m$$$ lines contain $$$6$$$ integers each: $$$a_i$$$, $$$x_i$$$, $$$b_i$$$, $$$y_i$$$, $$$c_i$$$, and $$$z_i$$$, describing their trades ($$$1 \le x_i, y_i, z_i \le n$$$, $$$1 \le a_i, b_i \le 5$$$, $$$c_i = 1$$$). It is guaranteed that $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$ are all distinct.
In the easy version, it always holds that $$$c_i = 1$$$.
For each test, output a floating-point number, the answer.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
43 1 200112 2 3 3 1 11 0 100000000000000000008 12 8773011000004 8 2 4 1 61 2 4 7 1 84 7 1 2 1 65 8 2 2 1 15 3 3 1 1 25 8 3 7 1 53 3 2 7 1 25 1 4 5 1 63 4 4 8 1 35 7 4 8 1 35 3 4 2 1 43 4 1 3 1 74 2 100112 3 5 4 1 25 2 1 4 1 1
4.0 0 15.4726631393 0.02777777777777
In the first test, you can ask for $$$8$$$ cups of type-2 coffee and $$$12$$$ cups of type-3 coffee. Then, you trade with customer $$$1$$$ using $$$k=4$$$, and thus recieve $$$4$$$ cups of type-1 coffee. We can show this is the maximum achievable.
In the second test, we cannot obtain any coffee of any type no matter what, so we output $$$0$$$.
After a long day of being orz, CodeTiger starts doing his homework. To be more effective, he has decided to plan out some breaks.
In CodeTiger's world, the day is $$$m$$$ seconds long, so clocks display integers between $$$0$$$ and $$$m-1$$$ inclusive. Specifically, $$$s$$$ seconds after CodeTiger starts working, the clock will display the integer $$$s \bmod m$$$.
CodeTiger decides that he will look at the clock at some points in time, and will take a break whenever he sees an integer on the clock less than or equal to a chosen integer $$$x$$$ (he is very genius, so his breaks last for a negligible amount of time).
Obviously, CodeTiger cannot always look at the clock, so he came up with some rules on when to look at the clock. The first time he looks at the clock is after $$$b$$$ seconds.
After that, suppose CodeTiger has looked at the clock $$$i$$$ times before, and the last time he looked was after $$$z$$$ seconds. Then he will next look at the clock after $$$(m-1)z+a(i\bmod c)^2$$$ seconds, where $$$a$$$ and $$$c$$$ are given constants.
CodeTiger will stop doing his homework after looking at the clock for the $$$n$$$-th time. How many breaks will CodeTiger take, if the clock initially displays $$$0$$$?
Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 100$$$).
The next $$$t$$$ lines each contain $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$, $$$x$$$, and $$$c$$$ ($$$2 \le n,m,a,b \le 10^9$$$, $$$0 \le x \lt m$$$, $$$1 \le c \le 10^3$$$).
For each testcase, print the number of breaks that CodeTiger takes.
44 9 2 3 4 569420 1000000000 6969 69420 999999999 420142 48 474 706 40 921210 873 131 32 592 572
3 69420 124 142
In the first test,
- CodeTiger first looks at the clock at time $$$b=3$$$. At this point, the clock displays the time $$$3$$$. $$$3 \le x=4$$$, so he will take a break.
- CodeTiger next looks at the clock at time $$$(m-1)\cdot 3 + a(1 \bmod c)^2 = 8\cdot 3 + 2\cdot 1 = 26$$$. At this time, the clock displays the time as $$$8$$$, so he does not take a break ($$$8 \gt x = 4$$$).
- Codetiger next looks at the clock at time $$$(m-1)\cdot 26 + a(2 \bmod c)^2 = 8\cdot 26 + 2\cdot 4 = 216$$$. Here, the clock will display the time as $$$0$$$. $$$0 \le x = 4$$$, so CodeTiger takes a break.
- Finally, CodeTiger looks at the clock at time $$$(m-1)\cdot 216 + a(3\bmod c)^2 = 8\cdot 216 + 2\cdot 9 = 1746$$$. At this time, the clock will display the time $$$0$$$, so he takes a break ($$$0 \le x = 4$$$).
In total, CodeTiger takes $$$3$$$ breaks.
In the second test, $$$x=m-1$$$, meaning that CodeTiger will take a break every time he looks at the clock. Therefore, we should output $$$n=69420$$$.
In the third test, note that it might be possible for $$$b \ge m$$$.
The city of Axington plans to expand!
Next to the city, there is a forested area that can be represented as a $$$n$$$-by-$$$n$$$ grid. Each cell is either empty or contains a tree. There is at least one tree.
Each day, there will be $$$k$$$ workers available to chop down trees. On any given day, you need to assign workers to trees in such a way that:
- Each worker is assigned at most one tree to chop down, and no two workers are assigned the same tree.
- Any tree designated to be chopped down must be connected to the edge of the grid.
Here, a tree is connected to the edge of the grid if it is possible to reach the edge of the grid by starting at the tree's cell, and moving only onto adjacent empty cells. Two cells are considered adjacent if they share a side.
Find the minimum number of days needed to chop all trees down, and construct one such plan.
Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).
The first line of each test contains $$$n$$$ and $$$k$$$, the size of the grid and the number of workers ($$$2 \le n \le 500$$$, $$$1 \le k \le 10^6$$$).
The next $$$n$$$ lines contain $$$n$$$ characters each, describing the grid. The $$$j$$$-th character in the $$$i$$$-th line is T if there is a tree at $$$(i,j)$$$, and . otherwise.
It is guaranteed that there is at least one tree in each grid.
It is guaranteed that the sum of $$$n^2$$$ over all tests does not exceed $$$250\,000$$$.
For each test, output $$$n$$$ lines with $$$n$$$ tokens each.
The $$$j$$$-th token in the $$$i$$$-th line should be . if the cell $$$(i,j)$$$ is empty, and an integer $$$a_{i,j}$$$ otherwise — denoting the day on which that tree should be cut down ($$$1 \le a_{i,j} \le n^2$$$).
If there are multiple possible answers, you can output any.
44 5T T T .T T T .T T T .. . . T2 1T TT T2 999T TT T6 100. T T T . .T . T T . TT T T T T TT . T T T .. T . . T T. T T T T .
2 2 2 . 2 2 1 . 1 1 1 . . . . 1 4 3 2 1 1 1 1 1 . 1 1 1 . . 1 . 2 1 . 1 1 2 3 2 1 1 1 . 2 2 1 . . 1 . . 2 1 . 1 1 1 1 .
In the first test, note that we are not allowed to cut down the tree at $$$(2,2)$$$ on the first day because it is not connected to the edge.
In the second test, all trees are connected to the edge, but we have to cut them down one at a time because we only have one worker.
In the third test, we can cut down all trees within one day.
This is the Hard version of the problem. The problems differ in their constraints and input formats. A solution to one may not work for the other.
Kanako-chan loves Hime-chan secretly, so she wants to give her as much coffee as possible (Hime is a caffeine addict). There are $$$n$$$ types of coffee numbered from $$$1$$$ to $$$n$$$, but Hime is only interested in type $$$1$$$.
Kanako was offered help by Sumika-senpai. Sumika has an unlimited supply of certain types of coffee. Specifically, you are given a binary string $$$s$$$ of length $$$n$$$, where $$$s_i = 1$$$ if and only if Sumika has coffee of type $$$i$$$. Kanako can ask for any non-negative real amount of coffee of each type that Sumika has, as long as the total volume of coffee she requests is at most $$$v$$$.
After getting some coffee from Sumika, Kanako can then trade with other customers at Cafe Liebe. In particular, there are $$$m$$$ customers willing to trade. To trade with the $$$i$$$-th customer, Kanako must do the following:
- Choose a non-negative real number $$$k$$$.
- Give the customer $$$ka_i$$$ cups of coffee $$$x_i$$$ and $$$kb_i$$$ cups of coffee $$$y_i$$$
- In return, the customer will give Kanako $$$kc_i$$$ cups of coffee $$$z_i$$$.
Kanako can trade with customers as many times as she wants. What is the maximum amount of coffee of type $$$1$$$ she can obtain?
Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \leq 10$$$).
The first line of each test contains $$$n$$$, $$$m$$$, and $$$v$$$ — the number of coffee types, the number of customers, and the maximum amount of starting coffee ($$$1 \le n \le 20$$$, $$$0 \le m \le 100$$$, $$$1 \le v \le 10^{18}$$$).
The second line contains a string $$$s$$$ of length $$$n$$$ consisting of 0s and 1s. The $$$i$$$-th character is 1 if and only if Sumika has coffee of type $$$i$$$.
The next $$$m$$$ lines contain $$$6$$$ numbers each: $$$a_i$$$, $$$x_i$$$, $$$b_i$$$, $$$y_i$$$, $$$c_i$$$, and $$$z_i$$$, describing their trades ($$$1 \le x_i, y_i, z_i \le n$$$, $$$1 \le a_i, b_i, c_i \le 10^6$$$). Note that $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$ are integers, whereas $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ can be float numbers in the hard version. It is guaranteed that $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$ are all distinct.
In the hard version, it always holds that $$$c_i \leq 5$$$.
For each test, output a floating-point number, the answer. If Kanako can get an arbitrarily large amount of coffee, output $$$-1$$$.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
13 2 10112 2 1 3 4.5 12 1 2 3 4 2
1.750000000000000000
In the sample, one can show that the optimal exchange can't yield above 1.75 cups. It can be further shown that there exists some initial ratio such that the final value infinitely approaches 1.75.
Codetiger is playing Minecraft with his friends again. His current world is a 2d park that can be represented on an infinite cartesian plane. In the park there are $$$n$$$ axis-aligned square trees, each centered at location $$$(x_i, y_i)$$$ and having side length $$$s_i$$$. No two trees have intersecting area in this world.
After his Minecraft dog was killed by one of his friends he decides to be more careful. To do so, he wants to make sure his new dog has various escape paths. As his dog and house will be at different locations over time and his dog is still growing, he needs to test if an escape path exists between various different points for various sizes of his dog. The dog can walk along any continuous path in the 2d world as long as at no point the area of the dog intersects the area of any trees. The dog is also an axis-aligned square. Note that the dog's movement is also axis-aligned.
As Codetiger is training to be a CEO and therefore practices delegating work to others (like the problem writing of this contest), he decides to ask you $$$q$$$ queries about his dog's possible escape paths. Each specifies the center location of the dog where it starts $$$(sx_i, sy_i)$$$, the center location of the dog where it should end up in Codetiger's potential new house $$$(ex_i, ey_i)$$$, and the side length of the dog $$$d_i$$$. It is guaranteed the dog will not intersect any trees at the start and end locations in any queries.
For each query you must answer whether any continuous escape path exists between the locations so that the dog intersects no trees. Output WOOF if one exists or MEOW otherwise.
The first line contains $$$n$$$, and $$$q$$$ — the number of trees and the number of queries. $$$(1 \leq n,q \leq 3 \times 10^4)$$$
Each of the next $$$n$$$ lines contains three integers, $$$x_i$$$, $$$y_i$$$, and $$$s_i$$$ — the $$$x$$$ and $$$y$$$ coordinates and side length of the tree. $$$(1 \leq x_i,y_i,s_i \leq 10^6)$$$
Each of the next $$$q$$$ lines contains three integers, $$$sx_i$$$, $$$sy_i$$$, $$$ex_i$$$, $$$ey_i$$$, and $$$d_i$$$ — the $$$x$$$ and $$$y$$$ coordinates of the query's starting position, ending position, and side length of the dog. $$$(1 \leq sx_i,sy_i,ex_i,ey_i,d_i \leq 10^6)$$$
For each query, respond either WOOF if there is a valid path or MEOW if not.
20 2 12 12 4 25 9 4 9 23 5 16 22 4 23 13 2 24 16 2 20 14 1 0 15 3 0 21 3 20 17 5 21 4 5 20 24 4 0 10 2 19 10 2 11 19 1 6 16 2 5 20 1 9 13 2 17 14 1 24 25 1 14 16 6 7 4 6 12 24 20 1
MEOW WOOF