Every year since 2004, the Google Santa Tracker project has helped visualize the route taken by the legendary character Santa Claus each December to distribute gifts to kids around the world.
Though December is months away, preparations are in full swing at Santa's home in Lapland. The Google Santa Tracker is also getting ready, and rumors are that this year is going to be especially interesting. A secret team of Engineers in Lightspeed Flights (ELF), in collaboration with the Gnome Institute of Generous Gift Logistics Engineering (GIGGLE) in Lapland, is working to develop new experimental optimization algorithms that help Santa deliver gifts more effectively.
The early results are promising, but Santa thinks they can be improved. When Santa learned about the famous optimization skills of Hash Code participants, he asked if Hash Code World Finalists would be able to help out. Are you up for the challenge?
Santa is delivering gifts on a frictionless 2D plane, using a reindeerpowered sleigh that accelerates using… carrots 🥕.
Your task is to plan actions for the sleigh to make gift deliveries and maximize the total score.
The world is a 2D grid with integer coordinates. We refer to a cell at column $$$c$$$ and row $$$r$$$ as $$$(c, r)$$$ $$$(10^9 \leq c, r \leq 10^9)$$$.
The distance between two cells $$$(c_a, r_a)$$$ and $$$(c_b, r_b)$$$ is calculated as $$$\sqrt{c_a  c_b^2 + r_a  r_b^2}$$$ (Euclidean distance).
Santa starts at Lapland $$$(0,0)$$$ where all the gifts are stored.
Santa only has $$$T$$$ seconds to deliver the gifts, so hurry up!
There are two types of things Santa can load onto his sleigh: gifts and carrots.
Gifts need to be delivered to children around the world. You are given the list of $$$G$$$ gifts, for each of which you know:
Carrots are food for Santa's magic reindeer who need to eat them to accelerate. Each carrot weighs 1 kg (yes, we know they are heavy… but they really are magic!).
Thanks to a very effective team of helper gnomes, gift delivery happens instantaneously at the beginning of the second. Similarly, gift/carrots pick up happens instantaneously at the beginning of the second.
Santa can deliver gifts to all children within a maximum distance of $$$D$$$ (inclusive) from his sleigh. Similarly, Santa can pick up gifts and carrots whenever the sleigh is within a maximum distance of $$$D$$$ (inclusive) from his base at $$$(0, 0)$$$. We call this maximum distance of $$$D$$$ "range".
For example, for the range $$$D = 3$$$ and the sleigh at $$$(c,r)$$$:
Santa moves around the world on his magic sleigh.
Thanks to the magic coating on his sleigh, Santa encounters no friction and conserves speed indefinitely. At any point the movement of the sleigh can be described as its velocity $$$[s_c, s_r]$$$, denoting how fast the sleigh moves in each direction within one second.
Santa starts with the velocity of $$$[0, 0]$$$ (not moving).
For example, in the figure below the sleigh is initially at position $$$(c, r)$$$ and its velocity is $$$[1, 2]$$$.
As long as the velocity remains constant, after each second the sleigh will move $$$1$$$ position to the right and $$$2$$$ positions upwards.
Each second, Santa can choose to feed one carrot (previously loaded to the sleigh) to the reindeer to accelerate by a chosen value in one of four directions: up, down, left, right. “Acceleration” means changing the velocity. If the velocity is initially $$$[s_c, s_r]$$$ and Santa accelerates, then:
Note that the concept of “acceleration” (defined above) allows Santa to “decelerate” (slow down) as well. For example, if accelerating up by 2 makes Santa's sleigh go faster, then a subsequent “acceleration” down by 2 will make them go slower.
Santa can choose to accelerate, but even magic sleighs have their limitations! The maximum acceleration that Santa's reindeers can provide at a given moment depends on the current weight of the sleigh. The heavier the sleigh, the slower the maximum acceleration!
The weight of the sleigh is a sum of:
Each input data set specifies the maximum acceleration in given ranges of sleigh weights. Maximum acceleration of $$$a_i$$$ for sleigh weight range $$$(l_{i1}, l_i]$$$ means that the maximum acceleration is equal to $$$a_i$$$ (inclusive) for all sleigh weights of $$$w$$$ that meet the constraints of $$$l_{i1} \lt w \leq l_i$$$.
This sleigh weight above includes the carrot just about to be eaten by the reindeer. However, right after the acceleration, the carrot is eaten and converted into reindeer energy, instantenously reducing the weight of the sleigh by 1 kg.
If reindeer can't handle the weight of the sleigh ($$$ w $$$ is above maximum $$$ l_i $$$) they can't accelerate at all (max acceleration = 0). The sleigh keeps its speed and continues floating until acceleration becomes possible again (e.g. gifts are delivered) or the time runs out. Also if there are no carrots on the sleigh, acceleration is not possible!
The acceleration is instantaneous and happens in the beginning of the second. Santa's sleigh can only accelerate once per second (it must float for at least one second before another acceleration is possible).
Consider the example represented in the description and the figure below.
The acceleration ranges are as follows, for the sleigh weight denoted as $$$w$$$:
The initial weight of the sleigh consists of 20 kg of presents and 11 kg of carrots. So the total weight is 31 kg which means the maximum acceleration is 2. The initial velocity at $$$t$$$ seconds is $$$[2, 2]$$$.
Note that the weight of the sleigh is also updated when gifts are delivered to children.
Consider the example below. The sleigh movement is the same as in the figure above, but we add gift deliveries. The range is $$$D = 1$$$.
Observe that, even though between $$$t$$$ and $$$t+1$$$ the sleigh passes close to the gift delivery location at $$$(c, r+2)$$$, it is not possible to deliver it. This is because gift deliveries must happen at the beginning of a second, not while the sleigh is floating.
The sleigh can perform the following actions. All actions apart from “Float” are instantaneous (take 0 seconds). All actions can be performed regardless of whether the sleigh is moving (no need to stop to make deliveries or load the sleigh).
Accelerate in one of four directions (up, down, left or right) by a given acceleration (not more than the maximum acceleration for the current weight of the sleigh). The sleigh has to take the float action at least once between two consecutive accelerations.
Float for a number of seconds. The velocity of the sleigh remains constant during the float action.
Load a number of carrots. The sleigh needs to be within a distance $$$D$$$ from the initial position $$$(0, 0)$$$.
Load a given gift. The sleigh needs to be within a distance $$$D$$$ from the initial position $$$(0, 0)$$$.
Deliver a given gift. The delivery location of the given gift has to be within a distance $$$D$$$ from the sleigh's position.
For instance, the following 3 sequences of actions are valid:
Observe that in (3) the last "Accelerate up" action is not affecting the final position of the sleigh: the velocity is updated, but the sleigh doesn't move at the updated velocity until a "Float" command is issued.
The following 2 sequences of actions are invalid because there are two acceleration actions without any float action between them:
Each input data set is provided in a plain text file. The file contains only ASCII characters with lines ending with a single '\n' character (also called “UNIXstyle” line endings). When multiple strings and numbers are given in one line, they are separated by a single space between each two elements.
The first line of the input file contains:
The subsequent $$$W$$$ lines contain the acceleration ranges description  two integer numbers separated by a single space:
Note that the weight range of the sleigh for max acceleration $$$ a_i $$$ is $$$ [l_{i1}, l_i] $$$ where $$$l_0 = 0$$$. It is guaranteed that $$$ l_{i1} \lt l_i $$$ and $$$ a_{i1} \gt a_i $$$
The subsequent $$$G$$$ lines contain gift descriptions  strings and integer numbers separated by single spaces:
Every position $$$(c_i, r_i)$$$ in the datasets is guaranteed to have at most 1 gift recipient and Lapland at $$$(0,0)$$$ is guaranteed to have none.
Input file  Description 
15 3 4 4

15 seconds, delivery distance of 3, 4 acceleration ranges and 4
gifts

Note that the input file does not contain any blank lines. Blank lines and line wrapping in the example above are added for clarity.
You need to specify the actions for Santa.
The submission file must be a plain text file containing exclusively ASCII character lines terminated with a single '\n' character (“UNIXstyle” line endings).
The first line must contain a single integer $$$C$$$ ($$$0 \leq C \leq 10^6$$$): the number of actions for Santa.
Each of the following lines must contain a valid action for the sleigh. Each action description must contain the action name and the action argument, separated by a space. The possible actions are:
AccUp ⟨a⟩
 Accelerates in the “up” direction
by integer $$$a$$$ ($$$ 0 \leq a \leq a_i $$$, where $$$a_i$$$ is the
applicable maximum acceleration for the current weight of the sleigh)
AccDown ⟨a⟩
 Accelerates in the “down”
direction by integer $$$a$$$ ($$$ 0 \leq a \leq a_i $$$, where $$$a_i$$$
is the applicable maximum acceleration for the current weight of the
sleigh)
AccLeft ⟨a⟩
 Accelerates in the “left”
direction by integer $$$a$$$ ($$$ 0 \leq a \leq a_i $$$, where $$$a_i$$$
is the applicable maximum acceleration for the current weight of the
sleighh)
AccRight ⟨a⟩
 Accelerates in the “right”
direction by integer $$$a$$$ ($$$ 0 \leq a \leq a_i $$$, where $$$a_i$$$
is the applicable maximum acceleration for the current weight of the
sleigh)
Float ⟨t⟩
 Advances the time by integer
$$$t$$$ seconds ($$$1 \leq t \leq T$$$). In each second the position of
the sleigh advances by the current velocity.
LoadCarrots ⟨N⟩
 Loads integer N carrots onto
the sleigh ($$$1\leq N \leq 1,000,000$$$), only valid within a distance
$$$D$$$ inclusive from $$$(0, 0)$$$.
LoadGift ⟨ChildName⟩
 Loads a gift for the
given child, only valid within a distance $$$D$$$ inclusive from (0, 0).
DeliverGift ⟨ChildName⟩
 Delivers the gift for
the given child, only valid within a distance $$$D$$$ inclusive from the
child.
Submission file  Description 
23

The file describes 23 actions

Note that the submission file should not contain any blank lines. Blank lines and line wrapping in the example above are added for clarity.
Float
action in between).
Float
action after the time of
simulation ran out.
The score of your solution is the sum of the scores awarded for each gift that have been delivered.
For example, the sample solution scores 16 points: 1 for Olivia's gift, 5 for Liam's gift, and 10 for Bob's gift.
Note that there are multiple data sets representing separate instances of the problem. The final score for your team will be the sum of your best scores on the individual data sets.