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)