The long road through Farmer John's farm has \(N\) crosswalks across it,
conveniently numbered \(1 \ldots N\) (\(1 \leq N \leq 100,000\)). To allow cows to
cross at these crosswalks, FJ installs electric crossing signals, which light up
with a green cow icon when it is ok for the cow to cross, and red otherwise.
Unfortunately, a large electrical storm has damaged some of his signals. Given
a list of the damaged signals, please compute the minimum number of signals that
FJ needs to repair in order for there to exist some contiguous block of at least
\(K\) working signals.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(N\), \(K\), and \(B\) (\(1 \leq B, K \leq N\)). The
next \(B\) lines each describe the ID number of a broken signal.

Please compute the minimum number of signals that need to be repaired in order
for there to be a contiguous block of \(K\) working signals somewhere along the
road.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Silver