NOI '10 P6 - Happily Growing - DMOJ: Modern Online Judge

NOI '10 P6 - Happily Growing

View as PDF

Submit solution

All submissions

Best submissions

Points: 50 (partial)

Time limit: 25.0s

Memory limit: 512M

Problem types

National Olympiad in Informatics, China, 2010

Nemo is a carefree little fish. His initial birth weight is $w_0$ ~w_0~. 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$ ~n~ shrimps in the ocean, numbered from $1$ ~1~ to $n$ ~n~. Shrimp $i$ ~i~ will have a weight of $w_i$ ~w_i~. The ocean can be represented as a Cartesian plane. At time $0$ ~0~, shrimp $i$ ~i~ will be at position $(x_i, y_i)$ ~(x_i, y_i)~. In the ocean, shrimps move in straight lines at constant velocities. Shrimp $i$ ~i~'s velocity vector is $(p_i, q_i)$ ~(p_i, q_i)~, which means at time $i$ ~i~, its position will be $(x_i + p_i \times t, y_i + q_i \times t)$ .

At time $0$ ~0~, Nemo's position will be $(x_0, y_0)$ ~(x_0, y_0)~. He may move however he pleases in the ocean, but his speed cannot exceed $V$ ~V~. Through his own hard work, Nemo wishes to eat the largest weight of shrimp as possible within $T$ ~T~ units of time (containing $T$ ~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 $w_i$ ~w_i~, his own weight will increase by $w_i$ ~w_i~. 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.

Input Specification

There are $10$ ~10~ test cases nemo1.in to 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$ ~1~ of input contains an integer from $1$ ~1~ to $10$ ~10~, representing the test case number. Test case nemoi.in will have $i$ ~i~ on its first line.
Line $2$ ~2~ contains five real numbers $w_0$ ~w_0~, $V$ ~V~, $T$ ~T~, $x_0$ ~x_0~, and $y_0$ ~y_0~. Respectively, they represent Nemo's initial weight, maximum speed, time to eat shrimp, and initial position at time $0$ ~0~.
Line $3$ ~3~ contains a single integer $n$ ~n~, representing the number of shrimp there are in the ocean.
For the following $n$ ~n~ lines, each line contains $5$ ~5~ real numbers $w_i$ ~w_i~, $x_i$ ~x_i~, $y_i$ ~y_i~, $p_i$ ~p_i~, and $q_i$ ~q_i~, representing the weight of shrimp $i$ ~i~, its position at time $0$ ~0~, and its velocity vector.

Output Specification

Line $1$ ~1~ of output should consist of a single integer $k$ ~k~, representing the number of shrimps Nemo will eat in your plan.
Line $2$ ~2~ should consist of a single real number $w$ ~w~, representing the total weight of shrimps that Nemo will eat in your plan.
For the following $k$ ~k~ lines, each line should contain $4$ ~4~ numbers $t$ ~t~, $x$ ~x~, $y$ ~y~, and $s$ ~s~. This indicates that at time $t$ ~t~, Nemo should be at position $(x, y)$ ~(x, y)~ to eat shrimp $s$ ~s~. Here, $t$ ~t~, $x$ ~x~, and $y$ ~y~ are real numbers, while $s$ ~s~ is an integer.
To ensure that your answer is precise enough, we suggest outputting all real numbers to $10$ ~10~ digits after the decimal. During grading, two real numbers are considered equivalent if their error (i.e. absolute difference) does not exceed $10^{-4}$ ~10^{-4}~.

Sample Input

Sample Output

1
5
5 2 2 1

Explanation

In the sample solution at time $5$ ~5~, Nemo will be at position $(2, 2)$ ~(2, 2)~ to eat shrimp number $1$ ~1~. Nemo can actually reach $(2, 2)$ ~(2, 2)~ much earlier, since the problem only requires his speed to merely not exceed $V$ ~V~.

Scoring

For each test case, we will have $9$ ~9~ grading parameters $a_{10}, a_9, \dots, a_2$ ~a_{10}, a_9, \dots, a_2~. If your output is invalid, then you will be given a score of $0$ ~0~. Otherwise, assuming that Nemo's weight increase in your solution is $w_\text{user}$ ~w_\text{user}~, then your score out of $10$ ~10~ for the test case will be determined as follows:

Score	Condition
$10$ ~10~	$w_\text{user} \ge a_{10}$ ~w_\text{user} \ge a_{10}~
$9$ ~9~	$w_\text{user} \ge a_9$ ~w_\text{user} \ge a_9~
$8$ ~8~	$w_\text{user} \ge a_8$ ~w_\text{user} \ge a_8~
$7$ ~7~	$w_\text{user} \ge a_7$ ~w_\text{user} \ge a_7~
$6$ ~6~	$w_\text{user} \ge a_6$ ~w_\text{user} \ge a_6~
$5$ ~5~	$w_\text{user} \ge a_5$ ~w_\text{user} \ge a_5~
$4$ ~4~	$w_\text{user} \ge a_4$ ~w_\text{user} \ge a_4~
$3$ ~3~	$w_\text{user} \ge a_3$ ~w_\text{user} \ge a_3~
$2$ ~2~	$w_\text{user} \ge a_2$ ~w_\text{user} \ge a_2~
$1$ ~1~	$w_\text{user} \ge 0$ ~w_\text{user} \ge 0~

If multiple conditions are satisfied, then the condition that yields the highest score will be taken.

Problem translated to English by Alex.

Comments

There are no comments at the moment.