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
250
13922
Returns: 64
250
14106
Returns: 65
250
14108
Returns: 65
250
14110
Returns: 65
250
14291
Returns: 66
250
14293
Returns: 66
250
14473
Returns: 67
250
14475
Returns: 67
250
14477
Returns: 67
250
14656
Returns: 68
300
22296
Returns: 87
300
22298
Returns: 87
300
22300
Returns: 87
300
22302
Returns: 87
300
22304
Returns: 87
300
22486
Returns: 88
300
22488
Returns: 88
300
22490
Returns: 88
300
22492
Returns: 88
300
22494
Returns: 88
300
22496
Returns: 88
300
22498
Returns: 88
300
22500
Returns: 88
300
22502
Returns: 88
300
22504
Returns: 88
300
22506
Returns: 88
370
30000
Returns: 93
410
30000
Returns: 82
450
30000
Returns: 73
490
30000
Returns: 66
530
30000
Returns: 60
570
30000
Returns: 56
610
30000
Returns: 52
255
29664
Returns: 179
255
29749
Returns: 180
255
29833
Returns: 181
255
29835
Returns: 181
255
29918
Returns: 182
255
30000
Returns: 183
256
29753
Returns: 178
256
29922
Returns: 180
257
29926
Returns: 178
255
29748
Returns: 180
255
29750
Returns: 180
255
29834
Returns: 181
255
29917
Returns: 182
255
29919
Returns: 182
256
29667
Returns: 177
256
29838
Returns: 179
256
29923
Returns: 180
252
29893
Returns: 188
252
29895
Returns: 188
252
29897
Returns: 188
252
29899
Returns: 188
252
29901
Returns: 188
252
29903
Returns: 188
245
29996
Returns: 204
246
29997
Returns: 202
246
29999
Returns: 202
20522
24575
Returns: 2
6426
9445
Returns: 2
18772
81
Returns: 1
13447
10629
Returns: 1
23497
27202
Returns: 2
27775
24325
Returns: 1
3982
14784
Returns: 4
18417
2156
Returns: 1
1932
5902
Returns: 4
5728
18537
Returns: 4
2522
28575
Returns: 12
426
8445
Returns: 21
772
25081
Returns: 34
1447
3629
Returns: 3
2497
27202
Returns: 11
775
4325
Returns: 6
982
26784
Returns: 28
417
22156
Returns: 57
1932
25902
Returns: 14
2728
18537
Returns: 7
122
28575
Returns: 1344
126
8445
Returns: 118
172
25081
Returns: 383
247
3629
Returns: 16
97
27202
Returns: 2404
2
21836
Returns: 95362180
6
24155
Returns: 6411694
22
21011
Returns: 116330
7
3592
Returns: 92162
7
5988
Returns: 256116
25
8994
Returns: 14644
22
9628
Returns: 24429
27
15508
Returns: 34707
12
8808
Returns: 119357
28
7466
Returns: 7229
2
9070
Returns: 16452980
3
14780
Returns: 15603458
1
7091
Returns: 50282281
1
15264
Returns: 232989696
1
15612
Returns: 243734544
1
24675
Returns: 608855625
1
17909
Returns: 320732281
3
6661
Returns: 3169209
3
18642
Returns: 24823155
1
8467
Returns: 71690089
250
28054
Returns: 169
250
28055
Returns: 169
250
28056
Returns: 170
250
28135
Returns: 170
250
28136
Returns: 170
251
28305
Returns: 170
251
28306
Returns: 170
252
28557
Returns: 171
252
28558
Returns: 171
253
28728
Returns: 171
253
28729
Returns: 171
253
28730
Returns: 172
254
28982
Returns: 172
254
28983
Returns: 172
254
28984
Returns: 172
254
28985
Returns: 173
254
29064
Returns: 173
254
29065
Returns: 173
257
29667
Returns: 174
257
29668
Returns: 174
257
29669
Returns: 174
257
29670
Returns: 175
257
29993
Returns: 178
257
29994
Returns: 178
258
29925
Returns: 175
258
29926
Returns: 175
258
29927
Returns: 175
258
29928
Returns: 175
258
29929
Returns: 176
30000
30000
Returns: 1