MagicalRocketCar
TCO 2014 Finals · 2014-03-26 · by snuke
Problem Statement
Fox Ciel has a new Magical Rocket Car. Ciel wants to use the car to drive as far as possible.
The Magical Rocket Car has multiple fuel tanks, each containing special magical fuel of some type. While driving, Fox Ciel will have to choose an order in which to use the fuel tanks. (Once she starts using a fuel tank, she has to continue using it until it becomes empty.)
Additionally, each fuel tank can be used in one of two modes.
You are given two
- Mode 1: The Magical Rocket Car will maintain a constant acceleration of x[i]/y[i] for y[i] seconds.
- Mode 2: The Magical Rocket Car will maintain a constant acceleration of y[i]/x[i] for x[i] seconds.
In both cases, the acceleration is given in meters per second squared (m/s^2). For each fuel tank, Ciel must choose one of these two modes.
The car will only move while Ciel uses some fuel tank. As soon as the last fuel tank runs out, the car will use its magic to stop immediately.
Compute and return the maximal distance in meters Ciel can travel in the Magical Rocket Car.
Notes
- Your return value must have absolute or relative error smaller than 1e-9.
Constraints
- x will contain between 1 and 100 integers, inclusive.
- x and y will contain the same number of integers.
- Each integer in x and y will be between 1 and 100, inclusive.
{3}
{3}
Returns: 4.5
There is only one fuel tank. For this fuel tank both modes have the same effect: the car will accelerate at 1 m/s^2 for 3 seconds. The total distance covered during those 3 seconds will be 4.5 meters.
{1,2,4}
{4,3,3}
Returns: 48.0
One optimal solution looks as follows: Use fuel tank 1 in mode 2 to accelerate at 3/2 m/s^2 for 2 seconds. Use fuel tank 2 in mode 1 to accelerate at 4/3 m/s^2 for 3 seconds. Use fuel tank 0 in mode 1 to accelerate at 1/4 m/s^2 for 4 seconds.
{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}
{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100}
Returns: 5.0E7
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 5000.0
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100}
{100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}
Returns: 2.1167075E7
Submissions are judged against all 139 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MagicalRocketCar with a public method double getmax(vector<int> x, vector<int> y) · 139 test cases · 2 s / 256 MB per case