P6473 [NOI Online #2 Junior] Unfinished

For offending the gods, Sisyphus is going to be punished. Zeus orders Sisyphus to push a huge boulder up a slope of length $L$. Sisyphus pushes upward at a constant speed of $v$ units per year (since the speed is constant, after $\frac{1}{2}$ year he can push upward by $\frac{v}{2}$ units). However, Zeus does not want Sisyphus to reach the top too quickly. Zeus can cast $n$ spells. If Zeus casts the $i$-th spell $(1\leq i \leq n)$, then when Sisyphus reaches position $a_i$ for the first time, he and the boulder will roll back to the bottom and start pushing again from the beginning. (The rolling time is ignored, i.e., it can be considered that right after reaching position $a_i$ for the first time, Sisyphus immediately restarts from the bottom.) For example, Zeus casts two spells with $a_i=3$ and $a_i=5$. If Sisyphus’s speed is $v=1$ and the slope length is $L=6$, then the pushing process is as follows: - Spend $3$ years to reach position $3$. - Affected by the spell $a_i=3$, return to the bottom and start again. - Spend another $3$ years to reach position $3$, but since this is the second time reaching it, the spell $a_i=3$ no longer takes effect. - Spend $2$ years to reach position $5$. - Affected by the spell $a_i=5$, return to the bottom and start again. - Spend $6$ years to go from the bottom to the top. The total time is $14$ years. Now, Zeus has $q$ queries. For the $i$-th query $t_i$, Zeus wants to know the minimum number of spells he needs to cast so that the number of years Sisyphus spends to reach the top is greater than $t_i$.

The first line contains three integers $n,L,v$, representing the number of spell types, the length of the slope, and Sisyphus’s speed. The second line contains $n$ integers. The $i$-th integer $a_i$ indicates the position where the $i$-th spell takes effect. $(1

Output $q$ lines, each containing exactly one integer. The integer on the $i$-th line is the answer to the $i$-th query. $(1 \leq i\leq q)$ If Zeus cannot make Sisyphus spend more than $t_i$ years no matter what, output $-1$.

1. Without using any spell, Sisyphus needs $2$ years to reach the top. 2. Using spell $2$, Sisyphus needs $\frac{11}{3}$ years to reach the top. (It takes $\frac{5}{3}$ years to reach the position of spell $2$ and roll down, then it takes $\frac{6}{3}=2$ years to reach the top.) 3. Using spells $1,2$, Sisyphus needs $\frac{14}{3}$ years to reach the top. 4. Zeus cannot make Sisyphus take more than $5$ years to reach the top. For test points $1\sim 8$: $n=1$. For test points $9\sim 12$: $n=2$. For test points $13\sim 17$: $n,q\le 1000$. For all test points: $1 \leq n,q \leq 2 \times 10^5$, $1\leq v\leq L\leq 10^{9}$, $1\leq a_i < L$, $1 \leq t_i\leq 10^9$. The testdata guarantees that all $a_i$ are pairwise distinct. Translated by ChatGPT 5