Maximizing Floating Egg Collection Score

Sue is on a mission to collect all floating colored eggs in a thrilling sea adventure. The eggs fall from the sky and their charm value decreases over time. Collecting an egg yields a score equal to its current y-coordinate divided by 1000. However, if an egg falls into the sea the charm (and thus the score) turns negative. Sue starts at a given position on the x-axis and can move along it at a speed of 1 unit per time unit. When positioned directly beneath an egg, she can use her secret weapon to instantly collect it.

Each egg i is initially located at an integer coordinate \((x_i, y_i)\) and falls vertically at a constant speed \(v_i\) (units per time unit). At time \(t\), the y-coordinate of egg \(i\) becomes \(y_i - v_i\,t\). Collecting an egg at time \(t\) gives a score of \(\frac{y_i - v_i\,t}{1000}\>.

The challenge is to determine the order in which to collect all eggs to maximize the total score.

Modeling the Problem:

The sea is approximated as the x-axis in a vertical plane. Sue’s initial position is \((x_0,0)\). When she moves, the time it takes is equal to the distance traveled (since her speed is 1 unit per time unit). Note that while moving, all remaining (uncollected) eggs continue falling, and each unit of time delay reduces the score of every remaining egg by its fall speed \(v_i\) (multiplied by 1 unit of time). Thus, if at some point the boat moves a distance \(d\) while there is a total remaining falling speed of \(R\), then an additional penalty of \(d \times R\) is incurred on the eventual total score sum (when you sum over the eggs, this delay subtracts from the original charm values \(y_i\)).

If we denote by \(\mathcal{R}(t)\) the sum of falling speeds of the eggs not yet collected, then the total penalty accumulated is the sum of the products of the time increments (i.e. travel distances) and the remaining speeds. With a total initial speed sum of \(V_{total}\) and a particular route resulting in a total travel time penalty of \(P\), the total score is given by:

[ \text{Score} = \frac{\sum_{i=1}^{N} y_i - P}{1000}. ]

The goal is thus to plan a route along the x-axis for collecting all eggs (remember, Sue can only move horizontally) so that the penalty \(P\) is minimized and the score is maximized.

Dynamic Programming Approach (on a line):

Sort the eggs into two groups according to their x-coordinate relative to \(x_0\): eggs on the left (with their distance from \(x_0\) stored as a positive value) and eggs on the right. Let \(L\) (and \(R\)) be the number of eggs on the left (and right, respectively). Define two DP states:

• dp_left[i][j]: the minimal total penalty incurred after collecting \(i\) eggs from the left and \(j\) eggs from the right, when the last collected egg is from the left side (located at \(x_0 - d_{left}[i-1]\)).
• dp_right[i][j]: similar, but with the last collected egg from the right side (located at \(x_0 + d_{right}[j-1]\)).

For a given state with \(i+j\) eggs collected, the remaining falling speed is \(R = V_{total} - (\text{sum of speeds of collected eggs})\). When moving from a state and traveling a distance \(d\) to collect the next egg, an extra penalty of \(d \times R\) is incurred.

The transitions are as follows:

• From dp_left[i][j] (current position at \(x_0 - L[i-1]\)):
  • If taking another egg from the left (if available), the additional distance is \(d = d_{left}[i] - d_{left}[i-1]\) (and if \(i = 0\), then \(d = d_{left}[0]\)).
  • If switching to the right side (if any egg remains on the right), the travel distance is \(d = d_{left}[i-1] + d_{right}[j]\) (or simply \(d = d_{right}[0]\) if \(i = 0\)).
• Similarly, from dp_right[i][j] (current position at \(x_0 + d_{right}[j-1]\)).

After computing the minimal total penalty \(P_{min}\) using DP, the maximum total score is:

[ \text{Answer} = \frac{\sum_{i=1}^{N} y_i - P_{min}}{1000}. ]

</p>

The following five solutions implement the above approach in Python 3, C++, Java, C, and JavaScript. They read the input, compute the optimal route using dynamic programming, and output the maximum achievable score with full precision (formatted appropriately).

inputFormat

The first line contains two integers \(N\) and \(x_0\) where \(N\) is the number of eggs.

Each of the next \(N\) lines contains three integers: \(x_i\), \(y_i\), and \(v_i\) representing the egg's initial x-coordinate, initial y-coordinate, and falling speed respectively.

You may assume that all coordinates are integers. Eggs with \(x_i < x_0\) are to the left and eggs with \(x_i \ge x_0\) are to the right of Sue's starting position.

outputFormat

Output a single floating-point number: the maximum possible total score, computed as \( (\sum y_i - P_{min})/1000 \), where \(P_{min}\) is the minimum penalty achievable. The result should be printed with a precision of at least three decimal places.

sample

3 10
8 100 2
12 150 1
10 120 3

0.360