Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | police.in, police.out | Sursă | IIOT 2021-22 Runda 4 |
| Autor | Edoardo Morassutto | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Police
Fearsome William is still free, and the Police is searching him in Murder Boulevard!
This street is L meters long, and currently William is at x=0, trying to reach his nest at x=L.
Along this street there are N semaphores at positions X_i.
All the traffic lights are synchronized: at t=0 the green triggers, and will stay green for T seconds; at t=T the red triggers, and will stay red for T seconds; and then the cycle repeats.
William wants to reach his nest as quickly as possible, but he doesn't want to attract too much attention.
Therefore, he travels at a constant speed of 1 meter per second (the speed limit), and he will stop and wait if he's at a red semaphore.
Since he's very impatient, sometimes he may cross the red semaphore without waiting for the green, but he can do so at most R times.
Which is the least amount of time William needs to reach his nest?
Date de intrare
The first line of the input file police.in contains 4 integers: N (the number of semaphores), R (the number of semaphores William can skip), T (the half-period of the semaphores), and L (the length of the street).
The second line contains N integers: the coordinates X_i.
h2. Date de ieşire
The output file police.out contains a single line with an integer: the minimum time in seconds that will be needed to reach the nest.
Restricţii
- 1 ≤ R ≤ N ≤ 10000
- 1 ≤ T ≤ 1000
- N < L ≤ 10^9
- X[i] < L, for each semaphore
- X[i] < X[i+1] for each i from 0 to n-2
Exemplu
| police.in | police.out |
|---|---|
| 3 1 3 10 1 5 9 | 11 |
| police.in | police.out |
|---|---|
| 1 0 5 10 5 | 15 |
Explicaţie
In the \textbf{first sample case} there are 3 semaphores, of which 1 can be skipped. When William reaches the first semaphore he finds it green, so it will pass.
Then at t=5 he reaches the second semaphore (at x=5), but it is red (since t=3).
He has two choices: wait 1 second that it becomes green, or skip the semaphore.
\begin{itemize}
\item If he waits, he will start again at t=6, will reach the last semaphore (at t=10) and will skip it since it is red and he still has 1 skip remaining.
He reaches his nest at t=11.
\item If he skips it, he will reach the last semaphore at t=9, but it is red (it just became red).
There he has to wait 3 seconds that it becomes green again, leaving it at t=12.
He reaches his nest at t=13.
\end{itemize}
Therefore, the best solution is to wait at the second semaphore and skip the last one, reaching the nest in 11 seconds.
In the \textbf{second sample case} there is only one semaphore.
When William reaches it he finds it red (it just became red), and he will wait since he doesn't have any skip available.
