Server
InterviewTime limit1sMemory limit256 MB
Count how many jobs from the front finish in request order before their total duration exceeds T.
- Level
Easy1 of 10
- Topics
- Prefix sum, Simulation
- Solved
- No attempts yet
Problem
You run a server that handles requested jobs under the FCFS (First-Come, First-Served) rule. Each day you can give the server at most minutes of time. You want to know how many jobs finish within today's time.
FCFS handles jobs only in the order the requests arrived. You cannot skip a job to handle a later one first, and once the remaining time is too short to finish a job, none of the jobs after it are handled either.
Suppose and the job durations, in request order, are 45, 30, 55, 20, 80, and 20 minutes. Then 4 jobs finish. The first four jobs take 150 minutes in total and fit inside the given time, but the first five take 230 minutes, which is more than 180. The sixth job on its own would fit in the remaining time, but the fifth job never finished, so the sixth job is not handled.
Input
The first line contains two integers and (, ), where is the number of jobs.
The second line contains natural numbers in request order. Each number is at most 100 and gives that job's duration in minutes.
Output
Print how many jobs finish within minutes when the jobs are handled under the FCFS rule.