National Olympiad in Informatics, China, 2010
Day 2, Problem 3 - Happily Growing
Nemo is a carefree little fish. His initial birth weight is w0. Cute little Nemo wishes to grow up as fast as possible, and thus will need to eat as much food as possible. Nemo's favorite food is little shrimps from the ocean.
Nemo's understanding of the available food is as follows: There are a total of n shrimps in the ocean, numbered from 1 to n. Shrimp i will have a weight of wi. The ocean can be represented as a Cartesian plane. At time 0, shrimp i will be at position (xi, yi). In the ocean, shrimps move in straight lines at constant velocities. Shrimp i's velocity vector is (pi, qi), which means at time i, its position will be (xi + pi*t, yi + qi*t).
At time 0, Nemo's position will be (x0, y0). He may move however he pleases in the ocean, but his speed cannot exceed V. Through his own hard work, Nemo wishes to eat the largest weight of shrimp as possible within T units of time (containing T moments). When Nemo and a little shrimp moves onto the same position at the same time, and the weight of the shrimp is smaller than Nemo's weight at that time, then Nemo will be able to successfully eat up the shrimp. When Nemo eats a shrimp of weight wi, his own weight will increase by wi. Note: shrimps cannot eat Nemo, nor will they cannibalize each other.
Nemo wishes for you to help him design a growth plan, so that the weight of the shrimp he eats is as large as possible.
There are 10 test cases
nemo10.in that will be given to your program (through standard input). They can be downloaded here for you to study: nemo.zip
Line 1 of input contains an integer from 1 to 10, representing the test case number. Test case
nemoi.in will have i on its first line.
Line 2 contains five real numbers w0, V, T, x0, and y0. Respectively, the represent Nemo's initial weight, maximum speed, time to eat shrimp, and initial position at time 0.
Line 3 contains a single integer n, representing the number of shrimp there are in the ocean.
For the following n lines, each line contains 5 real numbers wi, xi, yi, pi, and qi, representing the weight of shrimp i, its position at time 0, and its velocity vector.
Line 1 of output should consists a single integer k, representing the number of shrimps Nemo will eat in your plan.
Line 2 should consists of a single real number w, representing the total weight of shrimps that Nemo will eat in your plan.
For the following k lines, each line should contain 4 numbers t, x, y, and s. This indicates that at time t, Nemo should be at position (x, y) to eat shrimp s. Here, t, x, and y are real numbers, while s is an integer.
To ensure that your answer is precise enough, we suggest outputting all real numbers to 6 digits after the decimal. During grading, two real numbers are considered equivalent if their error (i.e. absolute difference) does not exceed 10−4.
0 6 1 6 0 0 1 5 2 2 0 0
1 5 5 2 2 1
In the sample solution at time 5, Nemo will be at position (2, 2) to eat shrimp number 1. Nemo can actually reach (2, 2) much earlier, since the problem only requires his speed to merely not exceed V.
For each test case, we will have 9 grading parameters a10, a9, …, a2. If your output is invalid, then you will be given a score of 0. Otherwise, assuming that Nemo's weight increase in your solution is wuser, then your score out of 10 for the test case will be determined as follows:
|10||wuser ≥ a10|
|9||wuser ≥ a9|
|8||wuser ≥ a8|
|7||wuser ≥ a7|
|6||wuser ≥ a6|
|5||wuser ≥ a5|
|4||wuser ≥ a4|
|3||wuser ≥ a3|
|2||wuser ≥ a2|
|1||wuser > 0|
If multiple conditions are satisfied, then the condition that yields the highest score will be taken.
Point Value: 50 (partial)
Time Limit: 60.00s
Memory Limit: 512M
Added: Aug 08, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3