GMGM - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: pols_agyi_pols
Testers: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have two guns: one that can shoot targets at a distance \leq D, and one that can shoot targets at a distance \gt D.
You’re initially holding the short-range gun. How many times will you need to change guns to shoot N targets in order, with the i-th being at a distance of A_i from you?

EXPLANATION:

Observe that you only need to change guns when you need to shoot a target that’s \gt D distance away immediately after shooting one that \leq D distance; or vice versa.

So, the number of changes required is just the number of indices i such that:

  • A_i \leq D and A_{i-1} \gt D; or
  • A_i \gt D and A_{i-1} \leq D.

This can be counted using a simple loop.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, d = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    ans = 0
    for i in range(1, n+1):
        ans += (a[i] <= d) != (a[i-1] <= d)
    print(ans)