5. Kartografia riek
Zadanie
Táto úloha je teoretická. Ako svoje riešenie odovzdaj pdf súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil(a) chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.
Ak máš hocijaké otázky k tejto úlohe, napíš Štepimu na [email protected] alebo Soni na [email protected] .
Konečne sa Štepi, Hanka a Miška naozaj vydali domov. Naložili si všetky veci do loďky a vytiahli mapy, ktoré im daroval Strížožírts. Tie mapy však boli iné ako poznali! Bola to iba zmes kratších a dlhších čiar, z ktorých vôbec nebolo jasné ako vyzerá rieka, po ktorej sa majú plaviť. Zmätene sa na seba pozreli a s prosbou o pomoc sa obrátili na Teba.
Amazonka je rozvetvený riečny systém, pričom rieka sa môže v nejakom mieste rozdeľovať na dve alebo sa dve môžu spojiť do jednej. Roky si domorodci kreslia mapy riek a to takým spôsobom, že vždy keď idú po nejakej trase, tak si zaznamenajú aké prítoky po ceste vidia. Ak loď odbočuje na rozdvojke doľava, potom posádka vidí rameno na pravej strane, čo zakreslia do mapy takto:
Ak sa spájajú dva prítoky a loď prichádza tým z prava, potom druhý prítok vidia po svojej ľavej ruke, čo zakreslia takto:
![](/uploads/contest/prask/rounds/r10z2/5/rameno.jpg" style="max-width:50%; margin)
a. (10 bodov) Ako by vyzerala mapa, ktorú zakreslí posádka, ak prechádza po vyznačenej trase v riečnej sieti?
Na cestu späť dostali moreplavci pod vedením Štepiho pre istotu týchto máp viacej. No na to, aby sa bezpečne dostal domov, by potreboval vedieť ako vyzerá celý riečny systém.
b. (20 bodov) Podľa nasledujúcich 3 máp zisti ako vyzerá celý riečny systém, ktorý popisujú tieto mapy. Všetky mapy začínajú v jednom bode a aj končia v jednom bode. V mapách je dokopy zakreslená celá sieť, nemôže sa stať, že by tam bola ešte nejaká vetva, ktorá nie je na žiadnej mape.
Moreplavci však došli na koniec mapy. Preto vystúpili v najbližšej dedine a kúpili si nové mapy. Najbližší úsek trasy čo ich čakal bol však zložitejší.
c. (20 bodov) Zisti ako vyzeral ďalší úsek riečneho systému, ak Štepi dostal tieto 4 mapy:
Keď už mal Štepi zakreslený celý riečny systém, zistil, že ho vie prejsť viacerými spôsobmi. Teraz by ho zaujímalo koľko rôznych ciest existuje.
d. (20 bodov) Zisti koľkými spôsobmi vie Štepi preplávať cez tento riečny systém, teda koľko je rôznych ciest, ktorými sa dá preplaviť z ľavého konca na pravý.
e. (30 bodov) Vymysli nejaký postup, ktorým sa dá vyriešiť úloha ako b) aj c) pre ľubovoľné zadané mapy. Stále môžeš predpokladať, že každý úsek rieky sa nachádza aspoň na jednej mape.
a. 
b. 
c. 
d. Miesta, kde sa rieka rozvetvuje alebo spája, budeme nazývať uzly. Pre každý uzol spočítame, koľkými spôsobmi sa do neho dá dostať. V uzle úplne naľavo začíname, takže máme len $1$ možnosť (proste tam sme). Môžeme si predstaviť, že uzly pospájame šípkami tak, ako medzi nimi vedú rieky. Teraz si predstavme, že chceme spočítať počet možností pre nejaký uzol $u$. Doňho sa vieme dostať po každej šípke, ktorá vedie do $u$. Ak teda chceme vedieť, koľkými spôsobmi sa vieme dostať do $u$, tak sčítame pre každú šípku do $u$ počet spôsobov pre uzol, z ktorého tá šípka vedie.
Takto postupne ideme po šípkach a vyplníme všetky uzly, čím dostaneme, že na koniec sa vieme dostať $9$ spôsobmi. Keďže $9$ nie je až tak veľa, tak sa dali aj všetky tieto spôsoby vypísať, ale tento postup bybol rýchly aj na veľkých riekach, kde by ciest bolo veľmi veľa.
e. Kým sa rieky len rozvetvujú a nespájajú, tak si vieme jednoznačne nakresliť, ako bude vyzerať začiatok rieky. Problém je, že keď sa rieky spájajú, tak na nejakej mape vidíme, že sa ku mne má pripojiť rieka, ale nevieme, ktorá rieka to má byť. Na obrázku je, ako by to vyzeralo pre rieku v úlohe c.
Keďže sme si ale nakreslili všetky začiatky, ktoré sme vedeli, tak teraz v každej rieke musí nasledovať nejaké spájanie. Musíme teda spojiť vľavo nejaký prípoj sprava a vpravo nejaký prípoj zľava. Nemôže sa stať, že by sa rieka vpravo pripojila k nejakej rieke zľava, lebo to by musela rieka tiecť do kruhu.
Nemôžeme ale spojiť rieky, ktoré nesusedia, lebo tým by sme uzavreli všetky rieky medzi nimi vnútri, a už by sa nemali k čomu pripojiť.
Na druhej strane, ak máme nejaké rieky, ktoré susedia a dajú sa spojiť, tak už rovno musia byť spojené. Ak by sa totiž povedzme ľavá rieka spájala s nejakou inou pravou neskôr, potom sused tej pravej bol tiež zavretý vnútri a nedal by sa spojiť.
Postup teda bude vyzerať tak, že kým sa rieky rozvetvujú, tak si tam jednoznačne kreslíme obrázok, potom keď už všade nasleduje spájanie, tak pospájame susedov, a toto opakujeme až kým nemáme celú rieku (alebo, ak sa niekedy nedá pokračovať, tak vieme, že tak rieka nemôže vyzerať a v mapách je chyba).
