Round Trip
InterviewTime limit1sMemory limit256 MB
A runner travels out and back along N courses given by their lengths; given total distance K, print which course the runner is on or about to enter.
- Level
Medium4 of 10
- Topics
- Array, Prefix sum, Binary search, Implementation
- Solved
- No attempts yet
Problem
A round-trip runner must pass through all N courses laid end to end on a straight line, reach the far end, and then return to the starting point. Given that the runner has covered distance K while traversing the courses, write a program that prints the number of the course the runner is currently on. If the distance K falls between two courses, print the number of the course the runner has yet to pass.
For example, let N=5 and the course lengths be 7, 4, 2, 4, 5 in order. Taking the starting point as 0, the layout of the courses can be drawn as follows.

- When K=0, the runner is on course 1, so print 1.
- When K=7, the runner is on course 2, so print 2.
- When K=9, the runner is on course 2, so print 2.
- When K=12, the runner is on course 3, so print 3.
- When K=28, this can be seen as the runner having reached the far end and returning to the starting position. The runner is on course 4, so print 4.
Also, K is always given as a positive integer smaller than the round-trip distance, or 0. For the example above, where the sum of all course lengths is 22, 0≤K≤43.
Input
The first line gives the integers N and K, separated by a space. (1≤N≤100,000) K is always a positive integer smaller than the round-trip distance, or 0. The second line gives the lengths of courses 1 through N in order, separated by spaces. Each course length is a natural number less than or equal to 50,000.
Output
On the first line, print the number of the course the runner is on when the distance covered is K.