Phoenix is redecorating his massive backyard and decides that he has space for $$$m$$$ total trees and he would like to maximize the beauty of his garden (which is calculated as the sum of the beauty of each tree). He visits Jett's store to buy seeds for the $$$m$$$ trees but since Spring is just around the corner, the store is running low on some types of trees. For the $$$i$$$th type of tree at Jett's store, there are $$$t_i$$$ seeds of that type and each of those trees has a beauty of $$$b_i$$$. Given this information, help Phoneix figure out the maximum beauty he can construct for his garden.
The first line of the input will contain $$$n$$$ $$$(1 \le n \le 100)$$$, the number of types of trees, and $$$m$$$ $$$(1 \le m \le 10^5)$$$, the size of Phoenix's garden, or the number of trees he can pick out.
The next $$$n$$$ lines each contain two integers $$$t_i$$$ $$$(1 \le t_i \le 2000)$$$, and $$$b_i$$$ $$$(1 \le b_i \le 1000)$$$, where $$$t_i$$$ is the amount of the $$$i^{th}$$$ tree that is available, while $$$b_i$$$ is the beauty points one tree of that type would bring.
A single integer representing the maximum amount of beauty points Phoenix can acquire for his garden.
3 8 5 4 4 6 3 5
43
In the sample, Phoenix can take all $$$4$$$ seeds with beauty of $$$6$$$, all $$$3$$$ seeds with beauty of $$$5$$$, and one seed with beauty of $$$4$$$ to get the maximum possible beauty of $$$43$$$.
The White Goosefoot is a very peculiar plant. While it is not very well known among humans, geese know about it very well. In fact, several species of very intelligent geese visit a White Goosefoot every day, as a part of a geese ritual, per say.
There are several geese flocks scattered around the world, which is represented here as a 2D-plane. Furthermore, there are also lots of White Goosefoot plants scattered about as well. Given the locations of both, determine for every single flock, the location of the closest White Goosefoot. In the case that multiple White Goosefoot plants are equidistant from a flock, output the one with the smallest $$$x$$$ value, and in the case that the $$$x$$$ values are the same, output the one with the smallest $$$y$$$ value.
The first line of the input contains two integers $$$n (1 \le n \le 100)$$$ and $$$m (1 \le m \le 100)$$$, the number of flocks and the number of plants, respectively.
The next $$$n$$$ lines each contain two space separated integers $$$n_x (0 \le n_x \le 10^4), n_y (0 \le m_y \le 10^4)$$$, a location of a single flock. It is guaranteed that flock locations are unique.
The next $$$m$$$ lines each contain two space separated integers $$$m_x (0 \le n_x \le 10^4), m_y (0 \le m_y \le 10^4)$$$, a location of a single plant. It is guaranteed that plant locations are unique.
$$$n$$$ lines of output, each as two space separated integers, where the $$$i^{th}$$$ line is the nearest White Goosefoot plant for the $$$i^{th}$$$ flock.
3 3 0 0 2 2 4 4 2 0 0 2 5 5
0 2 0 2 5 5
Redwoods are known as one of the tallest species of trees, reaching heights of more than 300 feet! Thus, Johnny has decided that he wants to build a treehouse in the redwood near his house. However, he also doesn't want to be lonely!
Johnny has decided that he will let those in if they were able to solve the answer to a question that he has devised. He will give anyone who wants to enter the list of numbers ranging from 1 to $$$n$$$ but has removed one number from the list. The numbers can also appear in any order, but each number will only appear once. Since he chose the number to remove at random, he wants to know the mean of the list of numbers as well. Output the floor of the absolute difference between the missing number that Johnny has removed and the mean of the list.
The first line will consist of an integer that represents $$$n$$$ ($$$1 \leq n \leq 10^5$$$). The next line will contain $$$n-1$$$ integers where each integer $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) represents a value in the list that Johnny will provide those who want to enter the treehouse.
Output the floor of the absolute difference between the missing number in the array and the mean of the list of numbers that Johnny has provided.
5 1 2 4 5
0
2 1
1
In the first test case, the missing number is 3. The average of the numbers is also 3, so we output 0.
In the second case, we are missing a 2. Since the average of the numbers is 1, we output 1.
Maria is a big fan of all things sweet, especially maple syrup. Luckily, she's managed to find a large grove of maple trees and wants to collect as much syrup as she can! The grove consists of $$$n$$$ trees and $$$n - 1$$$ paved roads that Maria can travel on. The grove is connected, so Maria can reach any tree from any start tree by traveling along these paved roads. Each tree has an associated syrup value, $$$s_i$$$, which gives how much syrup Maria can potentially extract from the tree.
Unfortunately, Maria doesn't want to risk getting lost in the grove and straying too far away from her starting position. Given that Maria can start from any tree in the grove and collect syrup from all trees that are directly connected to her starting tree with a single road, find out the maximum amount of syrup that Maria can collect!
The first line is a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, which gives the number of trees in the maple grove. The next line consists of $$$n$$$ integers $$$s_i$$$ $$$(1 \leq s_i \leq 1000)$$$, where the $$$i$$$th value gives the syrup values for the $$$i$$$th tree. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ $$$1 \leq u_i, v_i \leq n$$$, which gives two trees that are connected by a paved road.
Output a single integer giving the maximum amount of syrup that Maria can collect.
4 1 2 3 4 1 2 2 3 3 4
9
If Maria starts at tree $$$3$$$, she can collect $$$2 + 3 + 4 = 9$$$ syrup overall.
The Once-ler is back with his lucrative Thneed business!
There are $$$N$$$ truffula trees in a row, and the Once-ler visits them in order, starting at the first truffula tree. He starts with a Super-Axe-Hacker with durability $$$d$$$.
Each truffula tree has toughness $$$t_i$$$, and the Once-ler can choose to chop down a truffula tree if and only if the durability of his Super-Axe-Hacker is greater than or equal to the current tree's toughness ($$$d \ge t_i$$$). Every time the Once-ler chops down a tree, the durability of his Super-Axe-Hacker decreases by one.
However, this time, the Once-ler wants to avoid chopping down trees unsustainably and angering the Lorax. Therefore, the Once-ler refuses to chop down more than one tree in a row.
However, he still needs to make a profit. Each truffula tree he cuts down can make one Thneed. To reach his quota, he needs to make $$$k$$$ Thneeds.
What is the minimum starting durability $$$d_{min}$$$ of the Once-ler's Super-Axe-Hacker that guarantees at least $$$k$$$ Thneeds will be made?
The first line contains two integers $$$N$$$ and $$$k$$$ where $$$N$$$ is the number of truffula trees, and $$$k$$$ is the number of Thneeds the Once-ler needs to make. ($$$1 \le N \le 10^5, 1 \le k \le N$$$)
The next line contains $$$N$$$ integers $$$t_1...t_n$$$ where $$$t_i$$$ is the toughness of the $$$i$$$th truffula tree. ($$$1 \le t_i \le 10^9$$$)
Output $$$d_{min}$$$, the minimum starting durability that guarantees at least $$$k$$$ Thneeds will be made. If it is not possible to make $$$k$$$ Thneeds while satisfying all the requirements, output $$$-1$$$.
6 2 4 9 2 1 2 10
3
6 5 8 8 8 8 8 8
-1
In the first example, the Once-ler starts with durability $$$d=3$$$, and chops down the 3rd and 5th trees to create 2 Thneeds.
In the second example, the Once-ler cannot make 5 Thneeds without angering the Lorax.
Alfred, an avid botanist and lumberjack, while traveling across the state of California, has come across an absolutely humongous giant sequoia tree. Being the botanist that he is, Alfred would like to examine this fascinating giant sequoia tree in great depth. More specifically, he would like to observe its branches.
Each of the $$$n$$$ branches of the giant sequoia tree has a specific length associated with it, and certain branches are longer than others. Because of this, Alfred was inspired to solve a certain problem, though his skills in computing are quite limited, and he has come to you for help!
Alfred would like to figure out the longest strictly-increasing consecutive sub-array (a sub-array such that $$$a_{i+1} \gt a_i$$$ for each $$$i$$$ except the last in the sub-array) of the giant sequoia tree branches. However, he is torn between his love for botany and his duties as a lumberjack. He can either choose to leave the tree alone and compute the answer directly, or he can chop off a consecutive sub-array of size exactly $$$k$$$ from the giant sequoia tree before running his computations. More formally, Alfred can choose some index $$$i$$$ such that $$$i + k - 1 \leq n$$$ and then remove the branches at indices $$$i, i + 1, i + 2, \dots, i + k - 1$$$. Since he doesn't have all that much energy after hiking all day, he can only perform this action a maximum of one time.
Given his choices, can you help Alfred find the longest strictly-increasing consecutive sub-array within the giant sequoia tree after at most one chop of size $$$k$$$?
The first line of input will contain a two space-separated integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and $$$k$$$ ($$$0 \leq k \leq n$$$), the number of branches of the giant sequoia tree and the number of possible branch removals, respectively.
The second line of input will contain $$$n$$$ space separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$ for $$$1 \leq i \leq n$$$). The $$$i$$$-th integer on the second line represents the length of the $$$i$$$-th branch of the giant sequoia tree starting at the lowest branch.
The output should consist of a single integer $$$x$$$, where $$$x$$$ represents the longest strictly-increasing sub-array of branches after either $$$0$$$ or $$$k$$$ consecutive branch removals.
3 2 1 2 3
3
6 2 1 2 4 3 5 6
4
Alfred can choose to remove either $$$0$$$ or $$$k$$$ consecutive branches from the giant sequoia tree. Actions which are strictly disallowed are removing $$$x$$$ branches where $$$x \not\in \{0, k\}$$$ and/or removing a set of branches which are non-contiguous.
Cacti are basically desert trees, and they deserve some love too.
After staring at a bunch of cacti, you've realized that, indeed, cacti are quite beautiful! In fact, as you looked at them more, you realize that some "perfect cacti" look geometric:
Not only are cacti geometric, but they're also recursive (like trees)! However, so far you've only been able to cultivate perfect $$$k$$$-cacti of height 1 – that is, cacti that resemble perfect polygons with $$$k$$$ sides.
Suddenly, you remember something from class: just like trees, cacti can be graphs too! In fact, we can treat the perfect cactus graph as an unweighted, undirected graph between vertices (of the polygon). You begin to wonder: given a perfect cacti graph, how long does it take to get from one node to another? Or, even better – can you find these values, even as edges are broken and restored?
The first line begins with three integers, $$$k$$$ $$$(3 \leq k \leq 10^{18})$$$, $$$h$$$ $$$(h=1)$$$ and $$$q$$$ $$$(1 \leq q \leq 10^5)$$$. $$$k$$$ and $$$h$$$ describe the cactus graph (which is a $$$k$$$-cactus of height $$$h$$$).
It is guaranteed that the number of nodes in the perfect cactus graph does not exceed $$$10^{18}$$$.
Then, $$$q$$$ lines follow, each containing three integers: $$$a, i, j$$$. The type of query is determined by $$$a$$$:
Since the graph is not directly given to you, the vertices are labelled $$$0 \ldots k-1$$$, starting at the root, and going clockwise.
For each query where $$$a=1$$$, print out the minimum number of edges needed to get from vertex $$$i$$$ to vertex $$$j$$$. If no path exists, output -1.
10 1 7 1 0 8 2 0 9 1 0 8 2 0 1 1 0 8 3 0 9 1 0 8
2 8 -1 2
In an effort to "go green", a city is investigating planting a forest of sling-trees to replace its current network of highways and stroads.
Under the new transit plan, each of the city's $$$1 \leq N \leq 10^5$$$ neighborhoods would get a single sling-tree. To navigate the network, the citizens would climb into a tree, then repeatedly sling themselves to another tree.
However, not every tree can reach every other tree. Each sling-tree $$$i$$$ has a power $$$p_i$$$ and resistance $$$r_i$$$, where $$$1 \leq p_i, r_i \leq 10^6$$$. To sling from tree $$$i$$$ to tree $$$j$$$, the power of tree $$$i$$$ must not exceed the resistance of tree $$$j$$$. In other words, this requires that $$$p_i \leq r_j$$$.
Numerous groups have raised concerns about this system, specifically worrying about experiencing in-air collisions and getting back home. To reassure the public, the city has made two stipulations for the network.
1) To minimize in-air collisions, each tree will only accept launches from one other tree
2) Citizens will never get stuck in the system (they will be able to return to their starting tree).
Given the $$$N$$$ planned sling-trees and their power and resistances, determine whether the city can keep its promises.
The first line is a single integer, $$$N$$$, giving the number of neighborhoods. The next $$$N$$$ lines consist of two integers each, $$$p_i$$$ and $$$r_i$$$, for the $$$i$$$-th tree.
A single line, "YES" or "NO", whether we can navigate from each sling-tree back to itself.
3 5 2 9 10 1 6
YES
3 5 4 8 6 5 10
NO
Baobab trees, native to regions of Africa and Australia, are some of the stoutest trees in the world, meaning they bear immensely thick trunks of up to 35 feet in diameter! The trunk of a baobab must be thick enough for it to store plenty of water inside during the rainy season so that the tree can survive through harsh, dry seasons on the African savanna.
Kofi wants to plant several varieties of baobab trees on a $$$h\times w$$$ rectangular plot of land. His primary concern is whether all of the $$$T$$$ trees he wants to plant will be able to fit together within the plot upon reaching maturity. For the $$$i^{th}$$$ seed he wants to plant, Kofi has estimated the trunk and root area that the tree is expected to grow to, in terms of a square bounding box with side length $$$t_i$$$. Help Kofi determine where to plant his baobab seeds so that all of the trees will fit!
The first line of input contains two space-separated integers $$$h$$$ and $$$w$$$ $$$(1 \leq h, w \leq 6)$$$, the height and and width of Kofi's plot of land.
The next line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 26)$$$, the number of trees Kofi wishes to plant.
The last line of input contains $$$T$$$ space-separated integers $$$t_i$$$ ($$$1 \leq t_i \leq \min(h, w)$$$), each denoting the side length of the mature bounding box for the $$$i^{th}$$$ baobab that Kofi wishes to plant.
If it is not possible for Kofi to plant all of his baobabs together in the plot, print IMPOSSIBLE.
Otherwise, output a $$$h\times w$$$ grid representing a valid layout in which Kofi could plant all of his desired trees. Mark the cells of each mature tree bounding box with a unique upper-case letter corresponding to that tree, and mark cells containing no bounding box with a '.'. Note, you may print any $$$h\times w$$$ grid representing a valid configuration of the trees, so long as $$$h$$$ is the number of rows and $$$w$$$ the number of columns in the plot.
6 6 10 2 1 1 2 1 2 1 2 1 3
J J J I I E J J J I I D J J J H H C G G B H H A G G F F . . . . F F . .
6 5 4 4 2 2 2
IMPOSSIBLE