1. Pekelné teplo

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na

Vedúci sa na leto rozhodli podnikať. Dohodli sa, že si každý založí vlastnú farmu a na nej bude čosi pestovať. Od hrachu a fazule až po kukuricu či repu. Leto sa blíži a oni vedia, že musia všetci poriadne polievať svoju úrodu. Vedúci však majú obmedzený rozpočet a vedia postaviť iba jednu spoločnú studňu na niektorej farme. Práve teraz sa snažia vybrať z niekoľkých kandidátov vhodnú farmu na výstavbu studne. Pri porovnávaní však potrebujú často vedieť odpoveď na otázku: “Ak sa bude studňa nachádzať na farme \(x\), ako dlho potrvá, kým z nej voda dotečie na všetky zvyšné farmy?”

Úloha

Vašou úlohou je vyriešiť problémy súvisiace s touto otázkou. Ako zvyčajne, budete riešiť niekoľko podúloh zoradených podľa nami odhadovanej zložitosti:

1. (3 body) Na priloženej mape fariem zistite čas, ktorý bude vode trvať, pokým sa v prípade sucha dostane z vyznačeného miesta do jednotlivých miest. Pre tok vody platia nasledovné pravidlá:
   1. Ak sa voda nachádza na nejakej farme \(x\), vie sa odtiaľ presúvať na ďalšie farmy pomocou potrubí, ktoré z farmy \(x\) vedú.
   2. Prejsť potrubím trvá vode presne jednu minútu. Pre jednoduchosť totiž predpokladáme, že potrubia sú rovnako dlhé (neriaďte sa tým ako vyzerajú na obrázku).
   3. Presun vody v rámci jednej farmy nezaberá žiaden čas. To znamená, že začať polievať alebo poslať vodu ďalším potrubím vieme v okamihu ako tam voda pritiekla.
   Počas riešenia úlohy nemusíte riešiť množstvo vody. Predpokladajte, že potrubia sú dostatočne veľké a keď na farmu dorazí voda, je jej dosť na to, aby ňou farmári polievali aj ju poslali do všetkých zvyšných potrubí.

Na obrázku vidíte niekoľko fariem a jednu studňu. Čiary, spájajúce niektoré dvojice fariem, znázorňujú existenciu potrubí medzi nimi. Ak teda medzi farmami existuje potrubie, znamená to, že medzi nimi vie priamo tiecť voda. Písmená nad farmami predstavujú iba ich názvy, pomocou ktorých sa môžete na jednotlivé farmy odkazovať. Na obrázku napríklad vidíme, že voda vie za čas 3 dojsť napríklad aj na farmu F cez farmy A a I.

2. (3 body) Popíšte postup, ktorý ste použili na vyriešenie prvej podúlohy. Snažte sa, aby bol tento postup dostatočne všeobecný, nasledujúc váš postup by ste teda vedeli zistiť správnu odpoveď pre ľubovoľne vyzerajúcu mapu akéhokoľvek počtu fariem.

3. (5 bodov) Farmári si uvedomili, že im vaša predchádzajúca pomoc nestačí. Získali totiž lepší odhad o tom, ako dlho tečie voda jednotlivými potrubiami. Predsa len sú rôzne dlhé. Riešenie podúlohy b) teda zrazu nestačí.

   Navrhnite postup, ktorý zistí, ako najrýchlejšie sa vie voda dostať zo studne na všetky farmy. Pritom predpokladajte, že ku každému potrubiu je priradené jedno kladné číslo – čas za ktorý voda prejde z jednej strany na druhú (viď obrázok). Tento postup by mal fungovať pre ľubovoľnú mapu fariem a dĺžky potrubí.

   Za nájdenie správnej odpovede na nižšie uvedenom obrázku môžete získať 1 bod. Čísla pri potrubiach symbolizujú koľko času vode trvá, pokým prejde od jednej farmy k druhej.

Na obrázku znovu vidíme studňu a niekoľko fariem, pospájaných potrubiami. Čísla pri jednotlivých potrubiach určujú ich dĺžku. Teda voda sa vie dostať zo studne na farmy K za 3+3 minút cez farmu G.

4. (4 body) Studňa je aj vďaka vašej pomoci postavená. Na farme \(y\) však zrazu zistili, že potrebujú trochu viac vody. Starší farmári vám poradili, že to viete docieliť tak, že v potrubiach, ktorými voda preteká nastriedačku znížite a zvýšite tlak. To krátkodobo vytvorí podtlak a do cieľovej farmy sa dostane o niečo viac vody.

   Vidíme však, že voda zrazu nemôže ísť potrubiami úplne bez obmedzení, aby tento postup fungoval, musí prejsť cez párne veľa potrubí. Vašou úlohou je nájsť takú postupnosť potrubí, že voda sa na farmu \(y\) dostane čo najrýchlejšie a pritom prejde cez párny počet potrubí.

   Navrhnite postup, ktorý pre zadanú mapu fariem, dĺžky potrubí a farmu \(x\) kde je studňa a farmu \(y\) kde potrebujú viac vody nájde túto najrýchlejšiu postupnosť párneho počtu potrubí.