Problem C
Tycho
Languages
da
de
en
fi
lt
lv
pl
uk
Космічний дослідницький корабель Tycho VIII повинен повернутися до бази після збору мінеральних зразків. Tycho рухається прямою лінією з позиції $0$ до дому на позицію $b$. Рухаючись, він продовжує свій шлях повільною, але сталою швидкістю $1$ одиниця на секунду. Кожну секунду Tycho отримує $1$ одиницю пошкоджень від важких планетарних умов.
Ситуацію ускладнює радіація від недалекої пульсари, яка додає $d$ додаткових одиниць пошкоджень кожні $p$ секунд. Однак радіаційних пошкоджень можна уникнути, шукаючи укриття в одному з $n$ різних місць для приховування—печерах, рослинностях, великих каменях, трупах мегафауни планети—під час подорожі. Tycho може вибрати будь-яку точку на маршруті та стояти на місці будь-яку цілу кількість секунд.
Початкова позиція $0$ та дім на $b$ обидва мають укриття, тому Tycho не отримує радіаційні пошкодження там.
Яке є мінімальне пошкодження, яке отримає Tycho під час повернення до дому?
Приклад
Розглянемо ситуацію, де дім знаходиться на позиції $18$, а укриття є на позиціях $8$ та $15$.
Припустимо, що період випромінювання пульсара дорівнює $4$, тому якщо Tycho не заховується в укритті, він отримуватиме пошкодження у моменти часу $4$, $8$, $12$ тощо. Якщо Tycho вирушає зі стартової позиції (де він прихований від радіації) у час $0$, то він може дістатися до першого укриття через $8$ секунд, отримавши випромінювання $d$ у час $4$ (але не отримуючи випромінювання в час $8$, оскільки тоді він захищений). Продовжуючи рух без зупинки, він дістається до бази в позиції $b$ в час $18$, зазнавши ще $d+d$ одиниць радіаційної шкоди (у часи $12$ та $16$ відповідно). Таким чином, він зазнає $d+d+d=3d$ одиниць радіаційної шкоди та $18$ одиниць шкоди від навколишнього середовища. Якщо ж Tycho зупиниться на другому укритті (у позиції $15$) на $1$ секунду, то у цей час удар пульсара у час $16$ не завдасть йому шкоди, і він дістанеться до бази в позиції $b$ в час $19$ із загальним дискомфортом $2d + 19$ одиниць. Це краще для більшості значень $d$. Обидві ситуації показані тут:
Якщо період пульсара дорівнює $10$, то Tycho може зачекати на початковій позиції протягом $2$ секунд, а потім просто повернутися додому, не зупиняючись в жодному укритті. Таким чином, він проходить перше укриття (на позиції $8$) саме в той момент, коли пульсар спалахує і прибуває до дому в час $20$, із загальним збитком від навколишнього середовища $20$ і жодної шкоди від радіації.
Вхідні дані
$0<a_1<\cdots <a_ n< b$. Перший рядок містить чотири цілих числа $b$, $p$, $d$ і $n$, розділені одинарним пробілом: розташування домашньої бази $b$, період спалахів пульсара $p$, додаткові радіаційні збитки $d$, спричинені кожним спалахом пульсара, кількість прихистків $n$. Наступні $n$ рядків містять ціле число, що вказує розташування прихистків $a_1$, $\ldots $, $a_ n$, де $0<a_1<\cdots <a_ n< b$.
Вихідні дані
Виведіть одне ціле число: мінімальну кількість пошкоджень, яку Tycho повинен зазнати, щоб досягти місця призначення $b$.
Обмеження та оцінювання
Ви можете припустити, що $p < b$ та $n < b$. Ми завжди маємо: $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, та $0\leq n \leq 10^5$.
Ваше рішення буде перевірено на наборі тестових груп, кожна з яких має певну кількість балів. Кожна група містить певну кількість тестових випадків. Щоб отримати бали за групу тестів, потрібно вирішити всі тестові випадки в цій групі. Ваш кінцевий бал буде максимальним балом за одне відправлення.
Група |
Бали |
Обмеження |
$1$ |
$8$ |
$p\leq 10^6$ та Tycho не повинен чекати після виходу з позиції $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$ |
Без додаткових обмежень |
$^*$ У групі тестів $1$ Tycho може все ще потрыбно чекати в позиції $0$ перед початком руху. Наприклад, вхідні дані для прикладів $2$, $3$, та $4$ належать до групи тестів $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 |