Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (2. soutěžní den) 49. ročníku

P-III-4 Pramen

 Program: PRAMEN.PAS / PRAMEN.CPP
Vstup: PRAMEN.IN
Výstup: PRAMEN.OUT

V jistém lázeňském městečku mají N minerálních pramenů očíslovaných 1,2,...,N. Prameny jsou navzájem pospojovány pěšinami, přičemž pěšina vede mezi každou dvojicí pramenů. Turisté obvykle chtějí ochutnat vodu z každého pramenu, ale protože pěšiny nejsou nijak označené, občas se stane, že některého zbloudilého turistu najdou až ve vedlejší dolině. Správce lázní se proto rozhodl umístit ke každému pramenu právě jednu směrovku ukazující na další pramen, a to tak, že turista začínající svou procházku u libovolného pramenu a pokračující ve své cestě podle směrovek obejde postupně všechny prameny.

Správce tedy nechal vyrobit N směrovek s čísly pramenů 1,...,N. Dělníci ale příliš nepřemýšleli a rozmístili směrovky k pramenům úplně náhodně. Tak se stalo, že u každého pramene sice byla umístěna právě jedna směrovka ukazující k nějakému prameni, ale mohlo se stát, že pokud vyšel turista od některého pramene, tak se k některým jiným pramenům vůbec nedostal. Mohlo se dokonce stát, že směrovka u některého pramene ukazovala nazpět na ten samý pramen, u kterého byla umístěna.

Správce ví, že na dělníky se může spolehnout jen v této jednoduché operaci: vzájemně zaměnit směrovky u dvou pevně daných pramenů p a q, tzn. jestliže směrovka u pramene p ukazovala na pramen i a směrovka u pramene q ukazovala na pramen j, tak po této výměně bude u pramene p směrovka ukazovat na pramen j a u pramene q bude směrovka ukazovat na pramen i.

Napište program pro správce lázní, který zjistí, jaké výměny směrovek mají dělníci provést, aby bylo možné podle směrovek obejít všechny prameny a aby přitom počet provedených výměn byl nejmenší možný.

Vstupní soubor

Vstupní soubor PRAMEN.IN obsahuje na prvním řádku počet pramenů N (1<=N<=30000). Následuje N čísel (oddělených mezerami nebo konci řádků), přičemž i-tým z nich je číslo pramene, na který ukazuje směrovka umístěná u i-tého pramenu.

Výstupní soubor

První řádek výstupního souboru PRAMEN.OUT obsahuje minimální počet výměn M, které je třeba provést. Následuje M řádků popisujících jednotlivé výměny: (i+1)-tý řádek výstupního souboru (1<=i<=N) obsahuje dvě čísla p, q oddělená jednou mezerou, označující dvojici pramenů, u nichž je třeba vyměnit směrovky. Výměny se provádějí v uvedeném pořadí.

Příklad

PRAMEN.IN 7 5 1 4 6 2 3 7 PRAMEN.OUT 2 1 3 7 1 Poznámka: Uvedený výstupní soubor je jedním z možných správných výstupních souborů.

P-III-5 Kina

Program: KINA.PAS / KINA.CPP
Vstup: KINA.IN
Výstup: KINA.OUT

V jisté zemi právě začal Mezinárodní Filmový Festival Umělecké Kinematografie (MFF UK). V zemi je n (1<=n<=50) měst označených čísly 1,2,...,n. V každém městě je jedno kino. O každém kině je známo, který film z nabídky filmů MFF UK očíslovaných 1,2,...,t (1<=t<=n) v něm promítají. Konkrétně, v kině ve městě číslo i promítají každý večer stejný film číslo fi. Města jsou navzájem pospojována m obousměrnými cestami. Pro každou cestu c (1<=c<=m) známe čísla měst zc a kc (zc<>kc), která tato cesta spojuje, a také známe její délku lc (0<=lc<=1000). Mezi každou dvojicí měst vede nejvýše jedna cesta.

Předpokládejme, že máte rozpis k večerů (0<=k<=1000), přičemž pro každý večer i (1<=i<=k) je stanoveno číslo filmu pi, který byste chtěli v ten večer vidět. Některé filmy se v rozpisu mohou vyskytnout i vícekrát. Abyste mohli večer sledovat naplánovaný film, musíte se během dne dopravit do některého města (nezáleží na tom do kterého), v němž tento film uvádějí. Protože neradi cestujete, chtěli byste, aby celková vámi procestovaná vzdálenost byla co nejmenší. První den ráno se nacházíte ve městě číslo 1. Při přejíždění z města do města je možné projíždět přes libovolná jiná města. Z každého města se lze dostat do každého a přeprava se stihne vždy za jeden den. Nezáleží na tom, ve kterém městě zůstanete po shlédnutí posledního filmu.

Napište program, který pro každé město přečte číslo promítaného filmu, dále načte popis jednotlivých cest a rozpis filmů, které chcete v jednotlivých dnech vidět, a vypíše, ve kterém městě máte jít který večer do kina, aby vámi procestovaná dráha byla minimální. Dále vypíše délku této minimální trasy.

Vstupní soubor

Vstupní soubor KINA.IN obsahuje na prvním řádku tři čísla n,m,k. Druhý řádek obsahuje n čísel f1,f2,...,fn. Následuje m řádků popisujících cesty, každý z nich obsahuje trojici čísel zc,kc,lc. Poslední řádek obsahuje k čísel p1,p2,...,pk. Každá dvojice po sobě následujících čísel v řádku je oddělena jednou mezerou. Můžete předpokládat, že každý film pi (1<=i<=k), který chcete vidět, se promítá alespoň v jednom městě.

Výstupní soubor

Výstupní soubor KINA.OUT obsahuje na prvním řádku délku celkově procestované dráhy mezi městy. Druhý řádek popisuje jednu optimální trasu. Obsahuje k čísel (každá dvě po sobě jdoucí čísla jsou oddělena mezerou), i-té číslo v pořadí označuje město, v němž byste podle zvolené trasy měli vidět film pi.

Poznámka: Jestliže výstupní soubor obsahuje správnou minimální délku, ale buď neobsahuje žádný popis optimální trasy, nebo obsahuje popis trasy, který je chybný, bude řešení hodnoceno jako částečně správné a získá pro daný vstup poloviční počet bodů.

Příklad

KINA.IN 6 7 7 2 1 2 3 1 4 1 2 13 2 3 7 3 4 5 4 1 4 1 5 8 5 3 10 2 6 0 1 2 1 4 3 2 1 KINA.OUT 49 5 3 2 6 4 3 2