Experiment v povodí řeky
Skupina ekologů studuje povodí velké řeky a připravuje experiment. Mají k dispozici tři speciální tekutiny. Pro každou z nich potřebují vybrat pramen, do kterého
tekutinu nalijí, aby následně mohli po dobu 24 hodin měřit koncentraci tekutin v různých částech povodí, takzvaných sekcích. Sekce je úsek řeky mezi dvěma kontrolními
body. Kontrolním bodem je každý pramen, každý soutok dvou řek a také místo, kde se hlavní řeka vlévá do moře. Kromě toho jsou
definovány další kontrolní body na významných místech podél některých řek. Vzhledem k tomu, že v povodí
nedochází k soutoku tří a více řek, mají kontrolní body a sekce strukturu binárního stromu, jak je vidět na Obrázku 1.
Jak ilustruje obrázek 1a), v místě, kde se hlavní řeka vlévá do moře, může docházet k soutoku s jinou řekou, která je také součástí povodí hlavní řeky.
Výběr pramenů komplikuje ekologům fakt, že měření v dané sekci je validní pouze tehdy, když
během celého experimentu nedojde v sekci k promíchání dvou nebo tří tekutin.
Ekologové přirozeně chtějí uskutečnit co nejvíce validních měření, z toho důvodu se jako dobrá myšlenka jeví nalít tekutiny do takových pramenů, kdy je
maximalizován počet sekcí, kterými protéká právě jedna tekutina.
Obrázek 1. Příklady optimálních výběrů pramenů. Kontrolní body jsou zobrazeny jako uzly. Sekce jsou zobrazeny jako hrany, jejichž orientace sleduje tok dané řeky. Místo, kde se hlavní řeka vlévá do moře, je označeno kontrolním bodem 0. Červená, zelená a modrá barva odpovídají jednotlivým tekutinám. Sekce, kterými během experimentu protéká právě jedna z tekutin, jsou zvýrazněny příslušnou barvou. Černé hrany reprezentují sekce, kterými neprotéká žádná z tekutin, šedé hrany reprezentují sekce, kterými protékají dvě nebo tři tekutiny. a) Optimálního řešení je dosaženo, když jsou tekutiny nality do pramenů 2, 4 a 5. b) Optimálního řešení je dosaženo, když jsou tekutiny nality do pramenů 2, 3 a 13. Uzly 4, 5, 8 a 10 jsou příklady kontrolních bodů definovaných na významných místech podél řek. |
Úloha
Je dán seznam dvojic kontrolních bodů tvořících sekce. Vaším úkolem je určit maximální možný počet sekcí, kterými během experimentu protéká právě jedna tekutina, když
jsou všechny tři tekutiny nality do pramenů.
Vstup
První řádek obsahuje celé nezáporné číslo N udávající počet sekcí. Následuje N řádků, kde každý reprezentuje jednu sekci pomocí čísel C a D oddělených mezerou. Tato čísla jsou identifikátory kontrolních bodů vymezujících danou sekci. Kontrolní bod C je ten blíže k pramenu řeky. Kontrolní body jsou indexovány od 0 do N, přičemž 0 je vždy identifikátor kontrolního bodu umístěného v ústí hlavní řeky do moře. Sekce jsou na vstupu reprezentovány v náhodném pořadí. Hodnota N nepřesáhne 1,5 × 106. Je garantována existence alespoň třech pramenů.
Výstup
Výstupem je jeden řádek sestávající z jednoho celého nezáporného čísla, jež je rovno maximálnímu počtu sekcí, kterými protéká právě jedna tekutina při nalití všech tří tekutin do pramenů.
Příklad 1
Vstup6 5 3 6 3 3 1 4 1 1 0 2 0Výstup
4Řešení příkladu 1 je znázorněno na Obrázku 1a).
Příklad 2
Vstup13 12 0 11 12 9 12 6 11 7 11 8 9 3 10 10 9 1 4 4 7 2 5 5 7 13 8Výstup
8Řešení příkladu 2 je znázorněno na Obrázku 1b).
Příklad 3
Vstup19 6 12 10 5 15 0 12 15 3 7 1 13 18 6 17 8 13 11 9 12 7 6 5 15 4 1 2 10 8 11 11 10 19 13 14 16 16 2Výstup
11
Veřejná data
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při
každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu
pro každý soubor veřejných dat.
Veřejná data