Algoritmizace B4B33ALG
Algoritmizace

Experiment v povodí řeky

Zadání

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.

img1
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říklady

Příklad 1

Vstup
6
5 3
6 3
3 1
4 1
1 0
2 0
Výstup
4

Řešení příkladu 1 je znázorněno na Obrázku 1a).

Příklad 2

Vstup
13
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 8
Výstup
8

Řešení příkladu 2 je znázorněno na Obrázku 1b).

Příklad 3

Vstup
19
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 2
Vý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