Problem B: Rocket Stages
Many rockets are made up of several stages to increase efficiency.
When the fuel in one stage burns up, the stage can be discarded,
reducing the weight of the remaining rocket.
The first stage needs a strong engine capable of lifting the whole
rocket, while later stages can have smaller engines.
In this problem, you will determine which stages to put together to
maximize the upward velocity of the rocket when all the fuel has burned.
For each stage, you will be given:
- the mass S of the stage, in kilograms, when it is empty (without fuel),
- the mass L of the fuel, in kilograms, in the stage,
- the thrust T, in newtons, provided by the engine in the stage, and
- the fuel consumption C, in kilograms per second, of the stage.
Assume that the rocket points straight upward for the duration of the
flight. Two forces act on the rocket: the force of the engine,
which is T newtons upwards, and the force of gravity,
which is 9.8 M newtons downwards, where M is
the total mass of the rocket in kilograms, including fuel.
The acceleration of the rocket
is F divided by M metres per second per second upwards,
where F is the total net force acting on the rocket in newtons, and M
is the total mass of the rocket in kilograms, including fuel.
As soon as a stage finishes
burning, it is immediately discarded and the next stage starts to burn.
The final velocity of the rocket is the integral of the net acceleration
(due to gravity and the engine) over time.
Due to safety regulations, the net acceleration of the rocket is never
allowed to be downwards, until the rocket runs out of fuel.
Also due to safety regulations, the total mass of the rocket cannot exceed
10000 kilograms.
The rocket must have at least one stage.
Input Specification
The first line of input contains one integer specifying the number of
test cases to follow. Each test case begins with a line containing
an integer N, the number of rocket stages in the current test
case. There will be no more than 1000 stages. This line is followed by
N lines, one for each stage. Each of these lines contains the
four integers S, L, T, C that
describe a stage, as explained above. Each of these integers
can be represented by a 32-bit unsigned binary number.
The order of the stages as listed must be preserved but some
stages (including, possibly, the first stage) may be left out of the rocket. The stage listed first is at the
top of the rocket (and will burn last).
For every test case in the input, it is always possible to construct at
least one rocket satisfying all the requirements of the problem statement.
Sample Input
1
1
9999 1 1000000 1
Output Specification
For each test case, output a line containing a single integer, the
maximum possible speed in metres per second of the rocket when it has finished burning,
rounded to the nearest metre per second.
Output for Sample Input
90
Ondřej Lhoták, Gordon Cormack