Problem C
Tycho
Languages
da
de
en
fi
lt
lv
pl
uk
Pojazd do eksploracji planet Tycho VIII musi wrócić do bazy macierzystej po zebraniu próbek minerałów. Tycho podróżuje w linii prostej z pozycji $0$ do bazy domowej na pozycji $b$. Podczas ruchu posuwa się do przodu w wolnym, ale stałym tempie $1$ jednostki na sekundę. W każdej sekundzie Tycho ponosi $1$ jednostkę szkód środowiskowych spowodowanych trudnymi warunkami panującymi na planecie.
Sytuację pogarsza jeszcze promieniowanie z pobliskiego pulsara, które dodaje $d$ dodatkowych jednostek obrażeń co $p$ sekund. Obrażeń od promieniowania można jednak uniknąć, szukając schronienia w jednej z $n$ różnych kryjówek — jaskiniach, roślinności, dużych skałach, padlinach megafauny planety — po drodze. Tycho może zdecydować się na stanie w miejscu przez dowolną liczbę całkowitą sekund.
Pozycja startowa $0$ i baza domowa $b$ są osłonięte, więc Tycho nie otrzymuje tam żadnych obrażeń od promieniowania.
Jaka jest najmniejsza sumaryczna liczba obrażeń otrzymanych przez Tycho w drodze powrotnej do bazy?
Przykład
Rozważ sytuację, w której baza macierzysta znajduje się na pozycji $18$, a na pozycjach $8$ i $15$ znajdują się schrony.
Przyjmij, że okres pulsara to $4$, więc Tycho poza schronieniem odbierałby obrażenia w momentach $4$, $8$, $12$, itd. Jeśli Tycho wyjdzie z pozycji startowej (gdzie jest osłonięty) w czasie $0$, może dotrzeć do pierwszego schronu po $8$ sekundach, ponosząc obrażenia od promieniowania $d$ w czasie $4$ (ale żadnych w czasie $8$, ponieważ jest wtedy osłonięty). Kontynuując bez zatrzymywania się, dociera do bazy domowej w czasie $18$, ponosząc $d+d$ kolejnych jednostek obrażeń od promieniowania (odpowiednio w czasie $12$ i $16$). W ten sposób ponosi $d+d+d=3d$ jednostek obrażeń od promieniowania i $18$ jednostek obrażeń od środowiska. Jeśli zamiast tego Tycho czeka w schronie o numerze $2$ (na pozycji $15$) przez $1$ sekundę, impuls w czasie $16$ nie powoduje żadnych obrażeń, a do bazy macierzystej dociera w czasie $19$ z łączną liczbą $2d + 19$ jednostek obrażeń. Jest to lepsze rozwiązanie dla większości wartości $d$. Te dwie sytuacje są pokazane tutaj:
Jeśli okres pulsara wynosi $10$, Tycho może czekać na pozycji startowej przez $2$ sekundy, a potem po prostu wrócić do domu, nie zatrzymując się w żadnym schronie. W ten sposób mija schron o numerze $1$ (na pozycji $8$) we właściwym momencie, gdy pulsar rozbłyska i dociera do bazy macierzystej w czasie $20$, za łączną sumę $20$ szkód środowiskowych i żadnych szkód radiacyjnych.
Wejście
Pierwsza linia składa się z czterech liczb całkowitych $b$, $p$, $d$, oraz $n$, oddzielonych pojedynczymi spacjami: lokalizacji bazy domowej $b$, okresu rozbłysku pulsara $p$, dodatkowych szkód radiacyjne $d$ spowodowane przez każdą flarę pulsara, oraz liczby schronów $n$. Kolejne $n$ wierszy zawierają po jednej liczbie całkowitej oznaczającej lokalizacje schronów $a_1$, $\ldots $, $a_ n$, spełniające $0<a_1<\cdots <a_ n< b$.
Wyjście
Wypisz pojedynczą liczbę całkowitą: minimalną ilość obrażeń, jakie musi przyjąć Tycho, by dotrzeć na pozycję $b$.
Ograniczenia i punktacja
Możesz założyć $p < b$ oraz $n < b$. Zawsze jest spełnione $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, oraz $0\leq n \leq 10^5$.
Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda jest warta pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.
Grupa |
Punkty |
Ograniczenia |
$1$ |
$8$ |
$p\leq 10^6$ oraz Tycho nie musi czekać po wyjściu z pozycji $0$.$^*$ |
$2$ |
$5$ |
$b\leq 1000$, $p\leq 100$, $n\leq 10$ |
$3$ |
$7$ |
$b\leq 1000$ |
$4$ |
$15$ |
$p\leq 10^6$, $n\leq 1000$ |
$5$ |
$20$ |
$p\leq 100$ |
$6$ |
$35$ |
$p\leq 10^6$ |
$7$ |
$10$ |
Brak dodatkowych ograniczeń |
$^*$ W grupie testowej $1$, Tycho może nadal potrzebować czekać na pozycji $0$ zanim zacznie się poruszać. Na przykład, przykładowe wejścia $2$, $3$, oraz $4$ należą do grupy testowej $1$.
Sample Input 1 | Sample Output 1 |
---|---|
18 4 5 2 8 15 |
29 |
Sample Input 2 | Sample Output 2 |
---|---|
18 4 0 2 8 15 |
18 |
Sample Input 3 | Sample Output 3 |
---|---|
18 10 100 2 8 15 |
20 |
Sample Input 4 | Sample Output 4 |
---|---|
18 4 100 0 |
418 |
Sample Input 5 | Sample Output 5 |
---|---|
65 20 100 3 14 25 33 |
172 |