Attack on Titans
All submissions for this problem are available.
Titan is the largest ever threat to the humanity. The humanity have constructed N walls in order to defend their living area from the titans, as illustrated in the figure. All walls are circles centered at the humanity Capital and have strictly increasing radius. Humans live inside the walls. Walls are numbered from 1 to N, from the innermost to the outermost. Wall i has defensive power Di.
M waves of titans are approaching the humanity Capital, numbered from 1 to M. As the titans come in all directions uniformly, we can project the walls to 1 dimension and consider a wall of radius Ri to be located at x = Ri (see the illustration). The j-th wave of titans are initially (on day 0) at x = Pj and have attacking power Aj. The titans move towards x = 0 at a speed of 1 unit of distance per day. Upon reaching an outermost wall (say wall i), the titans attack the wall. If Di < Aj then wall i breaks and the titans will move forward towards the Capital on the next day. Otherwise, the attacking titans will be held at the wall but they will not be eliminated (unfortunately the humanity is very weak compared with the titans). If another wave of titans reach wall i later, the two waves will merge into a larger wave with an attacking power of the sum of the waves' individual attacking powers. The larger wave will attack the wall they are at immediately and if they break the wall, they will move forward towards the capital on the next day.
The only thing the humanity can do now is to enhance their walls. The defensive power Di of wall i can be enhanced by 1 unit in Ei days. The humanity can only enhance one wall at a time. Once a wall enhancement starts, no other wall enhancements can be made until the current enhancement finishes.
Determine the number of the outermost wall at which the humanity will be able to hold all waves of titans, and the minimum total number of days needed for wall enhancements to achieve that. Of course the humanity will do their best.
The input begins with the number of test cases T.
Each test case begins with a line of 2 integers, N, M.
N lines follow. The i-th line contains three integers Ri, Di, Ei.
M lines follow. The j-th line contains two integers Pj, Aj.
For each case output the outermost wall number at which the humanity will be able to hold all waves of titans. Also print the minimum total number of days of wall enhancements required to achieve that. If there is no way the humanity could prevent the titans from reaching the Capital (human extinction), output "poor humanity".
- T ≤ 10
- 1 ≤ N, M ≤ 5000
- 1 ≤ Ri, Di, Ei, Pj, Aj ≤ 109 for every 1 ≤ i ≤ N, 1 ≤ j ≤ M
- Ri < Ri+1 for every 1 ≤ i ≤ N - 1
- Pj < Pj+1 for every 1 ≤ j ≤ M - 1
- RN < P1
Input: 3 3 3 1 3 1 2 2 1 3 1 1 4 1 5 2 6 3 2 2 1 5 2 5 9 4 9 10 30 7 1 1 1 1 1 100 1000 Output: 2 4 1 28 poor humanity
Example 1: The humanity may enhance wall 2 four times so that on day 4 wall 2 will have defensive power 6.
On day 1, wall 3 will hold the 1st wave of titans.
On day 2, wall 3 will be broken as the first 2 waves of titans merge into one larger wave with attacking power 3.
On day 3, the larger wave reaches wall 2, which will have defensive power 4 by that time.
On day 4, all titans will be merged into one wave with attacking power 6 at wall 2, which will have defensive power 6 by that time.
Therefore wall 2 will be able to hold all titans.
The number of days required for wall enhancement is E2×4 = 4.
Example 2: The humanity shall use 4 days to enhance wall 2 once and hold the first wave of titans at wall 2 since day 4.
Then the humanity must start to enhance wall 1 twelve times, which takes 24 days.
On day 25, wall 2 will fall under the merged two waves of titans.
On day 29, wall 1 will be able to hold the titans of attacking power 17.
In total wall 2 is enhanced once and wall 1 is enhanced 12 times, so the minimum number of days required for wall enhancement is E2×1 + E1×12 = 4×1 + 2×12 = 28.
Example 3: The attacking power the titan wave is so strong so that even the humanity keeps enhancing their only wall starting from day 0, they still cannot stop the titans.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.