Golden Miner Submission Problem

This is a submission answer problem based on a variant of the popular "Golden Miner" game. In this problem, the mine field is abstracted as a rectangle of size \(2s \times s\) with the top-left corner as the origin, and the positive x-axis going to the right and the positive y-axis going down.

The miner starts at coordinate \((s, 0)\) and is allowed to move along the segment from \((0, 0)\) to \((2s, 0)\). The items (gold and other objects) are represented by non-intersecting circles inside the rectangle. Each circle has a value (which may be positive or negative).

The grabbing process is abstracted as shooting a ray from the miner. If the ray does not intersect any circle (note that tangency does not count), then the grab is invalid; otherwise, the miner will capture the circle whose first (nearest) intersection point (measured from the miner) is encountered.

Both moving and grabbing consume time. Moving 1 unit distance costs \(k_1\) time, and for a valid grab, every unit of distance from the miner to the intersection point costs \(k_2\) time. (Invalid grabs are ignored in time calculations.)

The objective of the game is to maximize the total value collected within a given time limit \(T\). However, the miner is lazy and will only accept at most \(2n\) operations (where \(n\) is the number of circles), no matter whether the operations result in a valid grab or not. Any operations in excess of this limit are ignored.

The judging uses an \(\epsilon\) of \(10^{-7}\): if the distances of the two intersection points of a ray with a circle differ by no more than \(10^{-7}\) then the circle is not considered intersected; similarly, if your total time spent exceeds the time limit by no more than \(10^{-7}\) it will be accepted.

Since this is a submission answer problem, the input data, scoring parameters, and checker will be provided for download. You are required to output your sequence of commands (each being a move or a grab) according to the output format described below.

Note: If at any moment the cumulative time exceeds \(T\), that operation and all subsequent operations will be ignored.

inputFormat

The input is given in the following format:

s n k1 k2 T
x1 y1 r1 v1
x2 y2 r2 v2
... (n lines total)

Where:

• \(s\) is a positive integer representing half of the width of the mine field.
• \(n\) is the number of circles (items).
• \(k_1\) is the time cost per unit distance of movement.
• \(k_2\) is the time cost per unit distance for a valid grab.
• \(T\) is the total time limit allowed.
• Each of the next \(n\) lines contains four numbers \(x_i\), \(y_i\), \(r_i\), \(v_i\) representing the center, radius of the circle, and its value respectively.

All numbers are separated by spaces.

outputFormat

The output should begin with an integer \(m\) (where \(0 \le m \le 2n\)) representing the number of operations your solution will execute. Each of the following \(m\) lines should describe one operation in one of the formats below:

• MOVE d --- where d is a floating-point number representing the horizontal distance to move. The miner moves along the x-axis. (Movement cost is computed as \(d \times k_1\)).
• GRAB \(\theta\) --- where \(\theta\) is a floating-point number (in radians) representing the angle of the shot relative to the positive x-axis. (For a valid grab, the time cost is computed as the distance from the miner to the intersection point multiplied by \(k_2\)).

If no operation is performed, simply output 0.

sample

10 1 1 2 100
5 5 1 100

0