Hide

Problem C
Tycho

Languages da de en fi lt lv pl uk
/problems/boi23.tycho/file/statement/fi/img-0001.jpg

Planeetantutkimusmönkijän Tycho VIII:n täytyy palata takaisin tukikohtaansa kerättyään mineraalinäytteitä. Tycho liikkuu suoralla viivalla pisteestä $0$ tukikohtaan pisteessä $b$. Se liikkuu eteenpäin hitaalla mutta varmalla $1$ yksikön nopeudella. Joka sekunti Tycho ottaa $1$ yksikön ympäristövahinkoa planeetan ankarien olosuhteiden takia.

Tilannetta pahentaa vielä lisää se, että läheisestä pulsarista tulee säteilyä, joka aiheuttaa $d$ yksikköä lisävahinkoa $p$:n sekunnin välein. Säteilyvahingon voi kuitenkin välttää etsimällä suojaa yhdestä $n$:stä eri piilopaikasta—luolista, kasvillisuudesta, suurista kivistä, planeetan megafaunan raadoista—matkan aikana. Tycho voi valita pysyä paikallaan missä tahansa kokonaislukumäärän sekunteja.

Sekä alkupiste $0$ että tukikohta $b$ ovat suojattuja, joten Tycho ei saa säteilyvahinkoa niissä ollessaan.

Mikä on pienin määrä vahinkoa, jonka Tycho voi saada matkallaan tukikohtaan?

Esimerkki

Tarkastellaan tilannetta, jossa tukikohta on kohdassa $18$ ja suojia on kohdissa $8$ ja $15$.

\includegraphics[width=.3\textwidth ]{img/samplesetup}

Oletetaan, että pulsarin jaksonaika on $4$, eli suojaamaton Tycho saisi vahinkoa hetkillä $4$, $8$, $12$, jne. Jos Tycho lähtee alkupisteestä (jossa se on suojassa) hekellä $0$, niin se voi saavuttaa ensimmäisen suojan $8$ sekunnissa, kerryttäen $d$ yksikköä säteilyvahinkoa hetkellä $4$ (mutta ei yhtään hetkellä $8$ koska se on silloin suojassa). Jatkaen pysähtymättä, se saavuttaa tukikohdan hetkellä $18$, kerryttäen $d+d$ yksikköä lisää säteilyvahinkoa (hetkillä $12$ ja $16$). Tällä tavoin se kerryttää $d+d+d=3d$ yksikköä säteilyvahinkoa ja $18$ yksikköä ympäristövahinkoa. Jos taas Tycho odottaa $2.$ suojassa (kohdassa $15$) $1$ sekunnin, niin hetken $16$ pulssi ei aiheuta sille vahinkoa, vaan se pääsee tukikohtaan hetkellä $19$ saaden yhteensä $2d + 19$ yksikköä vahinkoa. Tämä on parempi suurimmalle osalle $d$:n mahdollisista arvoista. Nämä kaksi tilannetta on esitetty tässä:

\includegraphics[width=.8\textwidth ]{img/sample1_2.pdf}

Jos pulsarin jaksonaika on $10$, niin Tycho voi odottaa alkupisteessä $2$ sekuntia ja sitten vain mennä tukikohtaan pysähtymättä mihinkään suojaan. Silloin se ohittaa $1.$ suojan (kohdassa $8$) juuri oikealla hetkellä, kun pulsarin purkaus tapahtuu, ja saapuu tukikohtaan hetkellä $20$, saaden yhteensä $20$ ympäristövahinkoa eikä yhtään säteilyvahinkoa.

\includegraphics[width=.4\textwidth ]{img/sample3.pdf}

Syöte

Syötteen ensimmäinen rivi sisältää neljä kokonaislukua $b$, $p$, $d$, ja $n$ välilyönneillä erotettuina: tukikohdan sijainti $b$, pulsarin purkauksien jaksonaika $p$, pulsarin jokaisen purkauksen aiheuttama lisävahinko $d$, suojapaikkojen määrä $n$. Seuraavat $n$ riviä sisältävät jokainen yhden kokonaisluvun, suojien sijainnit $a_1$, $\ldots $, $a_ n$, missä $0<a_1<\cdots <a_ n< b$.

Tuloste

Tulosta yksi kokonaisluku: pienin määrä vahinkoa, joka Tychon täytyy saada päästäkseen $b$:hen.

Rajoitukset ja pisteytys

Voit olettaa, että $p < b$ ja $n < b$. Kaikille syötteille pätee $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, ja $0\leq n \leq 10^5$.

Ratkaisu testataan testiryhmillä, joista kullakin on oma pistemäärä. Jokainen testiryhmä sisältää joukon testitapauksia. Ryhmän pisteet saa vain, jos ratkaisee kaikki sen testitapaukset. Tehtävän lopullinen pistemäärä on suurin yksittäisen lähetyksen pistemäärä.

Ryhmä

Pisteet

Rajoitukset

$1$

$8$

$p\leq 10^6$ ja Tychon ei tarvitse odottaa sen jälkeen kun se on lähtenyt kohdasta $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$

Ei muita rajoituksia

$^*$ Testiryhmässä $1$ Tycho voi joutua odottamaan kohdassa $0$ ennen kuin se on alkanut liikkua. Esimerkiksi esimerkkisyötteet $2$, $3$, ja $4$ kuuluvat testiryhmään $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