Hide

Problem E
Alice

/problems/dpop22.alice/file/statement/da/img-0001.png
John Tenniel, She came upon a low curtain she had not noticed before. Illustration fra Lewis Carroll’s Alice’s Adventures in Wonderland, 1865.

Alice er på eventyr, og er nået til et stort hus bestående af en række værelser med døre af forskellig størrelse. Nogle værelser har en lille udgang til den smukke have uden for huset, som Alice gerne vil ud i. Udgangene har forskellige højder, som Alice skal tilpasse sig, før hun kan bruge dem. Værelserne er anbragt i en cirkel; mellem hvert par af naboværelser er der en forbindelsesdør. Hver forbindelsesdør har både en minimal højde (ellers kan Alice ikke nå håndtaget for at åbne døren), og en maksimal højde (ellers er hun for stor til at komme igennem døren).

Alice har adgang til fortryllede småkager, som øger hendes højde med $1$ cm for hver bid, og en flaske med trylledrik, der mindsker hendes højde med $1$ cm for hver slurk. Hun vil gerne spise og drikke af dem færrest muligt antal gange. Hvordan kommer hun ud i haven?

Alice begynder historien som en almindelig syvårig pige på $122$ cm. Hun kan aldrig blive mindre end $1$ cm. Alice begynder i værelse $1$.

Eksempel

Eksempel $1$ ser sådan ud:

\includegraphics[width=.4\textwidth ]{img/sample-handdrawn.png}

Mere skematisk og med udtrykkelige dørbegrænsninger:

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

For eksempel kan forbindelsesdøren mellem værelse $1$ og $2$ kun bruges, når Alice er mellem $75$ og $150$ cm høj. Alice kan forlade værelse $1$ gennem den $96$ cm høje udgang, hvis hun drikker $122-96 =26$ slurke. En bedre løsning er at gå til værelse $2$, som ikke har nogen brugbar udgang, tage tre bidder af småkagen for at komme til værelse $3$, og derefter drikke $125-110=15$ slurke for blive lille nok til at komme ud.

Læg mærke til, at den ellers attraktive udgang i værelse $4$ er vanskelig at komme hen til. Hun skal spise eller drikke en masse for at komme derhen, uanset fra hvilken retning.

Indlæsning

På første linje står antallet $N$ af værelser. Du kan antage $2\leq N\leq 10^6$.

De næste $N$ linjer beskriver værelserne i rækkefølge med uret, kald dem $1$, $2$, $\ldots $, $N$. Hver linje består af $3$ positive heltal $a$, $b$ og $c$. Her angiver $a$ højden på værelsets udgang, mens $b$ og $c$ angiver henholdsvis den lavest nødvendige og størst mulige højde, som Alice skal have for at kunne komme fra $i$ til $i+1$ eller fra $N$ til $1$.

Der gælder $0\leq a \leq 1000$, $0\leq b\leq c\leq 1000$ og $c>0$. Når $a=0$ har værelset ingen brugbar udgang til haven.

Testgrupper

Der er fire testgrupper.

  1. I testgruppe $1$ gælder $b=0$, dvs. at alle forbindelsesdøre kan bruges, uanset hvor lille Alice er.

  2. I testgruppe $2$ er det garanteret, at Alice kun behøver at gå med uret, dvs. fra værelse $i$ til $i+1$.

  3. I testgruppe $3$ er $N\leq 1000$.

  4. Testgruppe $4$ har ingen yderligere begrænsninger og indeholder de tre andre grupper.

Udskrift

Et enkelt heltal: det mindste antal bidder og slurke, som Alice skal indtage for at nå ud i haven.

Sample Input 1 Sample Output 1
4
96 74 150
0 125 180
110 210 400
122 0 30
18
Sample Input 2 Sample Output 2
3
1 150 300
102 150 300
101 150 300
76
Sample Input 3 Sample Output 3
3
20 100 150
151 100 200
20 100 200
0
Sample Input 4 Sample Output 4
3
99 0 98
100 0 100
99 0 100
22
CPU Time limit 3 seconds
Memory limit 1024 MB
Authors
Alice Ryhl and Thore Husfeldt
Source D-Pop 2022
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in