P4272 [CTSC2009] Sequence Transformation

Given an integer sequence $X_1, X_2, X_3, \dots, X_N$ and three positive integers $Q, A, B$ that satisfy: - $1 \leq X_i \leq Q$ for any $1 \leq i \leq N$; - $X_i \leq X_{i+1}$ for any $1 \leq i < N$; - $A \leq \frac{Q - 1}{N - 1}$ and $A \leq B$. For any $1 \leq i \leq N$, perform the transformation $Y_i = X_i + \delta_i$, where $\delta_i$ is an integer, such that the new sequence $Y$ satisfies: - $1 \leq Y_i \leq Q$ for any $1 \leq i \leq N$; - $Y_{i+1} - Y_i \in [A, B]$ for any $1 \leq i < N$. For such a transformation, the required cost is defined as $\operatorname{TransformCost}(X, Y) = \sum_{i = 1}^{N}{\left\lvert\delta_i\right\rvert}$. The task is to find a transformation that minimizes $\operatorname{TransformCost}(X, Y)$.

The first line contains $4$ integers $N, Q, A, B$. The second line contains $N$ integers, namely $X_1, X_2, \dots, X_N$.

Output a single line with the minimal $\operatorname{TransformCost}(X, Y)$.

Sample Explanation. You can transform the sequence to $2\ 4\ 6$ or $1\ 3\ 5$. The former has a cost of $1$, and the latter has a cost of $2$. Therefore, the minimal $\operatorname{TransformCost}$ is $1$. Constraints. For $10\%$ of the testdata, $N \leq 100$, $Q \leq 10000$, $1 \leq A, B \leq 100$. For $30\%$ of the testdata, $N \leq 10000$, $Q \leq 10000$, $1 \leq A, B \leq 100$. For $60\%$ of the testdata, $N \leq 10000$, $Q \leq 10^9$, $1 \leq A, B \leq Q$. For $100\%$ of the testdata, $N \leq 500000$, $Q \leq 10^9$, $1 \leq A, B \leq Q$. Translated by ChatGPT 5