408625: GYM103230 B Blue Puppy and UFOs

Blue Puppy is looking for his little brother Torty. It's time to go home, but Torty is still playing among sea turtles and jellyfish on the beach, which is an interval $$$[0, b)$$$.

Blue Puppy has $$$n$$$ UFOs hovering above the beach, where the $$$i$$$-th UFO covers an interval $$$[x_i, x_i + \ell)$$$ with surveillance cameras.

What is the minimum number of UFOs that have to move so that the $$$n$$$ UFOs together cover the whole length of the beach?

The first line contains three integers $$$n$$$, $$$\ell$$$, and $$$b$$$, where $$$1 \le n \le 10^5$$$, $$$1 \le \ell, b \le 10^9$$$, and $$$n\cdot\ell \ge b$$$. The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$, where $$$-10^9 \le x_i \le 10^9$$$. The intervals covered by the UFOs may overlap at their initial positions.

Print the minimum number of UFOs that have to move.

8 2 10
-1 -2 3 4 5 8 9 10

2

10 77510323 144050237
37352276 91207595 287623234 -48741332 272918498 233298117 162635825 18573522 -73431711 177103533

0

10 22312461 199036869
55220051 138331995 182876693 25339421 21654390 110080598 101291658 117659246 121368663 181018092

5

One of the best ways is to move the UFO at $$$[4, 6)$$$ to $$$[1, 3)$$$, and move the UFO at $$$[10, 12)$$$ to $$$[6, 8)$$$. Then the $$$8$$$ UFOs together cover the interval $$$[-2, 11)$$$, which contains the beach $$$[0, 10)$$$.