Shuttle run
Statement
A student stands on a straight running track, starting at position 0. This student is going to do a shuttle run. With N points on the straight line in total, the student's goal is to touch every point from point 1 to point N in order. There is one rule, though. For the K points closest to 0, the student has to come straight back to position 0 right after touching the point. Specifically, K is a natural number from 1 to N-1.
The student takes 1 second to move a distance of 1, and the run ends once all N points have been touched. Write a program that computes the time it takes until the run ends.
The input is a one-dimensional array of size N, and the position of each point is given sorted in ascending order of distance from 0. For example, when N=6 and K=3, suppose the position of each point is given as follows.
| Number | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Position | 3 | 7 | 10 | 12 | 15 | 19 |
In the current example the student has to come back to position 0 after reaching point 1, point 2 and point 3, so the total time needed in this example is 3 + 3 + 7 + 7 + 10 + 10 + 12 + 3 + 4 = 59 seconds.
Input and Output Examples
Example 1
Input
6, 3, [3, 7, 10, 12, 15, 19]
Output
59
Example 2
Input
10, 5, [1, 3, 3, 5, 6, 9, 10, 15, 20, 25]
Output
61
Input
First the number of points N is given as a natural number. N is a natural number from 3 to 200,000.
Next K, the number of points to touch and come back from, is given as a natural number. K is a natural number less than or equal to N-1.
Next an array arr is given, holding the position information of the points numbered 1 through N. Each position value is a natural number less than or equal to 1,000,000,000. The position values never repeat. The input array arr is given with its position values already sorted in ascending order.
Output
Return the time the student needs to touch all N points while meeting the conditions of this problem.
Requirements
- You must write a solution(N, K, arr) function and return the answer
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 15 cases, and 2 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 15 cases to solve this.
Examples
2 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.
6, 3, [3, 7, 10, 12, 15, 19]
59
10, 5, [1, 3, 3, 5, 6, 9, 10, 15, 20, 25]
61
Notes
Background that helps with solving. The rules you have to follow are in the input and output specs and the requirements above.
This is problem 1 of practice test 9 in the original.
The arr in the second input and output example holds 3 twice. That contradicts the input condition that the position values never repeat, but the original has been carried over as it is.
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 2 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Input read time 256ms (excluded from the ranking)
Log in and you can see the code once you solve this problem.