P1052 [NOIP 2005 Senior] Crossing the River

There is a single-plank bridge over a river. A frog wants to jump along the bridge from one side of the river to the other. There are some stones on the bridge, and the frog dislikes stepping on them. Since both the bridge length and each jump distance of the frog are positive integers, we can view all points the frog can reach on the bridge as the sequence of integer points on a number line: $0,1,\cdots,L$ (where $L$ is the length of the bridge). The point with coordinate $0$ is the starting point of the bridge, and the point with coordinate $L$ is the endpoint of the bridge. The frog starts at the starting point and keeps jumping toward the endpoint. Each jump distance is any positive integer between $S$ and $T$ inclusive. Once the frog reaches or passes the point with coordinate $L$, it is considered to have left the bridge. Given the bridge length $L$, the jump distance range $S, T$, and the stone positions on the bridge, your task is to determine the minimum number of stones the frog must step on to cross the river.

The input consists of three lines: - The first line contains $1$ positive integer $L$, the length of the bridge. - The second line contains $3$ positive integers $S, T, M$, denoting the minimum jump distance, the maximum jump distance, and the number of stones on the bridge, respectively. - The third line contains $M$ distinct positive integers giving the positions of these $M$ stones on the number line (it is guaranteed that there are no stones at the start or at the end of the bridge). All adjacent integers are separated by a single space.

Output a single integer: the minimum number of stones the frog must step on to cross the river.

- Constraints - For $30\%$ of the testdata, $1 \le L \le 10^4$. - For $100\%$ of the testdata, $1 \le L \le 10^9$, $1 \le S \le T \le 10$, $1 \le M \le 100$. - Source - NOIP 2005 Senior, Problem 2. Translated by ChatGPT 5