DriveTheCarHard
TCO19 SRM 738 · 2018-09-29 · by wild_hamster
Problem Statement
You are going to drive a car for exactly total_time seconds along a long straight road segment. Your goal is to travel exactly distance meters in those total_time seconds.
At the beginning of the drive the car is stationary (i.e., its speed is 0 meters per second).
At each integer timestamp you can speed up your car. (This includes the beginning of your trip.) More precisely, at any such moment you can choose any positive integer X and increment your car's speed by X m/s. Doing so instantly consumes X*X units of fuel. You can speed up as many times as you like, and you can choose different values of X at different moments if you want.
Find and return the minimum total amount of fuel needed.
Notes
- There is always a solution.
Constraints
- total_time will be between 1 and 30000, inclusive.
- distance will be between 1 and 30000, inclusive.
4 10 Returns: 4
An optimal solution: increment the speed of your car by 1 m/s at each of the timestamps 0, 1, 2, and 3. Thus: During the first second of your trip the car will travel at 1 m/s. During the second second of your trip the car will travel at 2 m/s. During the third second of your trip the car will travel at 3 m/s. During the fourth second of your trip the car will travel at 4 m/s. The total distance traveled in those four seconds will be 1+2+3+4 = 10 m. Each speed-up will require 1*1 = 1 units of fuel for a total of 1+1+1+1 = 4 units.
5 33 Returns: 21
If you are driving for five seconds, there are five moments at which you can raise the speed of your car. In this test case you should increment your car's speed by 3, 3, 1, 1, and 1 m/s, respectively. Doing so will consume 3*3 + 3*3 + 1*1 + 1*1 + 1*1 = 21 units of fuel. The car will travel 3 + 6 + 7 + 8 + 9 = 33 meters.
1 30000 Returns: 900000000
228 29595 Returns: 242
250 13922 Returns: 64
Submissions are judged against all 138 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DriveTheCarHard with a public method int findMinimumFuel(int total_time, int distance) · 138 test cases · 2 s / 256 MB per case