DriveTheCarHard | Topcoder Archive

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.

Definition

Class:: DriveTheCarHard
Method:: findMinimumFuel
Parameters:: int, int
Returns:: int
Method signature:: int findMinimumFuel(int total_time, int distance)
(be sure your method is public)

Notes

There is always a solution.

Constraints

total_time will be between 1 and 30000, inclusive.
distance will be between 1 and 30000, inclusive.

Examples

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.