DriveTheCarEasy
TCO19 SRM 738 · 2018-09-29 · by wild_hamster
Problem Statement
You are driving a car along a long straight road. Initially your car has the speed of 0 meters/second. You are going to drive for S seconds. We will number these seconds from 1 to S, inclusive.
You are given N pairs of integers (moments[i], speed_changes[i]). Each such pair has the following meaning: Immediately before second number moments[i] you will instantly increase the speed of your car by speed_changes[i] meters/second.
Compute and return the total distance the car will travel during those S seconds.
Constraints
- S will be between 1 and 109, inclusive.
- N will be between 1 and 100, inclusive.
- speed_changes and moments will have exactly N elements each.
- Each element of speed_changes will be between 1 and 1000, inclusive.
- Each element of moments will be between 1 and S, inclusive.
1000
1
{1000}
{1}
Returns: 1000000
At the beginning (before second number 1) you increase the speed of your car from 0 m/s to 1000 m/s. The car then moves at this speed for 1000 seconds, so it will travel 1,000,000 meters.
5
5
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
Returns: 35
The speed during each second will be 1, 3, 6, 10 and 15 m/s respectively, so the answer is 1+3+6+10+15 = 35 meters.
100
5
{1, 2, 3, 4, 5}
{100, 100, 100, 100, 100}
Returns: 15
Note that moments may contain the same value multiple times. If it does, each occurrence should be processed separately. In this example your car stands still for 99 seconds. Then, immediately before the second #100, five separate speedups occur. In total, you increase the speed of your car by 1+2+3+4+5 = 15 m/s. Thus, during second #100 the car will travel 15 meters.
1000000000
3
{1000, 1000, 1000}
{3, 2, 1}
Returns: 2999999997000
Note that the elements of moments do not have to be sorted. Watch out for integer overflow.
100
10
{522,426,772,447,497,775,982,417,932,728}
{75,45,81,29,2,25,84,56,2,37}
Returns: 367474
Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DriveTheCarEasy with a public method long long calculateDistance(int S, int N, vector<int> speed_changes, vector<int> moments) · 47 test cases · 2 s / 256 MB per case