• KSP
• • Home
  • Novinky
  • Pravidlá
  • FAQ
  • Kuchárka
  • Liaheň
• Séria
• • Zadania a výsledky
  • Odovzdaj riešenie
  • Ideálne riešenie
  • Archív zadaní
  • Zbierka
• Akcie
• • Sústredenia
  • Proboje
  • Akadémia a klub
  • LTT
• Ostatné
• • Podporte nás
    2% z daní
  • Organizátori
  • Sponzori
  • Kontakt
• Iné semináre
• • Trojsten
  • KMS
  • FKS
  • Iné súťaže

Príklady 2. kola letnej časti 25. ročníka KSP

Milé naše riešiteľky, milí naši riešitelia,

práve čítate úvodník zadaní poslednej série KSP v tomto školskom roku. Vaši obľúbení vedúci ich vytvárali s tou najúprimnejšou snahou a preto sa Vám iste budú páčiť. Ostatne, ak by sa Vám nepáčili, bolo by to od Vás dosť trúfalé, nemyslíte?

Treba pamätať na to, že pri riešení KSP sa veľa naučíte. A kto veľa vie, je pre ľudstvo hodnotnejším človekom. A kto veľa nevie, nevie ani to, že termín, doktedy treba poslať riešenia je 15. mája. A samozrejme nevie ani veľa iných zaujímavých informácii a preto je riešenie nášho seminára jednoznačne odporúčané.

A ešte pripomíname, že v sobotu 24. mája sa koná ďalší ročník prestížnej online programátorskej súťaže IPSC. Všetko potrebné sa dozviete na http://ipsc.ksp.sk/. Príďte si zmerať sily s tímami z celého sveta!

Kofola obsahuje málo vitamínov. Treba jej piť veľa, ak chceme byť zdraví.
KSPáci

1. Zľav, lebo to jeho topánka kúpi!
2. Zberač Ivan
3. Zbúrajme si mrakodrapy!
4. Ostrov veľkého slizniaka
5. Okšoram a náhrdelník
6. O Krajine Strašných Pokladov.
7. Obrovská spotreba veteránov
8. Ospalý Lukáš
9. Tuniakové a iné bagety
10. Obchodný cestujúci má hlad

---

1. Zľav, lebo to jeho topánka kúpi!

15 bodov, kategória Z

A je to tu! Hermimu sa rozpadli tenisky. Smutne pozeral na svoje ponožky trčiace po stranách z jeho obľúbených tenisiek. (Možno si na ne spomínate z LTT, poprípade sústredenia v Terchovej...) To by sa ešte veľa nedialo, Hermi je predsa strašne drsný chlap a niečo také ako sem-tam vyčuhujúcu ponožku predsa znesie. Keby sa to tak ale dalo povedať aj o zvyšku rodiny! Preto sa po krátkej spŕške vyhrážok musel vydať po nové. Neverili by ste tomu, ale v Lamači nemajú dobré obuvníctvo. (To kvalitatívne nič nehovorí, nebolo predsa ani v raji...) Došiel teda pozrieť do Megasportu akéže tenisky mu môžu ponúknuť. Mali tam také tie otočné dvere, čo poznáme z filmov. A nalejme si čistej kofoly, hneď ako vo dverách zbadal cenovky, tak sa milé deti pretočil! Ale videl ich! Boli tam! Goratex, vibramová podrážka, farba čo mu ide k očiam. Vedel, že ich musí mať. Pozrel sa do peňaženky a zistil, že to nebude také ľahké. Našťastie ho milá mladá pekná tetuška, myslím že ryšavá bola, poinformovala o skvelom Megasporťáckom systéme zliav. Na každý pár tenisiek sa viaže určitá zľava, ktorú môžete pri budúcom nákupe použiť. Dokonca ak si kúpite viac párov, zľavy sa sčítajú. Ba je to ešte drsnejšie, ak vaša zľava prekročí 100 ozvalo neodolateľné vábenie mamonu. Čo si budeme nahovárať niečo o charaktere, tak ako každý íný, chce zruinovať obchodníkov a nabaliť sa z toho. Preto chce nakúpiť tak, aby zaplatil čo najmenej. Ešte jednu vec sme ale nespomenuli... Hermi je matfyzák a o matfyzákoch sa dobre vie, že nevedia moc dobre rátať (A nevymýšľam si, večer u ohníka vám môžem toľko historiek povyprávať!) a tu nastupujete vy! Napíšte mu, chudáčikovi, program, ktorý mu pomôže zmanažovať nákup. On síce vie skvele programovať, ale je trochu lenivý... (ale pssst!)

Úloha

Na vstupe je zadané číslo – cena tenisiek, ktoré si Hermi chce kúpiť, ďalej nasleduje číslo – počet ďalších tenisiek. V nasledujúcich riadkoch sú dvojice čísel a , kde je cena -teho páru tenisiek a je zľava v percentách, ktorú získame pri nasledujúcom nákupe. Vašou úlohou je vypísať, ktoré tenisky si má teraz Hermi kúpiť tak, aby keď sa na ďalší deň vráti a kúpi si iba svoje vyhliadnuté tenisky, zaplatil celkovo, tj. v oboch dňoch, čo najmenej (resp. zarobil čo najviac). Môžete predpokladať, že má neobmedzené zdroje peňazí a že ceny sú celé čísla.

---

2. Zberač Ivan

15 bodov, kategória Z

Ivan podniká so železom. Možno ste ho videli aj vy, ako si tlačil svoj vozíček po Bratislave. Momentálne pracuje inkognito na tratiach ŽSR, kde vytrháva koľajnice a odváža ich do zberných surovín. Ale tak ako do všetkého, aj do nižšej podnikateľskej vrstvy sa rád naváža protimonopolný úrad. A tak začal chudák milý Ivan pozorovať, že sa strácajú aj koľajnice, ktoré nevzal on. A uvedomil si, že má problém. Železnice totiž tieto jeho "služby" budú tolerovať iba do tej doby, kým sa bude dať po koľajniciach dostať medzi ľubovoľnými dvoma stanicami. Akonáhle železnice zistia, že niekto rozoberá trať, ktorá je jedinou spojnicou medzi stanicami, ihneď poštvú na chudáka INTERPOL.

Ivan vždy za jeden deň kompletne rozoberie trať medzi dvoma susednými stanicami (Je to silný chlap, keď nosí koľajnice a prepapá toho dosť veľa.) . A potom vždy jeden deň odpočíva (a prípadne cestuje na miesto, kde ide rozoberať ďalej). Teraz zistil, že jeho konkurencia si počína presne rovnako, len v iné dni – keď Ivan rozoberá trať, konkurencia odpočíva a naopak. A určite si tie mrchy vyberajú úseky trate tak, aby tým nešťastníkom, ktorý nakoniec trať

rozpojí, bol chudák Ivan.

Dnes by mal Ivan ísť rozobrať ďalší úsek trate a zaujímalo by ho, či vôbec ešte má šancu s konkurenciou vybabrať. Bohužiaľ, aj keď je schopný programátor, nemá počítač (Odniesol ho pred časom do zberných surovín.) a preto sa obrátil na vás s prosbou o pomoc. Napíšte program, ktorý zistí, kto z nich nebude mať na výber a rozoberie trať tak, že sa už nebude dať cestovať medzi ľubovoľnými dvoma stanicami. Ivan aj jeho konkurencia si samozrejme budú vyberať úseky trate na rozobranie tak, aby pokiaľ možno spôsobili, že trať rozpojí ten druhý.

Úloha

Na vstupe sú celé čísla a udávajúce počet staníc a počet tratí medzi nimi. Nasleduje dvojíc čísel , ktoré hovoria, že medzi stanicami a existuje trať. (Každá dvojica staníc je spojená najviac jednou priamou traťou a každý úsek trate spája dve rôzne stanice.)

Môžete predpokladať, že medzi každými dvoma stanicami existuje nejaká cesta (Odborne povedané, graf predstavujúci železničnú sieť je súvislý.) (môže viesť aj cez iné stanice). Ivan a jeho konkurent na striedačku rozoberú vždy jednu trať za deň. Prvý je na rade Ivan.

Môžete predpokladať, že úseky odoberajú optimálne. To znamená, že ak má jeden z nich možnosť odoberať úseky tak, aby časom určite vyhral, urobí to. Napíšte program, ktorý zistí, ktorý z týchto dvoch podnikateľov prehrá (t.j. odoberie trať tak, že sa nebude dať cestovať medzi niektorými dvoma stanicami).

Nezabudnite nám okrem svojho programu poslať aj poriadne zdôvodnenie, že naozaj vždy dá správnu odpoveď!

---

3. Zbúrajme si mrakodrapy!

15 bodov, kategória Z

Naši starí známi nerozluční priatelia Santo a Banto si povedali, že sedenie doma na hovníku a pravidelné pozeranie komerčných relácii ich nebaví, a preto sa rozhodli, že začnú podnikať. A tak začali búrať mrakodrapy na zákazku. Obidvaja sú veľmi šikovní a tak rýchlo došli na spôsob, ako zbúrať z mrakodrapu iba vrchných poschodí. (Akékoľvek pokusy zbúrať spodných poschodí presiahli očakávania a budova spadla celá) Skúsenosťami však došli na to, že je z bezpečnostného hľadiska najlepšie búrať vrch najvyššej budovy. Táto práca ich neobyčajne baví a napĺňa, čo vyústilo do toho, že v deštrukcii sa striktne striedajú. Ale to, čo ich baví najviac, je zdemolovanie poslednej budovy.

Santo a Banto dostali novú zákazku zdemolovať mrakodrapov. Po hodinovej hádke sa dohodli, že Santo začína demolovať ako prvý. Ako má búrať tak, aby na konci zbúral posledný kúsok posledného mrakodrapu?

Úloha

Na vstupe bude celých nezáporných čísel . Číslo udáva počet poschodí -teho mrakodrapu. Santo a Banto hrajú hru. V každom ťahu si hráč vyberie mrakodrap s maximálnym počtom poschodí (ak je takých viac, tak si vyberie ľubovoľný z nich) a zbúra z neho ľubovoľný počet poschodí. Hráči sa striedajú, začína Santo. Vyhráva ten, ktorý zbúra posledný kúsok posledného mrakodrapu.

Vašou úlohou je nájsť víťaznú stratégiu pre túto hru (víťazná stratégia je taký postup, ktorého keď sa držíme, tak vyhráme, bez ohľadu na to, ako hrá súper) a napísať program, ktorý vypíše prvý ťah držiaci sa víťaznej stratégie. Ak pre dané rozostavenie budov neexistuje víťazná stratégia, váš program má o tom podať správu.

Bodovanie: Ak sa vám nepodarí vyriešiť úlohu pre mrakodrapov, nevadí. Ak ju vyriešite pre , dostanete bodov, za mrakodrapy dostanete bodov a za mrakodrapy dostanete bodov.

---

4. Ostrov veľkého slizniaka

15 bodov, kategória Z a O

Slimačia rodinka sa vybrala na prvého apríla na výlet na Ostrov veľkého slizniaka. Tam sa konal cirkus. To bolo pre slimáky niečo výnimočné. Najviac sa tešili na veľký kolotoč. Vôbec im nevadilo, že na ňom niektoré sedačky chýbali – pekne sa to točilo (v protismere točenia ulity) a hralo pestrými farbami. Malé slimáčatá rýchlo bežali obsadiť si miesto na kolotoči, aby sa im ešte ušlo.

Dva slimáky v puberte, Maty a Maják, si doniesli soľničky, aby ich po sebe na kolotoči hádzali. Veľkému slizniakovi Mišovi sa to nepáčilo (Skúšali ste niekedy posoliť slimáka? A čo tak Majáka?) , a preto ich chcel usadiť čo najďalej od seba.

Úloha

Na vstupe máte v prvom riadku počet sedačiek . V každom z nasledujúcich riadkov je pozícia sedačky daná dvoma reálnymi číslami, ktoré predstavujú -ovú a -ovú súradnicu. Môžete predpokladať, že sedačky sú naozaj na kružnici a sú v poradí, v akom sú umiestnené na kolotoči. Vašou úlohou je nájsť dve sedačky pre Matyho a Majáka, ktoré sú spomedzi všetkých dvojíc sedačiek najviac vzdialené od seba.

---

5. Okšoram a náhrdelník

15 bodov, kategória Z a O

Možno si ešte pamätáte na žabiaka Okšorama. Nedávno aj s vašou pomocou zachránil prsteň svojho kamaráta Akinoma. Po tomto jeho hrdinskom čine zavládla na rybníčku pohoda a harmónia. Jarné slnečné lúče zohrievali kvitnúce lekná a spokojné žabky sa venovali chytaniu mušiek, naháňaniu sa v plytkých vodách rybníčka alebo hraniu sa šachu. Jedného dňa sa však okolím opäť rozľahol zúfalý plač Akinoma. Tentokrát žabiačik stratil svoj náhrdelník z malých kvietkov, ktorý dostal od rodičov a ktorý mal veľmi rád. Všetky žabky a aj iné zvieratká, túžiace Akinomovi pomôcť, začali hľadať všade možne aj nemožne. Ale náhrdelník ako by sa pod zem prepadol – nie a nie ho nájsť. Okšoram sa teda rozhodol, že sa pokúsi Akinomovi vytvoriť nový a potešiť ho aspoň tak.

Náhrdelník tvorili kvietky rôznych rastlín a farieb. Okšoram sa vybral na prechádzku (Alebo preskáčku? Pozor, nepliesť si so spojením na preskačku, tam sa píše krátke á.) krásne rozkvitnutým okolím rybníčka a pozbieral zopár kvietkov. Tie by rád všetky použil. Avšak s ich zapájaním do kruhu to nebude také jednoduché, pretože nie každá kvetinka ide zviazať s každou – vyzeralo by to nepekne a niekedy to dokonca vďaka nevhodným vlastnostiam stonky ani nejde. Okšoram si ako správny matematik úlohu formalizoval a každému kvietku priradil dve čísla – typy pripojení, akými kvetinku možno zviazať z oboch strán. Kvetinky možno spolu nejakou stranou zviazať iba ak majú na príslušných stranách rovnaké číslo – typ spojenia. Teraz sa už podujal na zväzovanie kvietkov do náhrdelníka. Po istom čase si však uvedomil, že to nie je vôbec také jednoduché a dokonca prestal veriť, že sa to dá. Zdá sa, že bude musieť ísť natrhať nejaké ďalšie kvietky, aby bol schopný náhrdelník dokončiť. Keďže, ako vieme, nie je veľmi zbehlý v riešení algoritmických úloh, pomôžte mu a rozhodnite, aký najmenší počet nových kvietkov potrebuje!

Úloha

Na vstupe máte počet kvietkov a počet typov pripojení . Nasleduje riadkov s dvojicou čísel . Jeden riadok popisuje jeden kvietok a čísla znamenajú typy pripojenia -teho kvietku. Kvietok sa zapája z oboch strán, pričom sa dá samozrejme otočiť – zmena poradia typov spojení daného kvietku situáciu neovplyvňuje (Odbornejšími slovami: hrany nie sú orientované.) . Vašou úlohou je zistiť najmenší počet nových kvietkov tak, aby sa dali všetky pospájať do náhrdelníka. To znamená pospájať všetky kvietky tak, aby pre každý kvietok platilo, že je jedným svojím spojením zviazaný s predchádzajúcim kvietkom s rovnakým typom spojenia a druhým svojím spojením zviazaný s nasledujúcim kvietkom. Kvietky musia tvoriť kruh, takže posledný musí byť spojený s prvým.

---

6. O Krajine Strašných Pokladov.

15 bodov, kategória O

Kapitánovi Jankovi Vrabcovi veštica vyveštila, že sa pri svojich plavbách dostane úplne všade. O to ho viac potešilo, keď našiel mapu Krajiny Strašných Pokladov (Ale ešte nevie, kde sa tá krajina nachádza.) , kde je obrovská kopa nevyzdvihnutých pokladov. Skvelá príležitosť. Nie?

Problémom je, že krajina sa skladá výhradne zo vzdušných zámkov, pričom niektoré zámky sú pospájané mostami tak, že medzi každými dvoma zámkami existuje práve jedna cesta po mostoch (Teda každý most je most :-)) . Zároveň existuje iba jeden zámok, do ktorého sa dá dostať z pevniny. To robí trošku problémy, lebo na každom moste sa platí konkrétne mýto a preto si musí zobrať zo sebou nejaké bubáky (nemôže mať predsa počas svojej cesty po Krajine Strašných Pokladov záporný počet peňazí v peňaženke).

Úloha

V prvom riadku vstupu sa nachádza číslo , ktoré označuje počet miest, mestá sú očíslované od po . Druhý riadok vstupu obsahuje kladných čísiel, -te číslo udáva veľkosť pokladu v -tom meste. Potom nasleduje riadkov, ktoré popisujú mosty medzi mestami. Most je popísaný troma číslami , kde sú čísla miest ktoré -ty most spája a je veľkosť mýta na danom moste. Náš hrdina začína v meste , chce prejsť cez všetky mestá a skončiť opäť v meste tak, aby počas cesty mal vždy čím zaplatiť mýto (zároveň nechce cez žiadny most chodiť viac ako 2-krát). Koľko najmenej peňazí si musí zo sebou na začiatku zobrať? Môžete predpokladať, že medzi každými dvoma mestami existuje práve jedna cesta.

---

7. Obrovská spotreba veteránov

15 bodov, kategória O

Andrej je veľkým fanúšikom starých áut. Doma v garáži má celú zbierku historických áut od motorového "koča" na uhlie až po športový kabriolet americkej výroby z prelomu 60-tych a 70-tych rokov. Ako každý správny zberateľ, Andrej svoje autá rád ukazuje a porovnáva s ostatnými. Naposledy sa dozvedel o veľkej veterán revue, ktorá sa bude konať na neďalekom Záhori, na ktorej by chcel predviesť svoj najnovší prírastok: auto bulharských generálov z prvej svetovej vojny. Bohužial, autá z tej doby majú veľkú spotrebu. Presnejšie, jeden liter na kilometer a teda Andrej nemôže ísť len tak cez ľubovoľné cesty, lebo sa mu môže pokojne stať, že mu dojde benzín v polovici cesty ďaleko od najbližšej pumpy.

Úloha

Na vstupe máte dané , počet miest, , počet obojsmerných ciest a , kapacitu nádrže Andrejovho auta. Mestá su pre jednoduchosť očíslované od po . Andrej býva v meste číslo jedna a veterán revue sa koná v meste číslo . Ďalej nasleduje trojíc kde sú dva konce jednej obojsmernej cesty a je jej dĺžka v kilometroch. Nakoniec nasleduje postupnosť núl a jednotiek kde -te číslo je jednotka práve vtedy, keď sa v -tom meste nachádza pumpa. Môžete predpokladať, že každá pumpa má dostatočné zásoby benzínu. Teda Andrej vždy môže natankovať ľubovoľne veľa, koľko sa mu zmestí do nádrže. Navyše, Andrej býva na vidieku a teda vzdialenosti vnútri miest sú zanedbateľné. Čo znamená, že ak Andrej má dostatok benzínu na to, aby sa dostal do mesta, má aj dostatok benzínu na to, aby sa dostal aj na pumpu, ak v ňom nejaká je. Andrej začína s plnou nádržou.

Keďže Andrej nechce minúť všetky svoje úspory na benzín, nájdite v zadanej cestnej sieti najkratšiu cestu z do takú, že Andrejovi nikdy nedojde benzín na polceste.

---

8. Ospalý Lukáš

15 bodov, kategória O a T

Lukáš sa posledné dva roky cíti veľmi unavený. Keď sa o tom dozvedel Zemčo, hneď mu poradil, že pod jeho domom bude možno staré indiánske pohrebisko a preto sa mu zle spí. Indiáni majú totiž veľmi bohatý posmrtný život a na pohrebisku sú stále oslavy, večierky, recepcie a bankety, ktoré rušia bežných smrteľníkov v spánku.

Lukáš o tom veľa čítal a vynašiel metódu, ako sa dá indiánska aktivita merať (Ale nikomu ju nechce prezradiť) . Podľa indiánskej aktivity vie zistiť, ako kvalitne môže spať. Deň pre jednoduchosť rozdelil na rovnako dlhých častí. Niekoľko mesiacov po sebe meral aktivitu indiánov, potom hodnoty v každej z častí dňa spriemeroval a aktivitu indiánov prepočítal na kvalitu spánku. Pre každý z časových úsekov teda získal jedno číslo, ktoré udáva, koľko energie vie získať v danom časovom úseku počas spánku.

Teraz chce svoje merania využiť, aby bol menej unavený – vymyslieť pravidelný denný režim, kedy bude spať. Lukáš chce prespať presne z častí dňa, pričom môže ísť spať aj niekoľkokrát za deň. Vždy, keď sa rozhodne prespať niekoľko častí dňa, prvú časť strávi zaspávaním, preto z nej energiu nezíska. Z ostatných častí už získa toľko energie, koľko nameral.

Úloha

Na vstupe sú dané dve kladné celé čísla a udávajúce celkový počet častí dňa a počet častí dňa, ktoré chce Lukáš prespať. Ďalej nasleduje čísel udávajúcich, koľko energie vie získať v danej časti dňa spánkom. Vašou úlohou je zistiť, koľko najviac energie vie získať.

---

9. Tuniakové a iné bagety

15 bodov, kategória T

Mirka to v poslednej dobe v práci vôbec nebaví. Stále dostáva nové úlohy, ktoré musí do nejakej doby splniť a vôbec nemá čas na hry. A tak stále a stále. Ešteže mu na prízemí firmy postavili novú bagetériu, v ktorej začali predávať vynikajúce bagety. Mirko sa začal riadiť loveckým princípom: keď ma práca omrzí, idem si dať bagetu a vyvetrať hlavu. Po čase sa už naučil dokonca dopredu odhadovať, koľko veľa bagetových prestávok bude na konkrétne úlohy potrebovať.

Každá minca má ale dve strany a toto Mirkove spríjemňovanie si práce sa prejavilo aj negatívne. Odborne povedané, Mirkovi začalo troška rásť bruško. Preto sa rozhodol, že ich konzumáciu obmedzí tak veľmi, ako sa len bude dať. Pomôžte Mirkovi a napíšte mu program. Ak sa situácia totiž nezlepší, Mirko stratí výbušnosť a prestane byť dobrý futbalista.

Úloha

Pracovný čas prebieha po minútach. Mirko na začiatku dňa vie, koľko úloh dostane a o každej z nich vie, v ktorej minúte ju dostane a v ktorej minúte ju dokončí (Mirko má nadprirodzené schopnosti, ktoré mu závidia všetci pracujúci na svete.) . Doby plnenia úloh sa všelijako prelínajú a Mirko zvláda naraz robenie ľubovoľného počtu úloh. Ku každej úlohe priradil Mirko minimálny počet bagiet, ktoré bude musieť skonzumovať počas jej plnenia. Každú minútu môže ísť raz na bagetu, pričom čas jedenia bagety je zanedbateľný. Ak Mirko ide na bagetu v minúte, v ktorej dostal úlohu alebo v ktorej končí jej plnenie, táto bageta sa k tejto úlohe ráta. Pri danom rozpise vypočítajte minimálny počet bagiet, ktoré Mirko musí skonzumovať.

Úloha

Na prvom riadku vstupu je jedno číslo – počet úloh; . Pre každú úlohu nasleduje jeden riadok s troma číslami . Číslo označuje minútu, kedy bude úloha zadaná, minútu, kedy skončí a počet bagiet, ktoré si úloha vyžaduje. Platí a navyše . Inými slovami: úloha je vždy riešiteľná.

Vypíšte práve jeden riadok a v ňom jedno číslo – minimálny počet bagiet, ktoré si Mirko musí kúpiť.

Pre odovzdanie tejto úlohy je potrebné byť registrovaný na Liahni a odovzdať riešenie na adrese https://liahen.ksp.sk//task.php?task_id=44 (úloha je medzi špeciálnymi úlohami a volá sa bageta). Riešenia tejto úlohy nám neposielajte poštou. Body dostanú len tí, ktorí ju odovzdali elektronicky.

Pri odovzdávaní bude riešenie otestované na príklade zo zadania – takto si môžete overiť, či máte správny formát vstupu a výstupu. Po termíne odovzdania riešení bude posledné odovzdané riešenie každého z riešiteľov otestované na iných testovacích vstupoch. Body za túto úlohu dostanete podľa úspešnosti vašich programov pri testovaní. Prosíme vás zároveň, aby ste si po registrácii vyplnili svoje celé meno. Musíme totiž vedieť, komu body patria. Kto tak nespraví, body za túto úlohu nedostane.

---

10. Obchodný cestujúci má hlad

15 bodov, kategória T

Obchodnému cestujúcemu Mišovi napiekla jeho babka jablkovú štrúdľu. Keďže on má štrúdle rád, tak si povedal, že si pre ňu príde. Ale keďže jeho babka býva v inom meste ako on, tak by to nebol pravý obchodný cestujúci, keby si tento výlet nespojil s obchodnou cestou. Preto si chce naplánovať takú obchodnú cestu, ktorá bude vychádzať aj sa končiť v jeho rodnom meste, nebude viac ako raz prechádzať cez rovnaké mesto, a navštívi počas nej aj svoju babičku. Má to ale jeden háčik. Celá táto cesta musí byť čo najkratšia, aby štrúdľa nestihla vychladnúť, kým sa s ňou Mišo vráti domov. Pomôžte mu nájsť túto cestu!

Úloha

Na vstupe je neorientovaný graf, konkrétne počet vrcholov a počet hrán medzi nimi . Nasleduje riadkov, na každom je trojica celých čísel , ktoré udávajú dĺžku hrany medzi -tym a -tym vrcholom. Medzi dvoma vrcholmi môže viesť viac ako jedna hrana. Vašou úlohou je nájsť najkratšiu kružnicu (t.j. cestu, ktorá začína aj končí v tom istom vrchole a cez žiadny iný vrchol neprechádza viac ako raz) , ktorá prechádza cez prvý a posledný (-tý) vrchol. Ak takáto kružnica neexistuje, váš program má o tom podať správu.

---