CALLIM - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N sweets in a row, the i-th has a calorie count of A_i.
How many of them can be eaten from the front, while not exceeding a calorie count of K?

EXPLANATION:

This is a simple implementation task - do exactly what the statement says.
That means:

  1. Store a variable S that denotes the total calories eaten so far, and another variable \text{ans} that denotes the answer.
    Initially, S = \text{ans} = 0.
  2. For i = 1, 2, 3, \ldots, N in order,
    • If S + A_i \leq K, the i-th sweet can be eaten.
      So, increase S by A_i and also increase \text{ans} by 1.
    • If S+A_i \gt K, it’s impossible to eat the i-th sweet, so break out immediately.

Print \text{ans} in the end.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    ans, sm = 0, 0
    for x in map(int, input().split()):
        if sm+x > k: break
        ans += 1
        sm += x
    print(ans)