Hide

Problem H
Hanoi på badehotellet

Badehotellet Fawlty Towers har købt et nyt stort kunstværk, der skal være hotellets vartegn i den kommende sæson. Den centrale del af kunstværket er tre prægtige tårne, der er prydede med messingskiver af forskellig størrelse. Kunstneren har forklaret, at når skiverne alle står stablet over det midterste tårn, så symboliserer det badehotellets storhed i forhold til de andre badehoteller. Det er meget vigtigt for symbolikken, at samtlige skiver ligger på samme tårn og er anbragt i rækkefølge af faldende diameter, med den største skive forneden.

Lige inden sæsonens store åbningsceremoni vælter tjeneren Manuel kunstværket, så skiverne flyver til alle sider. Han genskaber hastigt kunstværket efter bedste evne og nævner uheldet i en henslængt bemærkning til hotelejeren Basil. Dybt forfærdet styrter Basil hen til kunstværket for at sikre vartegnets symbolik. For at gæsterne ikke skal ane uråd, vil Basil diskret rette op på rodet med ryggen til kunstværket, så han samtidig kan smile beroligende til gæsterne. Det gør oprydningen en anelse mere besværlig, da han bag ryggen kun kan få fat i en enkelt skive ad gangen; nemlig den øverste fra hvert tårn. Denne skive kan han så diskret placere ned over et andet tårn. Det virker dog kun, hvis den flyttede skive kommer til at hvile på en større; ellers er han bange for at ødelægge kunstværket. Man kan altid flytte en skive til et tomt tårn.

Her er en optimal løsning på sytten skridt for situationen i eksempel $5$ forneden.

$\includegraphics[width=.9\textwidth ]{img/example.pdf}$

Hvor mange gange skal Basil flytte en messingskive for at få rettet op på kunstværket?

Indlæsning

Indlæsningen består af tre linjer af mellemrumsadskilte heltal; en linje for hvert tårn. Hver linje starter med et heltal $n_ i\geq 0$, som angiver antallet af yderligere tal på linjen. De resterende $n_ i$ tal på linjen angiver, hvilke skiver der er i tårnet, begyndende fra bunden af tårnet.

Alle skiver er af forskellig størrelse, netop tallene fra $1$ til $n=n_1+n_2+n_3$, hvor $2\leq n \leq 30$.

Udskrift

Et enkelt heltal: hvor mange træk der skal til for at samle alle skiver i sorteret rækkefølge på det midterste tårn, med den mindste skive øverst.

Pointsætning

Der er fire testgrupper:

($23$ point, $n\leq 30$) Manuel har fint samlet alle skiverne på et enkelt tårn, dog ikke nødvendigvis det midterste. Skiverne er desuden sorterede med den mindste skive øverst. Eksempel $1$ og $2$ tilhører denne gruppe.

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

$\includegraphics[width=.3\textwidth ]{img/sample-2.pdf}$
($24$ point, $n\leq 30$, indeholder gruppe $1$.) Skiverne på hvert tårn er sorterede med den mindste skive øverst. Eksempel $3$ tilhører denne gruppe.

$\includegraphics[width=.3\textwidth ]{img/sample-3.pdf}$
($25$ point, $n\leq 10$) Der er højst $10$ skiver; men de kan være vilkårligt rodede. Eksempel $4$ og $5$ tilhører denne gruppe.

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

$\includegraphics[width=.4\textwidth ]{img/sample-5.pdf}$
($28$ point, $n\leq 30$, indeholder grupperne $1$ til $3$.) Ingen yderligere begrænsninger. Eksempel $6$ tilhører denne gruppe.

$\includegraphics[width=.6\textwidth ]{img/sample-6.pdf}$

Sample Input 1	Sample Output 1
3 3 2 1 0 0	7

Sample Input 2	Sample Output 2
0 4 4 3 2 1 0	0

Sample Input 3	Sample Output 3
2 5 1 2 4 2 1 3	29

Sample Input 4	Sample Output 4
4 1 2 3 4 0 0	4

Sample Input 5	Sample Output 5
3 2 5 1 1 3 1 4	17

Sample Input 6	Sample Output 6
8 30 5 28 11 21 22 18 3 10 27 20 12 4 1 10 7 15 14 17 12 13 25 23 16 9 26 24 19 8 2 29 6	223697329

Problem HHanoi på badehotellet

Indlæsning

Udskrift

Pointsætning

Problem H
Hanoi på badehotellet