Problem E
Alice

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:

Mere skematisk og med udtrykkelige dørbegrænsninger:

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.

4
96 74 150
0 125 180
110 210 400
122 0 30

18

3
1 150 300
102 150 300
101 150 300

76

3
20 100 150
151 100 200
20 100 200

0

3
99 0 98
100 0 100
99 0 100

22