Bakalářskápráce Sadaúlohprovýuku programování

Západočeská univerzita v PlzniFakulta aplikovaných věd

Katedra informatiky a výpočetní techniky

Bakalářská práce

Sada úloh pro výukuprogramování

Plzeň 2017 Ondřej Skála

Prohlášení

Prohlašuji, že jsem bakalářskou práci vypracoval samostatně a výhradněs použitím citovaných pramenů.

V Plzni dne 25. dubna 2017

Ondřej Skála

Poděkování

Mé poděkování patří Ing. Arnoštce Netrvalové, Ph.D., za odborné vedení,cenné rady, trpělivost a ochotu, kterou mi v průběhu zpracování bakalářsképráce věnovala.

AbstractThis thesis deals with well-known online systems for programming training,which are described from the point of view of using of these systems and theirfocus. In the first part of thesis there are also described task descriptions.

In the second part of the thesis there is described set of chosen tasksfor teaching of programming on Faculty of Applied Sciences of Universityof West Bohemia. For each chosen task there are described task analysis,algorithms suitable for solving of the task and software solution. The correct-ness of each of software solutions was checked on the validator of appropriatesystem for programming training.

AbstraktPráce se ve své první části zabývá známými systémy pro nácvik programo-vání, které popisuje z hlediska práce s danými systémy a jejich zaměření.Rovněž jsou v první části práce popsána zadání úloh na serverech těchtosystémů.

Ve druhé části práce jsou uvedeny vybrané úlohy vhodné pro výukuprogramování na Fakultě aplikovaných věd Západočeské univerzity v Plzni.U jednotlivých úloh je provedena analýza, popsány algoritmy vhodné prořešení úloh a dále je uvedeno programové řešení úloh. Správná funkčnostprogramových řešení úloh byla zkontrolována validátorem příslušného sys-tému pro nácvik programování.

Obsah

1 Úvod 7

2 Online systémy pro nácvik programování 82.1 CodeChef . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.1 Zadání úloh . . . . . . . . . . . . . . . . . . . . . . . 92.1.2 Možné výsledky validace úloh . . . . . . . . . . . . . 10

2.2 CodinGame . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2.1 Zadání úloh . . . . . . . . . . . . . . . . . . . . . . . 112.2.2 Možné výsledky validace úloh . . . . . . . . . . . . . 12

2.3 HackerRank . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3.1 Zadání úloh . . . . . . . . . . . . . . . . . . . . . . . 132.3.2 Možné výsledky validace úloh . . . . . . . . . . . . . 14

2.4 Sphere Online Judge . . . . . . . . . . . . . . . . . . . . . . 142.4.1 Zadání úloh . . . . . . . . . . . . . . . . . . . . . . . 152.4.2 Možné výsledky validace úloh . . . . . . . . . . . . . 15

2.5 TopCoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.5.1 Zadání úloh . . . . . . . . . . . . . . . . . . . . . . . 172.5.2 Možné výsledky validace úloh . . . . . . . . . . . . . 18

2.6 UVa Online Judge . . . . . . . . . . . . . . . . . . . . . . . 182.6.1 Zadání úloh . . . . . . . . . . . . . . . . . . . . . . . 192.6.2 Možné výsledky validace úloh . . . . . . . . . . . . . 19

2.7 Timus Online Judge . . . . . . . . . . . . . . . . . . . . . . 202.7.1 Zadání úloh . . . . . . . . . . . . . . . . . . . . . . . 202.7.2 Možné výsledky validace úloh . . . . . . . . . . . . . 21

3 Vybrané úlohy vhodné pro výuku programování 223.1 Joseph’s Cousin . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.1.1 Originální zadání úlohy . . . . . . . . . . . . . . . . . 243.1.2 Česká verze zadání úlohy . . . . . . . . . . . . . . . . 253.1.3 Analýza úlohy . . . . . . . . . . . . . . . . . . . . . . 263.1.4 Algoritmy vhodné pro řešení úlohy . . . . . . . . . . 263.1.5 Řešení úlohy . . . . . . . . . . . . . . . . . . . . . . . 303.1.6 Výsledek validace . . . . . . . . . . . . . . . . . . . . 30

3.2 All Roads Lead Where? . . . . . . . . . . . . . . . . . . . . 313.2.1 Originální zadání úlohy . . . . . . . . . . . . . . . . . 313.2.2 Česká verze zadání úlohy . . . . . . . . . . . . . . . . 33

3.2.3 Analýza úlohy . . . . . . . . . . . . . . . . . . . . . . 343.2.4 Algoritmy vhodné pro řešení úlohy . . . . . . . . . . 363.2.5 Řešení úlohy . . . . . . . . . . . . . . . . . . . . . . . 433.2.6 Výsledek validace . . . . . . . . . . . . . . . . . . . . 45

3.3 Expensive Subway . . . . . . . . . . . . . . . . . . . . . . . 463.3.1 Originální zadání úlohy . . . . . . . . . . . . . . . . . 463.3.2 Česká verze zadání úlohy . . . . . . . . . . . . . . . . 483.3.3 Analýza úlohy . . . . . . . . . . . . . . . . . . . . . . 503.3.4 Algoritmy vhodné pro řešení úlohy . . . . . . . . . . 513.3.5 Řešení úlohy . . . . . . . . . . . . . . . . . . . . . . . 593.3.6 Výsledek validace . . . . . . . . . . . . . . . . . . . . 59

3.4 Where’s Waldorf? . . . . . . . . . . . . . . . . . . . . . . . . 603.4.1 Originální zadání úlohy . . . . . . . . . . . . . . . . . 603.4.2 Česká verze zadání úlohy . . . . . . . . . . . . . . . . 613.4.3 Analýza úlohy . . . . . . . . . . . . . . . . . . . . . . 633.4.4 Algoritmy vhodné pro řešení úlohy . . . . . . . . . . 633.4.5 Řešení úlohy . . . . . . . . . . . . . . . . . . . . . . . 683.4.6 Výsledek validace . . . . . . . . . . . . . . . . . . . . 69

4 Závěr 70

Literatura 71

Seznam použitých zkratek 73

1 Úvod

V poslední době se na internetu formují velké komunity programátorů ko-lem online systémů, jejichž cílem je usnadnit začátečníkům počátky progra-mování a pokročilým programátorům umožnit rozšíření jejich programátor-ských dovedností. Dalším cílem systémů pro nácvik programování je přípravaprogramátorů na ACM soutěže.

První část práce popisuje známé systémy pro nácvik programování a pří-pravu na ACM soutěže. Popis systémů se zaměřuje především na způsobpráce s danými systémy, počet podporovaných programovacích jazyků, za-měření těchto systémů a v neposlední řadě i na soutěže, které jsou komunitoupři těchto systémech pořádány.

Hlavním cílem bakalářské práce je výběr zajímavých úloh vhodných provýuku programování na počátku bakalářského studia. K vybraným úlohámjsou připraveny české verze zadání úloh, rozbor zadání úloh s analýzou mož-ných algoritmů řešení a rovněž vzorový zdrojový kód programového řešeníúloh v programovacím jazyce Java.

7

2 Online systémy pro nácvikprogramování

Hlavním účelem online systémů pro nácvik programování je zdokonalováníprogramátorských dovedností začínajících i pokročilých programátorů. On-line systémy proto nabízejí svým uživatelům katalogy úloh, z nichž si můžeuživatel konkrétní úloh vybrat a vyřešit.

Uživatelem odeslané řešení je na serveru online systému nejprve přelo-ženo, čímž se zkontroluje správná syntaxe odeslaného zdrojového kódu. Po-kud překlad programu proběhne správně, je následně program spuštěn. Popřekladu programu systém zkontroluje správnou funkci programu, kdy sys-tém programu zadá předem připravenou množinu vstupních dat a následněvýstup programu zvaliduje proti předem připraveným vzorovým výstupnímdatům. Pokud se výstupní data programu shodují s předem připravenýmivýstupními daty, online systém prohlásí odeslané řešení jako správné, v opač-ném případě online systém odeslané řešení odmítne jako nesprávné.

Online systémy pro nácvik programování typicky umožňují zobrazit po-řadí uživatelů s nejvyšším počtem odeslaných správných řešení, která bylavyhodnocena jako správná, a dále pořadí uživatelů podle času, který vyža-doval odeslaný program pro svůj běh se vzorovými vstupními daty [17].

Na serverech online systémů jsou rovněž často pořádány programátorskésoutěže, mezi něž patří například ACM International Collegiate Program-ming Contest. Systémy umožňují svým uživatelům na tyto soutěže trénovat.

Mezi známé systémy pro nácvik programování můžeme zařadit napříkladsystémy:

• CodeChef,

• CodinGame,

• HackerRank,

• Sphere Online Judge,

• TopCoder,

• UVa Online Judge,

• Timus Online Judge.

8

2.1 CodeChefSystém CodeChef (viz obrázek 2.1) je projektem indické společnosti Directi[1], která na trhu působí jako registrátor doménových jmen. Systém Code-Chef umožňuje nácvik programování ve více než 35 programovacích jazycích,mezi něž patří nejen obvyklé jazyky jako např. Java, ANSI C, C++, Python,LISP, ale rovněž jsou mezi podporovanými jazyky zastoupeny některé méněobvyklé programovací jazyky jako např. F#, Nice, LUA.

Obrázek 2.1: Logo systému CodeChefZdroj: http://www.codechef.com [cit. 2016/10/17]

Server každý měsíc pořádá několik soutěží, v nichž mohou uživatelé vy-hrát hodnotné ceny. Mezi soutěže, které jsou pořádány každý měsíc, patřínapříklad soutěž „Cook-Off“, která obsahuje několik úloh, na jejichž vyře-šení mají soutěžící 2,5 hodiny.

Pro uživatele jsou na serveru připraveny návody k některým úlohám natomto serveru. Dále se zde nachází rozpracované kurzy pro témata týkajícíse algoritmizace. V době psaní této části práce (říjen 2016) bylo dostupných8 kurzů, dalších 5 kurzů čekalo na dokončení.

2.1.1 Zadání úlohPro uživatele jsou v katalogu příkladů úlohy rozděleny do pěti skupin - úlohypro začátečníky, lehké úlohy, středně těžké úlohy, těžké úlohy a výzvy. Díkyrozdělení problémů podle obtížnosti není programátor začátečník frustrován,že není schopen vyřešit pro něj složitou úlohou, a zároveň pokročilý progra-mátor není „nuděn“ příliš jednoduchými zadáními úloh. Uživatelům jsoudále přístupné odeslané zvalidované zdrojové kódy ostatních uživatelů, tedyuživatelé se mohou podívat na správná řešení daného problému odeslanájinými uživateli.

Zadání úloh jsou dostupná v angličtině, mandarínské čínštině, ruštiněa vietnamštině. U každé úlohy je popsán problém, struktura vstupních dat,očekávaná struktura výstupních dat, omezení vstupních dat, ukázkový vstupa výstup. Dále jsou u každé úlohy uvedena omezení systémových prostředků,

9

http://www.codechef.com

které může uživatelem odeslaný program využívat. Jde o časový limit, bě-hem něhož musí program vyřešit zadaný problém pro daná vstupní data,a maximální možnou velikost zdrojového kódu odeslaného uživatelem k vali-daci. Zadání úlohy rovněž obsahuje seznam programovacích jazyků, v nichžmůže být řešení dané úlohy zrealizováno.

U některých úloh ze sekce začátečnických, lehkých a středně těžkých úlohzadání rovněž obsahuje stručné vysvětlení dané úlohy. Úloha také může býtsložena z více podúloh. V případě úlohy s podúlohami řešitel obdrží alespoňčást bodů, pokud je program schopen v daném časovém limitu vyřešit ome-zený rozsah vstupních dat, ale není dostatečně rychlý pro vyřešení většíchvstupních dat v zadaném časovém limitu.

2.1.2 Možné výsledky validace úlohSystém CodeChef podle výsledku proběhlé validace uživateli oznámí jedenz následujících výsledků validace: [2]:

• Compile Error - v případě syntaktické chyby v odeslaném řešenínebo pokud uživatel nedodržel závazné pokyny (například v případěprogramovacího jazyka Java není třída, ve které je uložena metodamain, pojmenovaná Main);

• Time Limit Exceeded - v případě, kdy program nevyřeší řešenouúlohu pro daná vstupní data v časovém limitu, který je uveden v zadáníkaždé z úloh;

• Runtime Exception nebo Runtime Error - v případě, kdy běhemvykonávání programu dojde k chybě, například vyhození výjimky;

• SIGSEGV - v případě, kdy program přistupuje k neplatné referenčníproměnné nebo dojde k porušení ochrany paměti (anglicky „segmenta-tion fault“);

• SIGABRT - v případě přerušení programu z důvodu fatální chyby(například v případě jazyka C++ není splněn predikát obsažený v pří-kazu assert);

• SIGFPE - v případě chyby výpočtu s plovoucí desetinnou čárkou(například pokud je v programu obsažena instrukce dělení nulou);

• NZEC - v případě, kdy návratový kód spuštěného programu není ro-ven nule (například pokud v případě programovacího jazyka C metodamain vrací jinou hodnotu než nula, v případě programovacího jazyka

10

Java může jít o případ, kdy je během běhu programu vyhozena vý-jimka);

• Wrong Answer - v případě, kdy se výstup hodnoceného programuneshoduje se vzorovým výstupem pro danou úlohu a daná vzorovávstupní data;

• Accepted - v případě, kdy výstup hodnoceného programu je správný,tedy pokud se shoduje se vzorovým výstupem pro danou úlohu a danávzorová vstupní data.

2.2 CodinGameFrancouzský systém CodinGame (viz obrázek 2.2) je provozován stejnojmen-ným francouzským startupem. Systém umožňuje svým uživatelům rozšiřo-vání programátorských dovedností v 25 programovacích jazycích, mezi nimižnechybí běžní zástupci jako například ANSI C, Java a PHP. Rovněž jsou za-stoupeny i méně obvyklé programovací jazyky, například Clojure, Dart aSwift [3].

Obrázek 2.2: Logo systému CodinGameZdroj: http://www.codingame.com [cit. 2016/10/19]

Jedním z cílů systému CodinGame je umožnit společnostem hledat novézaměstnance mezi uživateli systému. Společnosti hledající zaměstnance majímožnost na tomto serveru pořádat a sponzorovat soutěže a mezi soutěžícímidané soutěže pak mohou hledat nové zaměstnance pro rozšíření řad stáva-jících zaměstnanců. Soutěže mohou probíhat online, v tomto případě majísoutěže delší časové okno, během něhož mohou uživatelé soutěžit. Druhoumožností jsou soutěže, které probíhají na jednom místě v jeden čas. Všechnysoutěže jsou plně anonymní a společnosti hledající nové zaměstnance mohouobdržet osobní údaje soutěžícího pouze s výslovným souhlasem uživatele,jehož osobní údaje požadují.

2.2.1 Zadání úlohÚlohy, na tomto serveru nazývané puzzle, jsou v případě úloh, které jsouurčeny pro trénování programování, rozděleny na úlohy jednoduché, středně

11

http://www.codingame.com

těžké, těžké, velmi těžké, úlohy připravené jinými uživateli a úlohy týkajícíse strojového učení. U každé z trénovacích úloh je uvedeno, jaké oblasti sedaná úloha týká a obtížnost úlohy, dále co by si měl uživatel vyřešením danéúlohy procvičit a odkazy na externí zdroje, které se týkají úlohy. Uživatel simůže zobrazit algoritmus pro vyřešení dané úlohy, pseudokód řešení i řešenízapsané v uživatelem vybraném programovacím jazyce.

Každá úloha je koncipována jako počítačová hra. Příkladem může býtúvodní hra s názvem Onboarding, v níž má uživatel za úkol bránit planetupřed invazí mimozemských lodí. Vstupem programu je název dvou mimozem-ských lodí a jejich vzdálenost od planety. Pro vyřešení úlohy musí uživatel vesmyčce sestřelovat bližší loď, přičemž sestřelení uživatel provede vypsánímjména lodi na konzoli. Prostředí systému umožňuje vizualizaci běhu pro-gramu, kdy uživatel vidí průběh hry, v případě úlohy Onboarding docházík sestřelování lodí, jak je zřejmé z obrázku 2.3.

Obrázek 2.3: Vizualizace průběhu programového řešení úlohy Onboarding

2.2.2 Možné výsledky validace úlohV případě syntaktické chyby v programu systém uživateli ve webovém roz-hraní přímo zobrazí problematickou část kódu, v níž se nachází syntaktickáchyba. V případě, kdy překlad programu proběhne bezproblémově, začínávlastní hra. Uživatel vyhraje, pokud jeho program správně vyřeší úlohu prodaná vstupní data, nebo prohraje, pokud řešení odeslané uživatelem neníschopno správně vyřešit danou úlohu.

Hodnocení programu sestává z jednoho nebo více testovacích případů.Pokud uživatelův program vyřeší alespoň jeden z testovacích případů, je

12

validované řešení procentuálně ohodnoceno, přičemž hodnocení odpovídápoměru vyřešených testovacích případů vůči celkovému počtu testovacíchpřípadů.

2.3 HackerRankPrimárním cílem systému HackerRank (viz obrázek 2.4), provozovaného stej-nojmennou společností, je usnadnit společnostem, které hledají nové zaměst-nance, hledání nových talentů pro rozšíření řad stávajících zaměstnanců. Sys-tém proto hodnotí své uživatele na základě jejich programátorských schop-ností, což umožňuje společnostem redukovat čas nutný pro výběr kandidátůvhodných pro nabízené pracovní pozice [4]. K hodnocení uživatelů je naserveru používán hodnotící systém založený na ELO, pomocí něhož je prokaždého uživatele, který se účastní soutěže, spočítáno pravděpodobné umís-tění v soutěži. Pokud je uživatelem dosažené umístění v rámci dané soutěželepší, než bylo očekáváno, tak se hodnocení uživatele zvýší, v opačném pří-padě dojde ke snížení hodnocení uživatele [5].

Obrázek 2.4: Logo systému HackerRankZdroj: http://upload.wikimedia.org [cit. 2016/10/20]

Na serveru jsou pořádány soutěže, přičemž hodnocení uživatele v někte-rých z pořádaných soutěží slouží pro výpočet ohodnocení uživatele. Sou-těže jsou na serveru roztříděny do kategorií, kterých se daná soutěž dotýká.Z kategorií lze jmenovat například umělou inteligenci, algoritmizaci, funkci-onální programování, některé soutěže pak jsou zařazeny do kategorií podlepodporovaného programovacího jazyka, například v minulosti šlo o soutěžezaměřené na programovací jazyky Java, C++ a SQL.

2.3.1 Zadání úlohV části systému věnované trénování programování jsou úlohy koncipovanéjako kurzy, které se týkají nějakého problému. Jsou zde zařazeny jak kurzykonkrétních programovacích jazyků (například Java, C++, Python, Ruby,

13

http://upload.wikimedia.org

SQL), tak i kurzy, které se zabývají konkrétní oblastí (například umělá inte-ligence, datové struktury, distribuované systémy, funkcionální programování,databáze a další).

Podle typu kurzů se pak liší výčet podporovaných jazyků, kdy u kurzůtýkajících se konkrétního programovacího jazyka může být povolený jen je-den jazyk, nicméně u kurzů zabývajících se nějakou problémovou oblastí,jako je například kurz týkající se datových struktur, je povolených jazykůvíce. Nicméně i v tomto případě může být seznam povolených programova-cích jazyků omezený vzhledem k vlastnostem konkrétního jazyka (napříkladv případě kurzu týkajícího se spojového seznamu jsou povoleny jen některéobjektově orientované programovací jazyky - Java, C++, Python). U kurzů,u nichž není výběr jazyka nijak omezen, si může uživatel vybrat z dosta-tečného množství jazyků, mezi nimiž nechybí běžní zástupci (například C,C++, Java), méně obvyklé programovací jazyky (například Nim, Julia, Clo-jure) a nalezneme zde i některé ezoterické programovací jazyky (napříkladLOLCODE, Whitespace).

U každé úlohy je uveden stručný rozbor úlohy, náročnost úlohy a ma-ximální bodové ohodnocení úlohy. Uživatel získá maximální počet bodů,pokud odeslaný program správně vyřeší všechny testovací případy, méněbodů pak uživatel obdrží v případě, kdy jeho program není schopen vyřešitvšechny testovací případy, avšak vyřeší alespoň jeden testovaný případ.

2.3.2 Možné výsledky validace úlohPo odeslání řešení uživatelem systém program přeloží a spustí. V případěsyntaktické chyby v programu systém uživateli ve webovém rozhraní přímozobrazí chybu. Pokud překlad proběhne správně, systém spustí programa zkontroluje výstupní data. V případě chybného výstupu systém uživatelizobrazí vstupní data a výstup programu pro daný testovací případ. Pokudje výstup programu správný, systém uživateli oznámí úspěšnou validaci pro-gramu.

2.4 Sphere Online JudgeSystém Sphere Online Judge (viz obrázek 2.5) je provozován polskou spo-lečností Sphere Research Labs. Systém v době psaní této části práce (říjen2016) podporuje více než 45 programovacích jazyků [6], mezi nimiž jsouběžní zástupci jako například C, C++, Java; zástupci méně používanýchprogramovacích jazyků, mezi nimiž nalezneme například Nice, Nim, LUA; a

14

dále některé ezoterické programovací jazyky, z nichž je zastoupen napříkladWhitespace [6].

Na serveru je pořádáno mnoho soutěží, systém Sphere Online Judge oddoby svého vzniku hostoval více než 4000 soutěží [7].

Obrázek 2.5: Logo systému Sphere Online JudgeZdroj: http://spoj.com [cit. 2016/10/20]

2.4.1 Zadání úlohServer nabízí více než 13000 úloh pro trénování programování [6], jejichžzadání jsou dostupná ve více jazycích, konkrétně v angličtině, polštině, viet-namštině, portugalštině a dalších jazycích.

Úlohy jsou rozděleny do čtyř kategorií podle možných výsledků validace[8]. Jde o klasické úlohy, kde jsou možné dva výsledky validace - úspěšnávalidace nebo špatná odpověď, dále jsou zde úlohy „výzvy“, kde je uživa-tel hodnocen na základě kvality jeho řešení (například na základě velikostizdrojového kódu odeslaného řešení nebo na základě rozdílu přesného řešenía programem vypočteného přibližného řešení). Dalším typem úloh je typ„tutorial“, které odpovídají typu klasických úloh, ale jde o jednodušší úlohynebo úlohy s obecně známým algoritmem řešení, což tento typ úloh před-určuje k výukovým účelům. Posledním typem jsou úlohy typu „partial“,které odpovídají úlohám typu „výzva“, ale jsou podobně jako úlohy typu„tutorial“ určeny pro výukové účely.

Popis zadání úlohy sestává z popisu úlohy, popisu vstupních dat, popisupožadované struktury výstupních dat a příkladů vstupu a požadovanéhovýstupu. Dále jsou u popisu úlohy uvedeny informace o časovém limitu,během něhož musí program vyřešit zadaný problém pro daná vstupní data,a o maximální možné velikosti souboru se zdrojovým kódem odeslanéhouživatelem k validaci. Zadání úlohy rovněž obsahuje seznam programovacíchjazyků, v nichž může být programové řešení dané úlohy napsáno.

2.4.2 Možné výsledky validace úlohSystém Sphere Online Judge podle výsledku proběhlé validace uživatelioznámí jeden z následujících výsledků validace [8]:

15

http://spoj.com

• Compile Error - v případě syntaktické chyby v odeslaném řešenínebo pokud uživatel nedodržel závazné pokyny;

• Time Limit Exceeded - v případě, že program nevyřeší řešenouúlohu pro daná vstupní data v časovém limitu, který je uveden v zadáníkaždé z úloh;

• Runtime Error - v případě, že během vykonávání programu dojdek chybě, například vyhození výjimky;


• Accepted - v případě, kdy výstup hodnoceného programu je správný,tedy pokud se shoduje se vzorovým výstupem pro danou úlohu a danávzorová vstupní data;

V případě chyby Runtime Error je uživateli zobrazena zpráva, kde jechyba blíže specifikována. Může se jednat o následující stavy:

• SIGSEGV - v případě, kdy program přistupuje k neplatné referenčníproměnné nebo dojde k porušení ochrany paměti (anglicky „segmenta-tion fault“);

• SIGFXSZ - v případě, kdy program vytiskne příliš mnoho dat navýstup;

• SIGABRT - v případě přerušení programu z důvodu fatální chyby(například v C++ není splněn predikát obsažený v příkazu assert);

• SIGFPE - v případě chyby výpočtu s plovoucí desetinnou čárkou(například dělení nulou);

• NZEC - v případě, kdy návratový kód spuštěného programu není ro-ven nule (například pokud v případě programovacího jazyka C metodamain vrací jinou hodnotu než nula, v případě programovacího jazykaJava může jít o případ, kdy je během běhu programu vyhozena vý-jimka);

• Other - v případě jiného problému, který vedl k předčasnému ukončeníprogramu.

16

2.5 TopCoderSystém TopCoder (viz obrázek 2.6) je provozován společností Appirio, kteránabízí služby v oblasti crowdsourcingu [9].

Stěžejním cílem portálu je crowdsourcing, kdy uživatelé v rámci soutěžívykonávají nějaký úkol v zájmu společnosti, která danou soutěž vypsala.Společnost po skončení soutěže vybere nejlepší řešení a jejich autory finančněodmění. Nejlepší řešení pak společnost může použít v rámci své podnikatel-ské aktivity.

Obrázek 2.6: Logo systému TopCoderZdroj: http://topcoder-qa.com [cit. 2016/10/20]

Systém TopCoder se zaměřuje na hledání programátorů a dalších ITspecialistů, kteří řeší výzvy vypisované zákazníky systému. V současné doběkomunita systému TopCoder zahrnuje jeden milion členů a ročně je vypsánovíce než 7 tisíc crowdsourcingových výzev [9].

Systém rovněž obsahuje systém pro nácvik programování nazvaný Top-Coder Arena. Systém v době psaní této části práce (říjen 2016) podporujepouze 5 programovacích jazyků, kterými jsou Java, C++, C#, VB.NET aPython.

2.5.1 Zadání úlohÚlohy jsou rozděleny podle své obtížnosti na úlohy lehké, středně těžkéa těžké. U každé úlohy je rovněž zobrazen počet bodů, který lze za vyřešeníúlohy získat. Počet bodů je přímo úměrný obtížnosti dané úlohy.

Na rozdíl od jiných validátorů systém TopCoder nepožaduje napsání ce-lého funkčního programu, ale požaduje pouze metodu, resp. funkci, kterájako svoji návratovou hodnotu vrací řešení pro daná vstupní data. Vstupnídata jsou metodě, resp. funkci, předána ve formě formálních parametrů.Vzhledem k tomuto zadání úlohy rovněž obsahuje definici požadované me-tody, resp. funkce. Obsah této definice se liší podle použitého programova-cího jazyka, pro programovací jazyk Java jde o název třídy, název metody,typ formálních parametrů dané metody a typ návratové hodnoty.

Zadání dále obsahuje omezení na systémové prostředky, které mohoubýt použity odeslaným řešením. Jde o časový limit, během něhož program

17

http://topcoder-qa.com

musí vyřešit úlohu pro všechny sady vstupních dat, a maximální množstvíoperační paměti, kterou může program alokovat.

V zadání jsou rovněž uvedena omezení, která jsou kladena na vstupnídata. Poslední částí zadání jsou příklady vstupních dat a jim odpovídajícívýstupní data. Rovněž zde jsou v případě trénovacích úloh uvedena vysvět-lení výpočtu pro daná vstupní data.

2.5.2 Možné výsledky validace úlohUživatel nejprve musí své řešení přeložit. V případě, kdy zdrojový kód obsa-huje syntaktické chyby, je uživateli zobrazena chybová hláška, v níž je rovněžuvedena problematická část kódu. Pokud překlad proběhne bez problémů,je uživateli oznámeno, že překlad proběhl úspěšně.

V této chvíli uživatel může odeslat své řešení. Uživateli je zobrazeno,kolik za své řešení obdrží bodů. Počet bodů, které uživatel obdrží za vyřešeníúlohy, je nepřímo úměrný času, který uživatel na vyřešení úlohy potřeboval[10], tedy čím déle uživatel úlohu řešil, tím méně bodů může získat. Poodeslání řešení není automaticky spuštěna validace, validaci musí manuálněspustit uživatel. Po validaci je uživateli zobrazena informace, zdali validaceproběhla úspěšně nebo neúspěšně.

2.6 UVa Online JudgeSystém UVa Online Judge (viz obrázek 2.7) je provozován španělskou Uni-versidad de Valladolid a je zaměřen na nácvik programování a přípravu naACM soutěže. Systém v době psaní této části (říjen 2016) podporuje 6 pro-gramovacích jazyků, kterými jsou ANSI C, Java, C++, C++11, Pascal aPython. Na serveru jsou, podobně jako na jiných obdobných serverech, po-řádány soutěže v programování.

Obrázek 2.7: Logo systému UVa Online JudgeZdroj: http://disi.unal.edu.co [cit. 2016/11/10]

18

http://disi.unal.edu.co

2.6.1 Zadání úlohÚlohy jsou na serveru UVa Online Judge rozděleny dle svého původu. Jde na-příklad o úlohy z proběhlých soutěží, úlohy typu „Programming Challenges“a další. Úlohy nejsou rozděleny podle své obtížnosti nebo tématu, kteréhose úloha týká.

Zadání každé úlohy sestává z popisu problému, popisu struktury vstup-ních dat, požadované struktury výstupních dat, ukázkové sady vstupníchdat a k této sadě odpovídajících výstupních data. Zadání úlohy dále ob-sahuje časový limit, během něhož musí program vyřešit úlohu pro všechnysady vstupních dat. V zadání úloh jsou rovněž dostupné statistiky, v nichž semůže uživatel informovat o výsledcích validace všech odeslaných řešení všechuživatelů pro konkrétní úlohu a dále o programovacích jazycích, v nichž bylaodeslaná řešení realizována.

Ve statistikách je uživatel rovněž informován o dvaceti nejlepších úspěš-ných řešeních z hlediska doby jejich běhu. Uživatel se může podívat, v jakýchprogramovacích jazycích byla nejlepší řešení realizována a také na čas nutnýpro běh těchto řešení.

2.6.2 Možné výsledky validace úlohSystém UVa Online Judge uživateli po validaci odeslaného řešení oznámíjeden z výsledků [12]:


• Presentation Error - v případě, kdy je výstup programu správný,ale neodpovídá požadované struktuře výstupu (například přebývajícínetisknutelný znak);


• Compilation Error - v případě syntaktické chyby v odeslaném řešenínebo pokud uživatel nedodržel závazné pokyny (například v případěprogramovacího jazyka Java není třída, ve které je uložena metodamain, pojmenovaná Main);


19


• Memory Limit Exceeded - v případě, kdy program používá víceoperační paměti, než je povoleno;

• Output Limit Exceeded - v případě, kdy program na výstup vypi-suje příliš mnoho informací;

• Submission Error - v případě chyby při odesílání řešení na server;

• Restricted Function - v případě, kdy program používá funkci, kteráje potenciálně nebezpečná a je proto zakázána;

• Can’t Be Judged - v případě, kdy server nemá k dispozici vstupnía výstupní validační data pro kontrolu uživatelem odeslaného řešení.

2.7 Timus Online JudgeRuský systém Timus Online Judge je provozován Uralskou federální univer-zitou. Systém je zaměřen na nácvik programování a přípravu na ACM sou-těže, z nichž systém přejímá některé úlohy do svého katalogu úloh. SystémTimus Online Judge v době psaní této části práce (říjen 2016) podporuje11 programovacích jazyků, kterými jsou C, C++, Pascal, Java, C#, Go,Python, Ruby, Haskell, Scala a Rust [11].

2.7.1 Zadání úlohÚlohy jsou na serveru Timus Online Judge rozděleny dle více kritérií. Naserveru nalezneme úlohy rozdělené podle témat, jehož se jednotlivé úlohytýkají (dynamické programování, datové struktury, grafové úlohy, . . . ), nebopodle soutěží, z nichž byly úlohy přebrány.

U každé úlohy je uvedeno, kolik uživatelů úlohu úspěšně vyřešilo a nume-ricky vyjádřená obtížnost úlohy. Uživatel si může zobrazit výsledky ostatníchuživatelů, kde je zobrazen čas, po který program běžel a programovací jazyk,v němž bylo napsáno programové řešení dané úlohy, avšak uživateli nejsoudostupné zdrojové kódy programových řešení ostatních uživatelů.

Zadání úloh obsahuje „příběh v pozadí“, popis úlohy, popis vstupníchdat a na vstupní data kladená omezení, popis požadované struktury vý-stupu programu, omezení na čas, po který může program běžet a maximálnímnožství paměti, které může program alokovat.

20

2.7.2 Možné výsledky validace úlohPodle výsledku validace odeslaného řešení je uživateli oznámen jeden z ná-sledujících výsledků [11]:


• Compilation Error - v případě syntaktické chyby v odeslaném řešenínebo pokud uživatel nedodržel závazné pokyny (například v případěprogramovacího jazyka Java zdrojový kód obsahuje více než jednu ve-řejnou třídu);



• Memory Limit Exceeded - v případě, kdy program používá víceoperační paměti, než je povoleno;

• Output Limit Exceeded - v případě, kdy program na výstup vypi-suje příliš mnoho informací;

• Idleness Limit - v případě, kdy je program příliš dlouho nečinný;


• Restricted Function - v případě, kdy program používá funkci, kteráje potenciálně nebezpečná a je proto zakázána (například komunikacepo síti nebo přístup k souborům).

Každá úspěšně zvalidovaná úloha je ohodnocena, hodnocení je spočítánopodle doby, kterou validovaný program potřeboval pro řešení úlohy [11].

21

3 Vybrané úlohy vhodné provýuku programování

Vybrané úlohy vhodné pro výuku programování na počátku bakalářskéhostudia jsou uvedeny v tabulce 3.1. Úlohy byly vybrány z katalogu úloh vali-dátoru UVa Online Judge, neboť tento systém je využíván v rámci některýchpředmětů vyučovaných na Katedře informatiky a výpočetní techniky Fakultyaplikovaných věd Západočeské univerzity v Plzni a někteří studenti by protoměli mít alespoň základní znalost práce s tímto serverem.

Z hlediska výuky programování můžeme za výhodu považovat, že uživa-telé systému nemají k dispozici zvalidovaná řešení jiných uživatelů a takév zadání úloh není explicitně uvedeno, které oblasti se daná úloha týká.Studenti tedy musí samostatně vyřešit, jaké datové struktury a algoritmypoužijí.

Zdrojové kódy programového řešení všech úloh jsou umístěny na přilože-ném CD.

22

Název úlohy Číslo úlohy Téma úlohyWhere’s Waldorf? 10010 Řetězce, poleFlip-Flop the Squarelotron 10016 PoleAutomated Judge Script 10188 ŘetězceStrategy Game 12959 PoleNewspaper 11340 ŘetězceHuatuos Medicine 12992 Proměnné nebo rekurzeTri-du 12952 PodmínkyJoseph’s Cousin 10015 Zřetězený spojový seznamKnuth’s Permutation 10063 RekurzePrinter Queue 12100 Prioritní frontaErdös Numbers 10044 Nejkratší cesta v grafuPrime Path 12101 Nejkratší cesta v grafuCounting Stars 11244 Prohledávání do hloubky (DFS)Shortest Names 12506 Datová struktura TrieAll Roads Lead Where? 10009 Nejkratší cesta v grafuBicoloring 10004 Určení bipartity grafuThe Tourist Guide 10099 Dynamické programováníVacation 10192 Nejdelší společná podposloupnostSending Email 10986 Nejkratší cesta v grafuExpensive Subway 11710 Minimální kostra grafu

Tabulka 3.1: Úlohy vybrané pro výuku programování

23

3.1 Joseph’s Cousin

3.1.1 Originální zadání úlohy10015 - Joseph’s Cousin

The Josephs problem is notoriously known. For those who are not fa-miliar with the problem, among n people numbered 1; 2; . . . ;n, stan-ding in circle every mth is going to be executed and only the life ofthe last remaining person will be saved. Joseph was smart enough tochoose the position of the last remaining person, thus saving his lifeto give the message about the incident.Although many good programmers have been saved since Josephspread out this information, Josephs Cousin introduced a new vari-ant of the malignant game. This insane character is known for itsbarbarian ideas and wishes to clean up the world from silly progra-mmers. We had to infiltrate some the agents of the ACM in order toknow the process in this new mortal game.In order to save yourself from this evil practice, you must develop atool capable of predicting which person will be saved.The Destructive ProcessThe persons are eliminated in a very peculiar order; m is a dynamicalvariable, which each time takes a different value corresponding to theprime numbers succession (2, 3, 5, 7, . . .). So in order to kill the i-thperson, Joseph’s cousin counts up to the i-th prime.InputIt consists of separate lines containing n[1..3501], and finishes witha ‘0’.OutputThe output will consist in separate lines containing the position of theperson which life will be saved.Sample Input60Sample Output4

Originální zadání úlohy je dostupné na adrese: https://uva.onlinejudge.org/external/100/10015.pdf [cit. 2016/11/02].

24

https://uva.onlinejudge.org/external/100/10015.pdf


3.1.2 Česká verze zadání úlohy10015 - Josefova sestřenice

Josef se svou sestřenicí nevychází příliš dobře. Je tomu tak i z tohodůvodu, že Josefova sestřenice pořádá prazvláštní rituály, mezi něžpatří i „vražedné kolečko“. Během tohoto rituálu n lidí očíslovaných1; 2; . . . ;n stojí v kruhu a jsou postupně popravováni. Pouze posledníosoba z kruhu je ušetřena a přežije. Josef svoji sestřenici přelstil a vždysi stoupl v kruhu tak, aby byl poslední, a proto dosud vždy přežil. Díkytomu nás mohl informovat o podivném rituálu své sestřenice.Mnoho životů programátorů bylo dosud zachráněno, nicméně Josefovasestřenice, která je známá především díky svým barbarským nápadům,mezi něž patří snaha vyhladit všechny špatné programátory na světě,vymyslela novou verzi tohoto příšerného rituálu. Abychom se dozvědělinová pravidla tohoto rituálu, museli jsme infiltrovat několik našichagentů.Abyste se zachránili před touto ďábelskou praktikou, musíte vytvořitprogram určující pozici osoby, která bude zachráněna a jako jedináz kruhu přežije.Vražedný procesOsoby jsou popravovány ve velice podivném pořadí, kdy m je pro-měnná, která po každé popravě nabývá jiné hodnoty. Hodnoty pro-měnné m odpovídají vzestupně seřazeným prvočíslům (2, 3, 5, 7, . . .).Josefova sestřenice následně počítá do tohoto prvočísla. Osoba, jejížpozice odpovídá tomuto prvočíslu, je popravena a celý smrtící processe opakuje, jen proměnná m nyní obsahuje další prvočíslo.VstupVstup sestává z řádek obsahující číslo n[1..3501], z nichž každá řádkapředstavuje jeden testovací případ. Vstup končí znakem „0“.VýstupVýstupem je číslo pozice osoby, která jako jediná nebude popravena.Pro každý testovací případ musí být číslo pozice uvedeno na novémřádku.Vzorový vstup60Vzorový výstup4

25

3.1.3 Analýza úlohyZe zadání úlohy je zřejmé, že naším úkolem je zvolit vhodnou datovou struk-turu, která umožňuje zřetězený pohyb po elementech uložených v této struk-tuře. V rámci dané datové struktury musíme postupovat v kruhu, kdy sevždy posuneme o m pozic a osobu na této pozici zabijeme.

Například, pokud bychom řešili tuto úlohu pro případ šesti osob, napočátku bychom měli 6 osob očíslovaných 1, 2, 3, 4, 5, 6. V prvním koleje proměnná m rovna prvními prvočíslu, tedy m = 2. Počítáme od prvníosoby a počítání zastavíme u druhé osoby, kterou odstraníme ze seznamupřeživších osob. V dalším kole je m rovna hodnotě 3. Nyní začínáme počítatod osoby, která je další v pořadí po osobě zabité v předchozím kole. Nynítedy počítáme od osoby 3, pokračujeme přes osobu 4 a zastavíme se na osobě5, kterou zabijeme. V dalším kole je m = 5 a odpočítáváme od osoby číslo 6a pokračujeme přes osoby s čísly 1, 3, 4, 6. Odpočítávání zastavíme u osoby6, tu proto odstraníme ze seznamu. Analogickým postupem pokračujeme dodoby, kdy náš seznam obsahuje poslední přeživší osobu, která jako jedinápřežije.

Pro reprezentaci dat lze použít zřetězený spojový seznam, který umož-ňuje snadno procházet osoby v kruhu a zároveň i osoby odstranit, obojí lzedohromady provést s asymptotickou časovou složitostí O(n).

Není nutné simulovat postupné počítání v kruhu stojících osob, obzvláštěv případě, kdy bychom spojový seznam prošli několikrát. Počet pozic, o kterýse máme posunout, je kongruentní modulo n k aktuálnímu prvočíslu ulože-nému v proměnné m. Hodnota n odpovídá aktuálnímu počtu prvků ulože-ných ve spojovém seznamu. Počet pozic, o něž se musíme posunout, tedyodpovídá zbytku po celočíselném dělení m mod n.

3.1.4 Algoritmy vhodné pro řešení úlohyHlavním úskalím úlohy je volba vhodného algoritmu pro generování prvo-čísel vzhledem k časovému limitu na řešení úlohy. Časový limit v případětéto úlohy činí na první pohled velkorysých 10 sekund, nicméně je nutné po-čítat s relativně vysokou maximální hodnotou proměnné n udávající početprvočísel, které je třeba vygenerovat.

Řešení hrubou silou

V případě řešení hrubou silou (viz algoritmus 3.1) vyjdeme z definice prvo-čísla - číslo x je prvočíslo právě tehdy, když je beze zbytku dělitelné pouzečíslem jedna a sebou samým. V případě tohoto algoritmu tedy prvočísel-

26

nost čísla x testujeme dělením čísla všemi čísly, která připadají v úvahu jakomožní bezezbytkoví dělitelé testovaného čísla. Možnými děliteli jsou celá číslapatřící do intervalu < 2,

√x >.

Asymptotická složitost algoritmu činí O(n×√n).

Algoritmus 3.1: Algoritmus hledání prvočísel hrubou silouData: Proměnná pozadovano obsahující požadovaný počet

vygenerovaných prvočíselVýsledek: Pole vygenerovaných prvočísel

1 int pocet = 0; // počet dosud vygenerovaných prvočísel

2 int[] pole; // pole dosud vygenerovaných prvočísel

3 int cislo = 2; // aktuálně testované číslo

4 while pocet < pozadovano do5 boolean vysledek = true; // výsledek testu prvočíselnosti

// vyzkoušíme všechny možné dělitele testovaného čísla

z intervalu < 2,√

cislo >

6 int i = 2;7 for i ≤

√cislo do

8 if cislo mod i = 0 then// pokud je testované číslo beze zbytku dělitelné i,

nemůže jít o prvočíslo

9 vysledek = false;10 break;11 end12 i = i + 1;13 end

// pokud je testované číslo prvočíslem, vložíme jej do pole

vygenerovaných prvočísel a inkrementujeme čítač počtu dosud

vygenerovaných prvočísel

14 if vysledek = true then15 pole[pocet] = cislo;16 pocet = pocet + 1;17 end18 cislo = cislo + 1;19 end

27

Eratosthenovo síto

Eratosthenovo síto (viz algoritmus 3.2) je relativně jednoduchý algoritmuspro generování prvočísel. Algoritmus nehledá zadaný počet prvočísel, na-místo toho algoritmus hledá všechna prvočísla do zadané maximální hodnoty[18].

Algoritmus 3.2: Eratosthenovo síto [18]Data: Proměnná horniMez reprezentující horní mez intervalu,

v němž jsou prvočísla hledánaVýsledek: Pole logických hodnot, kde hodnota na indexu i značí,

zdali je číslo i prvočíslem1 boolean[] pole; // pole s hodnotami prvočíselnosti

2 pole[1] = false; // jedna není prvočíslo

3 int i = 2;// naplnění pole hodnotou true (značí, že čísla jsou prvočíselná)

4 for i ≤ horniMez do5 pole[i] = true;6 i = i + 1;7 end8 int p = 2;9 while p ≤

√horniMez do

// označení násobků prvočísla jako neprvočíselných čísel

10 int n = 2;11 for p× n ≤ horniMez do12 pole[p× n] = false;13 n = n + 1;14 end

// nalezení dalšího prvočísla

15 int x = p + 1;16 while pole[x] 6= true do17 x = x + 1;18 end19 p = x;20 end

Algoritmus pracuje s polem logických hodnot, kde hodnota na indexui značí, zdali je číslo i prvočíslem. Na počátku algoritmus alokuje pole logic-kých hodnot o délce n, kde n značí horní mez intervalu, v němž jsou hledánaprvočísla. Toto pole je naplněno hodnotami true s výjimkou prvního indexu,

28

kam je uložena hodnota FALSE (číslo jedna není obecně považováno za prvo-číslo). Následně algoritmus z pole vybírá nejnižší index, na němž je uloženahodnota TRUE (toto číslo je prvočíslem). Algoritmus dále všechny násobkyvybraného prvočísla označí hodnotou FALSE, neboť tyto násobky nemohoubýt prvočíselné.

Obrázek 3.1: Princip funkce Eratosthenova sítaZdroj: www.murderousmaths.co.uk/books/MMoE/new200sieve.gif

[cit. 2016/11/02]

Princip funkce algoritmu je zřejmý z obrázku 3.1. V prvním kroku jevybráno číslo dva, které je prvočíslem. Dále jsou označeny násobky dvou(v obrázku zeleně) jako čísla, která nejsou prvočísly. V dalším kroku algo-ritmu je vybráno číslo 3 a jeho násobky jsou označeny jako neprvočíselnáčísla (v obrázku modře). Algoritmus takto postupuje do doby, kdy vybranéprvočíslo není větší než odmocnina z horní meze intervalu, v němž jsou pr-vočísla hledána. Ve chvíli, kdy algoritmus vybere první prvočísla větší nežodmocnina z horní meze intervalu, v němž jsou prvočísla hledána, již není

29

www.murderousmaths.co.uk/books/MMoE/new200 sieve.gif

prováděno označování násobků vybraného prvočísla jako neprvočíselných čí-sel a všechna zbývající čísla jsou prvočísla.

Asymptotická časová složitost algoritmu činí O(n log log n) [18].

Další algoritmy

Dále jsou dostupné další algoritmy založené na principu „prosívání“ seznamučísel. Patří mezi ně například moderní algoritmus Atkinova síta, který do-sahuje lepší asymptotické časové složitosti O( n

log log n) [13], ovšem tento algo-

ritmus využívá sofistikovanějších principů a je složitější na pochopení a im-plementaci. Z tohoto důvodu není vhodný k implementaci začínajícími pro-gramátory.

3.1.5 Řešení úlohyV rámci řešení úlohy bylo v první řadě nezbytné zvolit vhodný algoritmuspro generování prvočísel, vzhledem k lepší asymptotické časové složitosti bylzvolen algoritmus Eratosthenova síta. Pro reprezentaci osob stojících v kruhubyl použit spojový seznam reprezentovaný kolekcí LinkedList ze standardníknihovny java.util programovacího jazyka Java.

3.1.6 Výsledek validaceÚloha byla úspěšně zvalidována, čas běhu činil 2,270 sekundy (viz obrázek3.2).

Obrázek 3.2: Zpráva o validaci úlohy Joseph’s Cousin

30

3.2 All Roads Lead Where?

3.2.1 Originální zadání úlohy10009 - All Roads Lead Where?

There is an ancient saying that „All Roads Lead to Rome“. If thiswere true, then there is a simple algorithm for finding a path betweenany two cities. To go from city A to city B, a traveller could take aroad from A to Rome, then from Rome to B. Of course, a shorter routemay exist.The network of roads in the Roman Empire had a simple structure:beginning at Rome, a number of roads extended to the nearby cities.From these cities, more roads extended to the next further cities, andso on. Thus, the cities could be thought of as existing in levels aroundRome, with cities in the ith level only connected to cities in the i−1thand i + 1th levels (Rome was considered to be at level 0). No loopsexisted in the road network. Any city in level i was connected to asingle city in level i − 1, but was connected to zero or more cities inlevel i+1. Thus, to get to Rome from a given city in level i, a travellercould simply walk along the single road leading to the connected i− 1level city, and repeat this process, with each step getting closer toRome.Given a network of roads and cities, your task is to find the shortestroute between any two given cities, where distance is measured in thenumber of intervening cities.InputThe first line is the number of test cases, followed by a blank line.The first line of each test case of the input contains two numbers indecimal notation separated by a single space. The first number (m) isthe number of roads in the road network to be considered. The secondnumber (n) represents the number of queries to follow later in the file.For each test case, in the next m lines in the input each contain thenames of a pair of cities separated by a single space. A city nameconsists of one or more letters, the first of which is in uppercase. Notwo cities begin with the same letter. The name Rome always appearsat least once in this section of input, for each test case; this city isconsidered to be at level 0, the lowest-numbered level. The pairs ofnames indicate that a road connects the two named cities. The firstcity named on a line exists in a lower level than the second named

31

city. The road structure obeys the rules described above. For each testcase, no two lines of input in this section are repeated.The next n lines, for each test case in the input each contain thenames of a pair of cities separated by a single space. City names areas described above. These pairs of cities are the query pairs. Your taskfor each query pair is to find the shortest route from the first namedcity to the second. Each of the cities in a query pair is guaranteed tohave appeared somewhere in the previous input section, for each testcase, describing the road structure.Each test case will be separated by a single line.OutputIn each test case, for each of the n query pairs, output a sequenceof uppercase letters indicating the shortest route between the twoquery pair cities. The sequence must be output as consecutive letters,without intervening whitespace, on a single line. For each test case,the first output line corresponds to the first query pair, the secondoutput line corresponds to the second query pair, and so on. Theletters in each sequence indicate the first letter of the cities on thedesired route between the query pair cities, including the query paircities themselves. A city will never be paired with itself in a query.Print a blank line between the outputs for two consecutive test cases.Sample Input17 3Rome TurinTurin VeniceTurin GenoaRome PisaPisa FlorenceVenice AthensTurin MilanTurin PisaMilan FlorenceAthens GenoaSample OutputTRPMTRPFAVTG

32

Originální zadání úlohy je dostupné na adrese: https://uva.onlinejudge.org/external/100/10009.pdf [cit. 2016/11/10].

3.2.2 Česká verze zadání úlohy10009 - Kam vedou všechny cesty?

„Všechny cesty vedou do Říma,“ tedy alespoň to tvrdí jedno starověkérčení. Pokud by to byla pravda, pak lze sestavit jednoduchý algoritmuspro hledání tras mezi jakýmikoliv dvěma městy. Abychom se dostaliz města A do města B, stačilo by jít z města A do Říma a poté z Římado města B. Samozřejmě by mohla existovat kratší cesta.Síť cest ve starověkém antickém impériu měla jednoduchou strukturu- některé cesty začínaly v Římě a vedly do blízkých měst, z těchto městvedly další cesty do vzdálenějších měst a podobně. Vzhledem k tomutolze města rozdělit do úrovní okolo Říma, kde města i-té úrovně bylacestami spojeny jen s městy i−1-té úrovně a i+1-té úrovně (Řím byl naúrovni 0). V systému cest neexistovaly žádné smyčky. Každé město nai-té úrovni bylo spojeno právě s jedním městem úrovně i+1 a s žádnýmnebo více městy úrovně i− 1. Vzhledem k tomuto uspořádání měst ameziměstských cest mohl cestovatel, jehož cílem byl Řím, jednodušejít po cestě k městu o úroveň nižší než mělo město, v němž se právěnacházel, a tento proces opakoval, dokud nedorazil do Říma.Vaším úkolem je najít nejkratší cestu mezi dvěma zadanými městy,přičemž vzdálenost je rovna počtu navštívených měst.VstupPrvní řádka vstupu obsahuje počet testovacích případů a je následo-vána prázdnou řádkou.Na první řádce každého testovacího případu najdeme dvě dekadickáčísla oddělená mezerou. První číslo m udává počet cest v síti dopravníinfrastruktury, druhé číslo n pak udává počet dvojic měst, mezi nimižmáme najít cestu.Dále jsou uvedeny dvojice měst, které jsou spojeny cestou. Tato městajsou oddělena mezerou. Název města sestává z jednoho a více pís-men, první písmeno názvu města je velké. Je zaručeno, že žádná dvěměsta nebudou mít stejné počáteční písmeno svého názvu. Město Rome(Řím) je uvedeno alespoň jednou v seznamu měst a je umístěno nanulté úrovni v hierarchii měst, která byla popsána výše. První městona řádce je vždy město na nižší úrovni než město uvedené druhé. Jezaručeno, že se nebudou dvojice měst ve vstupu opakovat.

33



Dalších n řádek obsahuje dvojice měst oddělené mezerou, mezi kterýmibudeme hledat nejkratší cestu. Každé město uvedené v dvojicích měst,mezi nimiž hledáme cestu, bylo alespoň jednou uvedeno při definovánícest mezi městy.Každý testovací případ je oddělen prázdnou řádkou.VýstupPro každý testovací případ vypíšeme několik sekvencí velkých písmensložených z počátečních písmen měst na nalezené nejkratší cestě. Sek-vence nesmí obsahovat mezery a musí být vypsána na jedné řádce. Sek-vence obsahuje i počáteční písmena počátečního a koncového města.Jednotlivé vypsané sekvence jsou vždy uvedeny na nové řádce.Výsledné sekvence cest jsou pro každý testovací případ oddělenéprázdnou řádkou.Vzorový vstup17 3Rome TurinTurin VeniceTurin GenoaRome PisaPisa FlorenceVenice AthensTurin MilanTurin PisaMilan FlorenceAthens GenoaVzorový výstupTRPMTRPFAVTG

3.2.3 Analýza úlohyJe zřejmé, že jde o grafovou úlohu. V první řadě je tedy třeba vybrat vhodnoudatovou strukturu pro reprezentaci grafu. Dále bude třeba vybrat vhodnýalgoritmus pro nalezení nejkratších cest v grafu.

Při výběru datových struktur pro reprezentaci grafu máme na výběr zedvou možností, kterými jsou reprezentace spojovým seznamem a reprezen-tace maticí sousednosti. Reprezentace grafu spojovým seznamem (viz obrá-

34

zek 3.3) je vhodná především pro grafy, kde není příliš mnoho hran mezivrcholy. V případě reprezentace grafu spojovým seznamem obsahuje datovástruktura reprezentující vrchol grafu spojový seznam obsahující vrcholy sou-sedící s daným vrcholem, nebo jinak řečeno vrcholy, s nimiž daný vrchol sdílíhrany grafu.

Obrázek 3.3: Reprezentace grafu spojovým seznamemZdroj: http:

//btechsmartclass.com/DS/images/Graph%20Adjacency%20List.jpg[cit. 2016/11/10]

Reprezentace grafu maticí sousednosti (viz obrázek 3.4) je naopak vhodnápro grafy obsahující vrcholy sousedící s mnoha jinými vrcholy. Pokud bychompoužili reprezentaci grafu maticí sousednosti pro graf obsahující jen málohran, dostali bychom řídkou matici sousednosti (za řídkou matici považujemetakovou matici, jejíž prvky jsou z převážné části nulové), což je v případěuložení matice v „hustém formátu“ paměťově značně neefektivní.

Obrázek 3.4: Reprezentace neorientovaného grafu maticí sousednostiZdroj: http://btechsmartclass.com/DS/images/Graph%

20Adjacency%20Matrix%201.jpg [cit. 2016/11/10]

Matici sousednosti sestavíme poměrně jednoduše - nejprve si očíslujemevrcholy grafu od jedné vzestupně. Čísla vrcholů grafu budou představo-

35

http://btechsmartclass.com/DS/images/Graph%20Adjacency%20List.jpg

http://btechsmartclass.com/DS/images/Graph%20Adjacency%20List.jpg

http://btechsmartclass.com/DS/images/Graph%20Adjacency%20Matrix%201.jpg

http://btechsmartclass.com/DS/images/Graph%20Adjacency%20Matrix%201.jpg

vat řádky, resp. sloupce matice sousednosti. Následně matici naplníme datypodle vztahu 3.1, v němž i představuje řádek a j sloupec matice:

mi,j ={

0 . . . pokud vrcholy i a j nejsou spojené hranou,1 . . . pokud vrcholy i a j jsou spojené hranou. (3.1)

V případě neorientovaných grafů je výsledná matice sousednosti symet-rická (viz obrázek 3.4). V opačném případě, kdy uvažujeme orientovaný graf,není matice sousednosti obecně symetrická. Pokud bychom uvažovali ohod-nocený graf, v matici bychom namísto pevné hodnoty 1 značící sousedícívrcholy umístili ohodnocení hrany, která dané dva vrcholy spojuje.

Hlavním úkolem je nalezení nejkratší cesty v grafu, kterou po jejím na-lezení vypíšeme v požadovaném formátu.

3.2.4 Algoritmy vhodné pro řešení úlohyStěžejní částí úlohy je výběr a implementace vhodného algoritmu pro hledánínejkratší cesty v grafu. Ze zadání víme, že graf reprezentující úlohu budeacyklický, neorientovaný a neohodnocený. Tyto atributy jsou důležité provýběr vhodného algoritmu pro nalezení nejkratší cesty v grafu.

Některé algoritmy pro hledání nejkratší cesty v grafu vyžadují ohodno-cený graf. Ohodnocený graf v našem případě získáme poměrně jednoduše.Postačí přiřadit všem hranám v grafu ohodnocení hrany rovno jedné.

Prohledávání do šířky (BFS)

Algoritmus prohledávání grafu do šířky (Breadth-first search, BFS; viz al-goritmus 3.3) především popisuje strategii procházení grafu, nicméně jej lzevyužít i pro hledání nejkratší cesty v neohodnocených grafech [14]. V tomtopřípadě předpokládáme, že všechny hrany grafu mají stejné ohodnocení,které je typicky rovno jedné. V případě, kdy bychom měli ohodnocený graf,lze toto omezení algoritmu překonat „rozsekáním“ hrany s ohodnocenímn na n „jednotkových“ hran, mezi něž umístíme pomocné vrcholy [19].

Princip algoritmu (viz obrázek 3.5) při prohledávání grafu je jednoduchý- nejprve navštívíme startovní vrchol s a do FIFO fronty (FIFO - First InFirst Out; první vrchol, který vstoupil do fronty, ji také jako první opustí)si uložíme sousední vrcholy vrcholu s. V dalším kroku vybíráme z frontyvrcholy, které sousedí s vrcholem s (v obrázku 3.5 jde o vrcholy r a w)a těmto vrcholům nastavíme vzdálenost 1 a předchůdce s. Do fronty si ulo-žíme sousední vrcholy právě navštívených vrcholů. Z těchto vrcholů začneme

36

Algoritmus 3.3: Prohledávání grafu do šířky (BFS) [14]Data: Graf G = (V, H), kde V jsou vrcholy a H hrany grafu, a

startovní vrchol sVýsledek: Pro každý vrchol grafu vzdálenost od vrcholu s a

předchůdce na nejkratší cestě do vrcholu s

// pro každý vrchol grafu nastavíme vzdálenost ∞ a předchůdce NULL

1 foreach vrchol v ∈ V do2 v.vzdalenost = ∞;3 v.predchudce = NULL;4 end

5 s.vzdalenost = 0;// Inicializujeme frontu Q a vložíme do ní vrchol s

6 Fronta Q;7 Q.push(s);

8 while Q není prázdná do9 u = Q.pop();

10 foreach vrchol v sousedící su do// Pokud jsme vrchol ještě nenavštívili

11 if v.vzdalenost 6=∞ then// Nastavíme vzdálenost

12 v.vzdalenost = u.vzdalenost + 1;// Nastavíme předchůdce

13 v.predchudce = u;// Vložíme do fronty

14 Q.push(v);15 end16 end17 end

37

Obrázek 3.5: Ukázka průběhu algoritmu BFSZdroj: http://4.bp.blogspot.com/-cBfQheDKSqw/UL84AjQU7TI/

AAAAAAAABB4/oTq7riy8Zng/s000/bfs.png [cit. 2016/11/12]

opět navštěvovat sousední vrcholy (v obrázku 3.5 jde o vrcholy t, v, x), kte-rým nastavíme vzdálenost 2 a předchůdce podle toho, z jakého vrcholu jsme„přišli“. Takto pokračujeme do doby, než navštívíme všechny dostupné vr-choly [14]. V průběhu algoritmu každý vrchol navštívíme nejvýše jednou.

Asymptotická složitost algoritmu BFS činí v případě reprezentace grafuspojovým seznamem O(m + n), kde m značí počet vrcholů a n počet hran[14].

Dijkstrův algoritmus

Dijkstrův algoritmus (viz algoritmus 3.4) hledá nejkratší cesty v orientova-ném ohodnoceném grafu ze zadaného počátečního vrcholu s do všech zbýva-jících vrcholů v grafu [14]. Předpokladem pro správnou funkčnost algoritmuje nezáporné ohodnocení hran v grafu [14]. Pokud graf obsahuje záporněohodnocené hrany, je nutné pro hledání nejkratší cesty mezi vrcholy pou-

38

http://4.bp.blogspot.com/-cBfQheDKSqw/UL84AjQU7TI/AAAAAAAABB4/oTq7riy8Zng/s000/bfs.png

http://4.bp.blogspot.com/-cBfQheDKSqw/UL84AjQU7TI/AAAAAAAABB4/oTq7riy8Zng/s000/bfs.png

žít jiný algoritmus. Lze použít například Floyd-Warshallův algoritmus neboBellman-Fordův algoritmus, které jsou popsány dále.

Dijkstrův algoritmus lze využít i v neorientovaném grafu [19], neboť ne-orientovaný graf snadno převedeme na orientovaný - postačí mezi dvěmavrcholy v1 a v2, mezi nimiž vedla neorientovaná hrana, položit dvě oriento-vané hrany, z nichž první povede z vrcholu v1 do vrcholu v2 a druhá viceversa, tj. z vrcholu v2 do vrcholu v1 (tento postup ovšem povede k vytvořenícyklů v grafu, což znemožňuje použití některých algoritmů, které vyžadujípro svou správnou funkcionalitu acyklický graf). V případě použití reprezen-tace grafu spojovým seznamem nebo maticí sousednosti, jak bylo popsánovýše, máme již grafy uložené v orientované podobě a lze Dijkstrův algo-ritmus použít rovnou bez nutnosti použití výše popsané úpravy hran grafuz neorientovaných na orientované.

Obrázek 3.6: Ukázka průběhu Dijkstrova algoritmuZdroj: https://www.cs.indiana.edu/~achauhan/Teaching/B403/

LectureNotes/images/10-dijkstra.jpg [cit. 2016/11/12]

Průběh Dijkstrova algoritmu je zobrazen na obrázku 3.6. Vrcholu s na-stavíme vzdálenost rovnu nule a ostatním vrcholům vzdálenost od vrcholus rovnu nekonečnu. V průběhu algoritmu postupně z prioritní fronty odebí-ráme vrcholy s nejnižším ohodnocením a ty prohlašujeme za trvalé (k těmtovrcholům již známe nejkratší cestu; v obrázku 3.6 zobrazeny černě). Následnězkontrolujeme vzdálenosti sousedních vrcholů. Pokud má některý ze soused-ních vrcholů vzdálenost od vrcholu s větší než součet vzdálenosti aktuálníhovrcholu a ohodnocení příslušné hrany incidentní s aktuálním i daným sou-sedním vrcholem, aktualizujeme vzdálenost daného vrcholu (např. ve stavu(c) v obrázku měl vrchol t původní vzdálenost 10, avšak do vrcholu t se

39

https://www.cs.indiana.edu/~achauhan/Teaching/B403/LectureNotes/images/10-dijkstra.jpg

https://www.cs.indiana.edu/~achauhan/Teaching/B403/LectureNotes/images/10-dijkstra.jpg

Algoritmus 3.4: Dijkstrův algoritmus [19]Data: Graf G = (V, H, c), kde V jsou vrcholy, H hrany grafu, c

představuje ohodnocení hran; vrchol sVýsledek: Pro každý vrchol grafu vzdálenost od vrcholu s a



1 foreach vrchol v ∈ V do2 v.vzdalenost = ∞;3 v.predchudce = NULL;4 end5 s.vzdalenost = 0;

// Inicializujeme prioritní frontu Q netrvalých bodů a vložíme do ní

vrcholy grafu

6 Fronta Q = v ∈ V s prioritami v.vzdalenost;

// Inicializujeme prázdnou množinu P, kde budou uložené trvalé

vrcholy

7 Množina P;

8 while Q není prázdná do// Vybereme vrchol s nejnižší prioritou

9 u = Q.pop();// Vybraný vrchol prohlásíme za trvalý a proto jej vložíme do

množiny P

10 P.add(u);11 foreach vrchol v sousedící s u do

// Pokud jsme nalezli kratší cestu do vrcholu v

// c(u, v) značí ohodnocení hrany mezi vrcholy u a v

12 if v.vzdalenost > u.vzdalenost + c(u, v) then13 v.vzdalenost = u.vzdalenost + c(u, v);14 v.predchudce = u;

// Obnovíme správné pořadí ve frontě

15 Q.reorder();16 end17 end18 end

40

lze dostat z vrcholu y ve vzdálenosti od počátečního vrcholu s 5 po hraněs ohodnocením 3 a proto je vzdálenost vrcholu t rovna 5 + 3 = 8).

Asymptotická časová složitost Dijkstrova algoritmu činí O(n2), v případěimplementace s použitím Fibonacciho haldy lze časovou složitost snížit naO(n log n+m) [14].

Floyd-Warshallův algoritmus

Floyd-Warshallův algoritmus (viz algoritmus 3.5) slouží k nalezení nejkrat-ších cest mezi každou dvojicí vrcholů grafu. Předpokladem pro správnoufunkčnost algoritmu je orientovaný graf, ve kterém nesmí být obsaženy zá-porné cykly, avšak na rozdíl od Dijkstrova algoritmu může graf obsahovatzáporně ohodnocené hrany [14].

Algoritmus 3.5: Floyd-Warshallův algoritmus [19]Data: Matice sousednosti D0

Výsledek: Matice Dn obsahující vzdálenosti mezi všemi dvojicemivrcholů grafu

// Proběhne n iterací (n značí počet vrcholů v grafu)

1 for i = 1, . . . , n do// Procházíme matici o rozměru n× n

// u značí číslo řádku matice

2 for u = 1, . . . , n do// v značí číslo sloupce matice

3 for v = 1, . . . , n do// Pokud existuje kratší cesta, tak vložíme její délku do

matice

4 if Du,v > Di,v +Du,i then5 Du,v = Di,v +Du,i;6 end7 end8 end9 end

Na počátku běhu algoritmu očíslujeme n vrcholů čísly 1, . . . , n. Ve čtver-cové matici D řádu n si budeme ukládat vzdálenosti mezi každou dvojicívrcholů grafu. Výpočet matice D neproběhne „naráz“, ale proběhne ite-rativně, kdy v i-té iteraci určíme matici Di. V matici Di hodnota du,v, kdečíslo u značí řádek, číslo v pak sloupec matice Di, značí délku nejkratší cestymezi vrcholy označenými čísly u a v, která prochází vrcholy označenými čísly

41

1, . . . , i. Matice D0 je vstupem algoritmu a značí matici sousednosti obsahu-jící informaci o sousedících vrcholech a ohodnocení hran mezi nimi. Výpočetkončí po n iteracích, kdy výsledná matice Dn obsahuje nejkratší cesty, kterémohou vést přes všech n vrcholů grafu [19].

Pro výpočet prvků du,v maticeDi v i-té iteraci algoritmu použijeme vztah3.2

du,v = min{Di−1u,v , D

i−1u,i +Di−1

i,v } (3.2)

Pokud chceme pomocí Floyd-Warshallova algoritmu zjistit i vrcholy ležícína nejkratší cestě, musíme ještě počítat matici předchůdců. V této maticiuchováváme pro každou dvojici vrcholů u, v nejvyšší číslo iterace i, v níždošlo ke změně matice D na řádku u a ve sloupci v, resp. jinak řečeno sipamatujeme vrchol, který leží na nejkratší cestě mezi vrcholy u, v. Nejkratšícestu pak můžeme z matice předchůdců snadno rekurzivně zrekonstruovat[19].

Asymptotická složitost Floyd-Warshallova algoritmu činí O(n3), kde nznačí počet vrcholů grafu. Floyd-Warshallův algoritmus je v reálných pod-mínkách rychlejší než Dijkstrův algoritmus v případě, kdy bychom Dijkstrůvalgoritmus spouštěli ze všech vrcholů grafu, abychom nalezli nejkratší cestymezi všemi dvojicemi vrcholů grafu [14].

Bellman-Ford-Mooreův algoritmus

Bellman-Ford-Mooreův algoritmus (viz algoritmus 3.6), často uváděn jenjako Bellman-Fordův algoritmus, slouží pro nalezení nejkratší cesty mezidvěma vrcholy v grafu, avšak narozdíl od algoritmů popsaných výše nekladena graf žádné požadavky na acykličnost nebo nezáporné ohodnocení hran.Bellman-Fordův algoritmus je schopen kromě nalezení nejkratší cesty v grafuobsahujícím cykly i záporné ohodnocení hran detekovat cyklus záporné délky[19].

Na počátku algoritmu nastavíme vzdálenost vrcholu s rovnu nule a vzdá-lenost ostatních vrcholů rovnu nekonečnu. Dále v průběhu algoritmu jsouopakovaně prováděny tzv. aktualizace hran („updaty“), které kontrolují ko-rektnost hran a případně opravují nejvyšší odhad vzdálenosti nejkratší cesty.Hranu uv, vedoucí z vrcholu u do vrcholu v nazveme korektní hranou, pokudplatí

dist[v] ≤ dist[v] + c(uv), (3.3)

42

kde dist[v] značí vzdálenost vrcholu v od počátečního vrcholu s a c(uv)značí ohodnocení hrany vedoucí z vrcholu u do vrcholu v, v opačném případěnazveme hranu uv nekorektní hranou [19].

Při update hrany dochází k výpočtu vzdálenosti vrcholu v podle vztahu3.4.

dist[v] = min{dist[v] + c(uv)} (3.4)

Bellman-Fordův algoritmus v n − 1 iteracích updatuje všechny hranygrafu. Počet n − 1 odpovídá počtu hran na nejdelší možné cestě mezi nvrcholy, kde n značí počet vrcholů v grafu. Při implementaci je vhodnézjistit, zdali došlo ke změně vzdálenosti nějakého vrcholu [19]. Pokud byke změně nedošlo, můžeme algoritmus ukončit, neboť ani v dalších krocíchzměna nenastane.

Pokud algoritmus doběhne do konce, tedy proběhne n− 1 iterací, je po-sledním krokem algoritmu kontrola přítomnosti cyklu záporné délky v grafu.Pokud se v grafu nachází cyklus záporné délky, bude některá z hran neko-rektní [19]. Postačí tedy toto otestovat a v případě nalezení nekorektní hranymůžeme konstatovat přítomnost cyklu záporné délky v grafu. V opačném pří-padě, kdy graf neobsahuje žádnou nekorektní hranu, nalezl Bellman-Fordůvalgoritmus nejkratší cestu mezi požadovanou dvojicí vrcholů.

V případě, kdy graf obsahuje cyklus záporné délky, mohli bychom neu-stále „chodit dokola“ po cyklu záporné délky, čímž bychom snižovali délkunejkratší cesty. Proto je nutné na konci algoritmu zkontrolovat korektnostvšech hran. Proto v případě, kdy graf obsahuje cyklus záporné délky, nej-kratší cesta v grafu neexistuje.

Asymptotická časová složitost Bellman-Fordova algoritmu činí O(nm),kde m značí počet vrcholů a n počet hran [14].

3.2.5 Řešení úlohyPro řešení úlohy byl zvolen Dijkstrův algoritmus vzhledem ke své příznivéčasové asymptotické složitosti O(n2). Dalším zvažovaným kandidátem bylFloyd-Warshallův algoritmus, který by musel být v každém testovacím pří-padu spuštěn pouze jednou, neboť určí nejkratší cestu mezi všemi dvojicemivrcholů v grafu, ovšem za cenu vyšší asymptotické složitosti O(n3). Jako pri-oritní fronta byla zvolena generická kolekce PriorityQueue ze standardníknihovny java.util programovacího jazyka Java. Graf byl reprezentovánspojovým seznamem, ohodnocení hran nebyla s ohledem na zadání úlohyukládána (u všech hran obsažených v grafu bylo předpokládáno ohodnocenírovno jedné).

43

Algoritmus 3.6: Bellman-Fordův algoritmus [19]Data: Graf G = (V, H, c), kde V jsou vrcholy, H hrany grafu, c

představuje ohodnocení hran; počáteční vrchol sVýsledek: Pro každý vrchol grafu vzdálenost od vrcholu s a



1 foreach vrchol v ∈ V do2 v.vzdalenost = ∞;3 v.predchudce = NULL;4 end5 s.vzdalenost = 0;

// Opakované updaty hran

6 for i = 1, . . . , n-1 do7 foreach hrana e ∈ H do8 u = e.pocatek; // u je počáteční vrchol hrany

9 v = e.konec; // v je koncový vrchol hrany

10 if v.vzdalenost > u.vzdalenost + c(e) then11 v.vzdalenost = u.vzdalenost + c(e);12 v.predchudce = u;13 end14 end15 end

// Kontrola přítomnosti cyklů záporné délky v grafu

16 foreach hrana e ∈ H do// u je počáteční vrchol hrany

17 u = e.pocatek;// v je koncový vrchol hrany

18 v = e.konec;

19 if v.vzdalenost > u.vzdalenost + c(e) then// Graf obsahuje cyklus záporné délky

20 exit;21 end22 end

44


Obrázek 3.7: Zpráva o validaci úlohy All Roads Lead Where?

45

3.3 Expensive Subway

3.3.1 Originální zadání úlohy11710 - Expensive Subway

Peter lives in Expensive City, one of the most expensive cities in theworld. Peter has not got enough money to buy a car, and the buses inExpensive City are pretty bad, so he uses the subway to go to work. Upto now, the subway was very cheap: you could travel anywhere withjust one $2 ticket. Last month, the managers decided that it was toocheap so they invented the EFS (Expensive Fare System). With thissystem, users can only buy monthly tickets between adjacent stations,which allows them to move between these stations any number oftimes. The price of the monthly ticket varies between stations, so thedecision of which tickets to buy must be taken carefully.

With the previous subway plan, the cheapest way to travel from Pi-cadilly to Victoria and Queensway was to buy the monthly ticketPicadilly-Victoria and Queensway-Victoria, for a total cost of $12.Peter is a salesperson, so he needs to be able to travel to any part ofthe city. He wants to spend as little money as possible, and here iswhere you come into the picture. He has hired you to write a programthat, given the list of stations, the fares of the monthly tickets be-tween pairs of stations and the station nearest Peter’s home, returnsthe minimum amount of money Peter has to spend in order to travelto any other station. This program also has to return value if it is notpossible to go from Peter’s home station to all the rest, because in thiscase Peter will begin to consider using buses.InputThe input consists of several test cases. A test case begins with a linecontaining two integers: 1 ≤ s ≤ 400 (the number of stations) and0 ≤ c ≤ 79800 (the number of connections) separated by a single

46

space. This is followed by s lines, each one containing the name of asubway station. These names will be strings of characters (uppercaseor lowercase) without punctuation marks or whitespace characters,and with a maximum length of 10 characters. After the names ofthe stations there will be c lines showing the connections betweenstations. A connection allows people to travel from one station to theother in both directions. Each connection is represented as two stringsindicating the names of the stations and a positive integer indicatingthe cost of the monthly ticket, all of which are separated by singlespaces. All names of stations appearing in the connections will havepreviously appeared in the list of s stations. The connections will allbe different, and there will not be any connection from a station toitself. The test case will end with a line containing the name of thestation from which Peter needs to travel to all the other stations.The input finishes with the phantom test case „0 0“, which must notbe processed.OutputFor every test case, the output will be a line containing an integer, theminimum monthly price that Peter has pay to travel from the givenstation to all the others, or Impossible if it is not possible to travelto all the stations.Sample Input3 3 PicadillyVictoriaQueenswayPicadilly Victoria 2Queensway Victoria 10Queensway Picadilly 20Picadilly4 2PicadillyVictoriaQueenswayTemplePicadilly Victoria 2Temple Queensway 100Temple0 0

47

Sample Output12Impossible

Originální zadání úlohy je dostupné na adrese https://uva.onlinejudge.org/external/117/11710.pdf [cit. 2016/11/12]. Obrázek byl převzat z ori-ginálního zadání.

3.3.2 Česká verze zadání úlohy11710 - Drahé metro

Petr bydlí v Expensive City, v jednom z nejdražších měst na světě. Petrnemá dostatek peněz, aby si koupil automobil, autobusy jsou v Ex-pensive City poměrně špatné, a proto využívá služeb metra pro cestudo práce. Dosud bylo metro velmi levné - každý mohl cestovat kamko-liv se mu zachtělo s levnou jízdenkou za dva dolary. Minulý měsíc semanažeři rozhodli, že tato jízdenka je levná až příliš a vymysleli sys-tém EFS (Drahý systém jízdného, Expensive Fare System). Uživatelésystému EFS si mohou zakoupit pouze jízdenky mezi sousedními sta-nicemi metra. Jízdenky dovolují uživatelům mezi příslušnými dvěmastanicemi cestovat bez omezení. Cena měsíční jízdenky se různí podlestanic, mezi kterými platí, proto Petr musí vhodnou jízdenku vybíratpečlivě.

V novém systému EFS je pro Petra nejlevnější si zakoupit jízdenkymezi stanicemi Picadilly-Victoria a Victoria-Queensway v celkové ceně12 dolarů, ačkoliv existuje přímé spojení mezi stanicemi Picadilly aQueensway, jízdenka mezi těmito dvěma stanicemi stojí 20 dolarů.Petr je obchodník a proto se potřebuje dostat do všech městskýchčástí. Za jízdenky chce utratit co nejméně peněz a zde přichází řadana vás. Petr vás najal, abyste pro něj napsali program, který po zadání

48



seznamu stanic, cen jízdného mezi dvojicemi stanic a stanice nejblížePetrova domova určí minimální cenu jízdenek tak, aby Petr utratilco nejméně peněz a zároveň mohl cestovat do všech stanic metra.Program musí v případě, kdy se nelze metrem dostat do všech stanictoto oznámit a Petr v tomto případě uváží cestování autobusem.VstupVstup se skládá z několika testovacích případů. Testovací případ za-číná řádkou obsahující dvě celá čísla 1 ≤ s ≤ 400 (počet stanic metra)a 0 ≤ c ≤ 79800 (počet spojení) oddělená mezerou. Následuje s řádek,z nichž každá obsahuje název jedné ze stanic metra. Názvy stanic jsouřetězce (mohou obsahovat velká i malá písmena) bez interpunkce amezer o maximální možné délce 10 znaků. Po části vstupu s názvystanic je uvedeno c řádek s jednotlivými spoji mezi stanicemi. Každýumožňuje cestování pasažérů v obou směrech. Každé spojení je re-prezentováno dvěma řetězci značícími stanice, mezi nimiž leží danéspojení, a cenou měsíční jízdenky, všechny údaje na řádce jsou od-děleny mezerou. Všechna jména stanic, která se objeví v části popisuspojení, již byla uvedena v seznamu stanic. Žádné spojení nebude uve-deno dvakrát, a rovněž nebude uvedeno žádné spojení stanice se sebousamou. Testovací případ končí řádkou s názvem stanice, ze které Petrpotřebuje cestovat do všech ostatních stanic.Vstup končí dvěma nulami „0 0“, které nesmějí být zpracovány.VýstupPro každý testovací případ bude výstupem řádka obsahující přirozenéčíslo značící minimální cenu všech jízdenek, které si Petr musí koupit,aby se mohl dopravit do libovolné stanice metra. Pokud by toto nebylomožné, bude výstupem Impossible.Vzorový vstup3 3PicadillyVictoriaQueenswayPicadilly Victoria 2Queensway Victoria 10Queensway Picadilly 20Picadilly4 2PicadillyVictoria

49

QueenswayTemplePicadilly Victoria 2Temple Queensway 100Temple0 0Vzorový výstup12Impossible

Obrázek byl převzat z originálního zadání, které je dostupné na adresehttps://uva.onlinejudge.org/external/117/11710.pdf [cit. 2016/11/12].

3.3.3 Analýza úlohyZe zadání úlohy je zřejmé, že se jedná o grafovou úlohu. Prvním krokempři řešení této úlohy je výběr vhodných datových struktur pro reprezentacigrafu. Struktury vhodné pro reprezentaci grafu byly popsány v kapitole 3.2.3.

Naším stěžejním úkolem je vybrat podgraf ze zadaného grafu tak, abysoučet ohodnocení hran v podgrafu byl co nejmenší, a zároveň musí býtv podgrafu obsaženy všechny vrcholy původního grafu. Takový podgraf na-zýváme minimální kostra grafu (viz obrázek 3.8). Z obrázku jsou zřejmévlastnosti minimální kostry grafu - neobsahuje cykly, obsahuje všechny vr-choly původního grafu a součet ohodnocení obsažených hran je nejmenšímožný.

Obrázek 3.8: Minimální kostra grafuZdroj: https://www.cs.indiana.edu/~achauhan/Teaching/B403/

LectureNotes/images/09-mst-intro.jpg [cit. 2016/11/12]

50


https://www.cs.indiana.edu/~achauhan/Teaching/B403/LectureNotes/images/09-mst-intro.jpg

https://www.cs.indiana.edu/~achauhan/Teaching/B403/LectureNotes/images/09-mst-intro.jpg

V minimální kostře grafu pak sečteme ohodnocení všech hran, čímž zjis-tíme minimální cenu jízdného, kterou musí Petr zaplatit za jízdenky, abymohl cestovat mezi všemi stanicemi metra.

3.3.4 Algoritmy vhodné pro řešení úlohyStěžejní částí řešení úlohy je implementace algoritmu pro nalezení minimálníkostry grafu. Ze zadání víme pouze, že zadaný graf bude mít kladné ohod-nocení hran. Zadání nám negarantuje žádné další speciální vlastnosti grafu,a to včetně souvislosti (souvislým grafem rozumíme graf, v němž existujecesta pro každou dvojici vrcholů v grafu). V případě nesouvislého grafu byvýsledkem řešení úlohy bylo, že nelze určit minimální cenu jízdenek tak, abybyly pokryty všechny stanice metra.

Kruskalův algoritmus

Kruskalův algoritmus (viz algoritmus 3.7) lze použít pro nalezení minimálníkostry grafu [19]. Algoritmus nejprve seřadí hrany grafu dle jejich ohod-nocení. Následně tyto hrany zkouší přidat do kostry tak, aby po přidáníhrany nevznikl v dosavadní kostře cyklus. Pokud cyklus po přidání hrany dokostry nevznikne, je přidaná hrana součástí minimální kostry grafu. V opač-ném případě, kdy by po přidání hrany do kostry vznikl cyklus a tím bydošlo k porušení vlastností kostry, hrana není přidána. Při přidávání hranynemusíme testovat přítomnost cyklu, postačí zjistit, zdali přidávaná hranaspojuje různé komponenty souvislosti [19].

Průběh algoritmu je zobrazen na obrázku 3.9. Na počátku má algorit-mus k dispozice hrany grafu, pro který hledáme minimální kostru. V prvnímkroku algoritmus seřadí hrany podle jejich ohodnocení. Následuje postupnépřidávání hran do kostry grafu. Nejprve algoritmus zkusí přidat hranu mezivrcholy A a B. Protože tato hrana spojuje dvě komponenty souvislosti, jepřidána do výsledné minimální kostry grafu. Analogicky algoritmus postu-puje pro hrany mezi vrcholy D a F , C a E, C a D. Následně algoritmus zkusído kostry vložit hranu mezi vrcholy E a F , ovšem tato hrana, podobně jakonásledující testovaná hrana mezi vrcholy D a E, nespojuje dvě komponentysouvislosti, a proto není tato hrana do výsledné minimální kostry přidána.Poslední testovanou hranou je hrana mezi vrcholy A a C, která je přidánado kostry. V tomto okamžiku je výsledná kostra grafu složena jen z jednékomponenty souvislosti a proto můžeme algoritmus ukončit.

51

Algoritmus 3.7: Kruskalův algoritmus [16]Data: Graf G = (V, H, c), kde V jsou vrcholy, H hrany grafu, c

představuje ohodnocení hrany; počáteční vrchol sVýsledek: A obsahující hrany minimální kostry grafu G

// Na počátku prázdná množina A obsahující hrany v minimální kostře

1 Množina A = ∅;// Pro každý vrchol vytvoříme samotnou komponentu souvislosti

2 foreach vrchol v ∈ V do3 makeSet(v);4 end

// Seřadíme hrany vzestupně dle jejich ohodnocení

5 sort(H);

6 foreach hrana h ∈ H do// Vrcholy u a v jsou vrcholy na koncích hrany h

7 vrchol u = h.pocatek;8 vrchol v = h.konec;

// Pokud jsou vrcholy u a v v různých komponentách souvislosti

9 if FIND(u) 6= FIND(v) then// Hranu h přidáme do fronty

10 A.add(h);// Sjednotíme komponenty, v nichž ležely vrcholy u a v

11 UNION(u, v);12 end13 end

52

Obrázek 3.9: Hledání minimální kostry grafu pomocí Kruskalova algoritmuZdroj: http://cs.lmu.edu/~ray/images/kruskal.png [cit.

2016/11/13]

V průběhu algoritmu testujeme hrany, zdali s nimi incidentní vrcholypatří do jedné či dvou komponent souvislosti. Tento problém se nazýváUnion&Find problém. Union&Find problém je realizován dvěma operacemi,kterými jsou UNION, která sjednocuje dvě komponenty souvislosti, a FIND,která vrátí reprezentanta komponenty souvislosti pro daný vrchol grafu. Re-prezentanta vybereme pro každou komponentu souvislosti pouze jednoho,tohoto reprezentanta sdílejí všechny vrcholy dané komponenty souvislosti[19].

Problém Union&Find může být řešen několika způsoby. Nejjednoduš-ším způsobem je řešení pomocí pole. Nejdříve očíslujeme vrcholy grafu čísly1, . . . , n. V poli R[1 . . . n] budeme mít uloženo číslo reprezentanta kompo-nenty souvislosti pro každý vrchol grafu. Operace FIND pouze vrátí pro vr-chol i hodnotu R[i], z čehož vyplývá, že její časová asymptotická složitostje rovna O(1) [19]. Operace UNION nejdříve najde pro dva zadané vrcholyi a j reprezentanty a = R[i] a b = R[j]. Pokud nejsou získaní reprezentantia, b shodní, operace UNION v poli přepíše všechny výskyty reprezentantaa na reprezentanta b, což značí sjednocení daných komponent souvislostí.Asymptotická časová složitost operace UNION činí O(n) [19].

Problém Union&Find může být implementován i dalšími způsoby, kdymůžeme získat lepší časovou složitost operace UNION, ovšem za cenu zhor-šení složitosti operace FIND. Asymptotická časová složitost obou operací pakv případě použití implementace nazývané union by rank činí O(log n) [19].

Časová asymptotická složitost Kruskalova algoritmu činí O(m log n) přiimplementace problému Union&Find nazývané union by rank [19].

53

http://cs.lmu.edu/~ray/images/kruskal.png

Prim-Jarnikův algoritmus

Prim-Jarnikův algoritmus (viz algoritmus 3.8) si při svém běhu udržujepouze jednu komponentu souvislosti, kterou postupně rozšiřuje. Do vytvá-řené komponenty, která na konci algoritmu odpovídá minimální kostře grafu,jsou postupně přidávány hrany s nejmenším ohodnocením, které vedou z tétokomponenty do jiné [19]. Tímto se konstruovaná minimální kostra postupně„rozrůstá“ do doby, kdy jsou v konstruované minimální kostře obsaženyvšechny vrcholy zadaného grafu, pro který hledáme minimální kostru (vizobrázek 3.10).

V průběhu algoritmu si pamatujeme pro každý vrchol v, který zatím neníobsažen v množině hran T tvořících minimální kostru, ohodnocení hrany d[v]s nejmenším ohodnocením a odkud tato hrana vede odkud[v]. Hrana, kterousi pamatujeme, musí vést „ven“ z komponenty souvislosti, tedy musí býtincidentní s některým z vrcholů tvořících konstruovanou minimální kostrugrafu. Nyní postačí projít hodnoty d[v] všech vrcholů grafu, které dosudnejsou součástí konstruované minimální kostry a z těchto hodnot vybratnejnižší hodnotu a k ní příslušnou hranu, kterou přidáme do konstruovanéminimální kostry grafu. Po každém přidání vrcholu do konstruované mi-nimální kostry je nutné zkontrolovat u všech vrcholů, které dosud nejsouobsaženy v minimální kostře grafu, zdali si pamatujeme správnou hranu,tedy hranu s nejnižším ohodnocením vedoucí do některého z vrcholů, kteréjsou dosud obsaženy v konstruované kostře grafu [19].

Obrázek 3.10: Hledání minimální kostry grafu Prim-Jarnikovýmalgoritmem

Zdroj: http://cs.lmu.edu/~ray/images/prim.png [cit. 2016/11/13]

54

http://cs.lmu.edu/~ray/images/prim.png

Algoritmus 3.8: Prim-Jarnikův algoritmus [19]Data: Graf G = (V, H), kde V jsou vrcholy, H hrany grafuVýsledek: Množina A obsahující hrany minimální kostry grafu G

// Na počátku prázdná množina A obsahující hrany v minimální kostře

1 Množina A = ∅;// Zvolíme startovní bod r a nastavíme pole d[v] obsahující

ohodnocení hran vedoucích „ven“ z komponenty souvislosti pro

všechny vrcholy

2 d[r] = 0;3 odkud[r] = NULL;4 foreach Vrchol v ∈ V \{r} do5 d[v] = ∞;6 odkud[v] = NULL;7 end

// Inicializujeme prioritní frontu vrcholů grafu

8 Fronta Q = v ∈ V s prioritami d[v];

// Hrany postupně přidáváme do kostry

9 while Q není prázdná do10 Vrchol v = Q.pop();11 A.add(hrana(v, odkud[v]));12 end

// Zkontrolujeme správnost d[v] a odkud[v]

13 foreach Hrana h ∈ H do// Vrcholy u a v jsou vrcholy na koncích hrany h

14 Vrchol u = h.pocatek;15 Vrchol v = h.konec;16 if d[v] > h.ohodnoceni then17 d[v] = h.ohodnoceni;18 odkud[v] = u;19 end20 end

55

Asymptotická časová složitost Prim-Jarnikova algoritmu činí v případěrealizace prioritní fronty polem O(n2 + m), při realizaci prioritní fronty bi-nární haldou pak časová složitost činí O(n+m) log n.

Borůvkův algoritmus

Borůvkův algoritmus (viz algoritmus 3.9) je dalším zástupcem algoritmů prohledání minimální kostry grafu. Borůvkův algoritmus vyžaduje, aby mini-mální kostra grafu byla určena jednoznačně [19]. Jednoznačné určení mini-mální kostry v grafu je zaručeno v grafech, kde mají všechny hrany vzájemněrůzná ohodnocení [19]. Borůvkův algoritmus lze dobře paralelizovat [19].

Algoritmus 3.9: Borůvkův algoritmus [19]Data: Graf G = (V, H), kde V jsou vrcholy, H hrany grafuVýsledek: Graf T představující minimální kostru grafu G

1 Graf T = (V, ∅);2 while graf T není souvislý do

// Pomocný graf Gpom

3 Graf GPom = (reprezentanti komponent souvislosti T, ∅);4 foreach hrana h ∈ H do

/* u je reprezentant komponenty, v níž leží vrchol na začátku

hrany; podobně v */

5 Vrchol u = reprezentant(h.pocatek);6 Vrchol v = reprezentant(h.konec);7 GPom.pridejHranu(u, v);

// Odstraníme smyčky v grafu Gpom

8 GPom.odstranSmycky();

/* Odstraníme násobné hrany, ponecháme hranu s nejnižším

ohodnocením, kterou přidáme do kostry grafu T */

9 foreach dvojice vrcholů [uv] ∈ GPom do10 Mnozina hrany = najdiVsechnyHrany([uv]);11 Hrana min = urciNejlevnejsiHranu(hrany);12 T .pridejHranu(min);13 end14 end15 end

Na počátku běhu algoritmu máme k dispozici graf obsahující vrcholya ohodnocené hrany (viz obrázek 3.11). Jak již bylo řečeno, pro správnou

56

funkci algoritmu je nutné, aby minimální kostra grafu byla určena jed-noznačně, tedy aby neexistovali dvě různé minimální kostry se shodnýmsoučtem ohodnocení hran obsažených v daných minimálních kostrách. Po-kud není zaručena jednoznačnost kostry, lze použít Kruskalův nebo Prim-Jarnikův algoritmus, které byly popsány výše.

Algoritmus v první iteraci (viz obrázek 3.12) vybere pro každý vrcholhranu s nejnižším ohodnocením, která je s tímto vrcholem incidentní. Provrcholy A a D jde o hranu AD, pro vrchol B byla vybrána hrana AB, provrcholy C a E hrana CE, pro vrchol F hrana DF a pro vrchol G hrana EG.Tímto v grafu vznikly dvě komponenty souvislosti, z nichž první je tvořenavrcholy {A,B,D, F}, druhá komponenta souvislosti je pak tvořena vrcholy{C,E,G}. Ve druhé iteraci algoritmu (viz obrázek 3.13) je pak vybránahrana komponenty {A,B,D, F} s nejnižším ohodnocením, která vede venz této komponenty. Protože získaná minimální kostra nyní pokrývá všechnyvrcholy grafu, můžeme algoritmus ukončit.

Obrázek 3.11: Počáteční stav při běhu Borůvkova algoritmuZdroj:

https://en.wikipedia.org/wiki/Borůvka’s_algorithm#/media/File:Borůvka_Algorithm_1.svg [cit. 2016/11/14]

Při implementaci pro každou komponentu souvislosti zvolíme reprezen-tanta této komponenty a pro každou komponentu souvislosti hledáme hranus nejnižším ohodnocením, která vede z této komponenty „ven“. V každéiteraci si vytvoříme pomocný graf Gpom, jehož vrcholy jsou jednotlivé kom-ponenty souvislosti. Do pomocného grafu přidáváme všechny hrany z pů-vodního grafu (vrcholy původního grafu jsou nahrazeny reprezentanty kom-ponent souvislosti). Při přidávání hran do pomocného grafu mohou vznikatsmyčky, které rovnou zahazujeme, a násobné hrany mezi vrcholy pomoc-ného grafu, z nichž ponecháme jen tu s nejnižším ohodnocením. Před dalšíiterací Borůvkova algoritmu musíme sjednotit nyní propojené komponenty

57

https://en.wikipedia.org/wiki/Bor�vka's_algorithm#/media/File:Bor�vka_Algorithm_1.svg


souvislosti. Protože sjednocujeme více komponent souvislosti, není vhodnépostupně sjednocovat jednotlivé dvojice komponent souvislosti, neboť bysjednocování tímto způsobem mohlo trvat příliš dlouho [19]. Je vhodnějšísjednotit komponenty souvislosti tím, že pomocí prohledávání do hloubky(Depth-first search, DFS) projdeme všechny vrcholy ve sjednocovaných kom-ponentách souvislosti (které jsou již nyní propojené) a všem nalezeným vr-cholům nastavíme stejného reprezentanta.

Asymptotická časová složitost Borůvkova algoritmu činí O(m log n), kdem značí počet hran a n počet vrcholů grafu.

Obrázek 3.12: První iterace běhu Borůvkova algoritmuZdroj:


Obrázek 3.13: Druhá (poslední) iterace běhu Borůvkova algoritmuZdroj:


58





3.3.5 Řešení úlohyPři řešení úlohy byl použit Kruskalův algoritmus vzhledem k příznivé hod-notě asymptotické časové složitosti, která činí O(m log n). Při implementacitéto úlohy není nutné ukládat celý graf, postačí si jen uložit hrany. Namístonázvů vrcholů si v hranách pamatujeme jejich číselná označení. Čísla vr-cholů pak můžeme přímo používat v části implementace Union&Find, anižbychom si museli pamatovat názvy vrcholů grafu.

Při implementaci problému Union&Find bylo použito mírně vylepšenéřešení, kdy si u operace UNION pamatujeme ještě vrcholy ležící v dané kom-ponentě a jejich počet. Poté přepisujeme reprezentanty jen u vrcholu ležícív komponentě s menším počtem vrcholů. Tímto vylepšením získáme amorti-zovanou asymptotickou časovou složitost operace UNION rovnu O(log n) [19].


Obrázek 3.14: Zpráva o validaci úlohy Expensive Subway

59

3.4 Where’s Waldorf?

3.4.1 Originální zadání úlohy10010 - Where’s Waldorf?

Given a m by n grid of letters, (1 ≤ m,n ≤ 50), and a list of words,find the location in the grid at which the word can be found.A word matches a straight, uninterrupted line of letters in the grid.A word can match the letters in the grid regardless of case (i.e. upperand lower case letters are to be treated as the same). The matchingcan be done in any of the eight directions either horizontally, verticallyor diagonally through the grid.InputThe input begins with a single positive integer on a line byitself indicating the number of the cases following, each ofthem as described below. This line is followed by a blankline, and there is also a blank line between two consecutiveinputs.The input begins with a pair of integers, m followed by n, 1 ≤ m,n ≤50 in decimal notation on a single line. The next m lines contain n

letters each; this is the grid of letters in which the words of the listmust be found. The letters in the grid may be in upper or lower case.Following the grid of letters, another integer k appears on a line byitself (1 ≤ k ≤ 20). The next k lines of input contain the list of wordsto search for, one word per line. These words may contain upper andlower case letters only (no spaces, hyphens or other non-alphabeticcharacters).OutputFor each test case, the output must follow the descriptionbelow. The outputs of two consecutive cases will be separatedby a blank line.For each word in the word list, a pair of integers representing thelocation of the corresponding word in the grid must be output. Theintegers must be separated by a single space. The first integer is theline in the grid where the first letter of the given word can be found (1represents the topmost line in the grid, and m represents the bottom-most line). The second integer is the column in the grid where the firstletter of the given word can be found (1 represents the leftmost columnin the grid, and n represents the rightmost column in the grid). If a

60

word can be found more than once in the grid, then the location whichis output should correspond to the uppermost occurence of the word(i.e. the occurence which places the first letter of the word closest tothe top of the grid). If two or more words are uppermost, the outputshould correspond to the leftmost of these occurences. All words canbe found at least once in the grid.Sample Input1

8 11abcDEFGhigghEbkWalDorkFtyAwaldORmFtsimrLqsrcbyoArBeDeyvKlcbqwikomkstrEBGadhrbyUiqlxcnBjf4WaldorfBambiBettyDagbertSample Output2 52 31 27 8

Originální zadání úlohy je dostupné na adrese https://uva.onlinejudge.org/external/100/10010.pdf [cit. 2017/03/05].

3.4.2 Česká verze zadání úlohy10010 - Kde je Waldorf?

Vaším úkolem je najít v zadané mřížce písmen o rozměrech m × n

pozice, na kterých lze najít hledaná slova.Slova musí být ve mřížce nalezena jako nepřerušená posloupnost pís-men s dodrženým pořadím písmen, u jednotlivých písmen nezáleží na

61



jejich velikosti (jednotlivá písmena slov tedy mohou být malá i velká).Hledaná slova se v mřížce mohou nacházet v horizontálně, vertikálněi diagonálně ve všech osmi směrech.VstupVstupní data začínají celým kladným číslem na jedné řádce,které udává celkový počet testovaných případů. Tato řádka jenásledována prázdnou řádkou. Dále se prázdná řádka nacházímezi dvěma po sobě jdoucími případy.Každý testovaný případ začíná dvojicí celých čísel uvedených v de-sítkové soustavě, z nichž první je číslo m následované číslem n (1 ≤m,n ≤ 50), na samostatné řádce. Každá z následujících m řádek ob-sahuje n písmen, která představují jednotlivé řádky mřížky písmen,v nichž budou hledána zadaná slova. Písmena mřížky mohou být velkái malá. Po řádkách, které popisují mřížku písmen, následuje řádka ob-sahující pouze jedno celé číslo k (1 ≤ k ≤ 20), které udává početřádek s hledanými slovy, která následují na dalších k řádkách. Hledanáslova mohou obsahovat jen malá a velká písmena, nebudou obsahovatmezery, pomlčky a jiné nealfabetické znaky.VýstupPro každý testovací případ musí výstup přesně odpovídatníže uvedené specifikaci výstupu. Výstupní data dvou po sobějdoucích testovacích případů budou oddělena prázdnou řád-kou.Pro každé hledané slovo vypište dvojici celých čísel oddělených meze-rou, která představuje pozici hledaného slova v mřížce písmen. Prvníz čísel udává řádku mřížky, ve které se nachází první písmeno hle-daného slova (první horní řádka mřížky je označena číslem 1, číslom naopak označuje spodní řádku mřížky). Druhé číslo udává sloupecmřížky, ve kterém se nachází první písmeno hledaného slova (sloupecmřížky nacházející se nejvíce vlevo je označen číslem 1, číslo n naopakoznačuje sloupec mřížky nejvíce vpravo).Pokud se slovo nachází v mřížce vícekrát, je očekávaným výsledkemvýskyt slova v co nejvyšším řádku mřížky. Pokud se první písmenoslova nachází vícekrát ve stejném řádku, potom je požadovaným vý-sledkem výskyt slova ve sloupci co nejvíce vlevo mřížky. Všechna slovase v mřížce nacházejí alespoň jednou.Vzorový vstup1

62

8 11abcDEFGhigghEbkWalDorkFtyAwaldORmFtsimrLqsrcbyoArBeDeyvKlcbqwikomkstrEBGadhrbyUiqlxcnBjf4WaldorfBambiBettyDagbertVzorový výstup2 52 31 27 8

3.4.3 Analýza úlohyZe zadání je zřejmé, že úloha je jednou ze známých luštitelských her, v tomtopřípadě jde o klasickou osmisměrku. Stěžejním řešeným úkolem v rámciúlohy je vyhledávání podřetězce v řetězci. Vstupní data úlohy mají formudvourozměrného pole znaků, v němž hledáme zadané řetězce v osmi směrech(horizontálně zleva doprava i zprava doleva, vertikálně shora dolů i zdola na-horu, diagonálně pak ve čtyřech směrech - doleva a nahoru, doleva a dolů,doprava a nahoru, doprava a dolů).

Ve chvíli, kdy nalezneme hledané slovo, vypíšeme informaci o pozici, nakteré se dané slovo nachází. Zde je třeba dát pozor na správné číslovánířádků i sloupců, které dle zadání úlohy začíná číslem jedna.

3.4.4 Algoritmy vhodné pro řešení úlohyZnámé algoritmy pro vyhledávání podřetězců v řetězci jsou určené pro vy-hledávání podřetězců v řetězci (tedy v jednorozměrném poli znaků), ovšemv případě této úlohy je nutné podřetězce hledat v dvourozměrném poli znakůa ve více směrech.

63

V případě této úlohy lze snadno získat řetězce jakožto jednorozměrnápole znaků, v nichž budeme hledat hledané podřetězce, kdy postačí hledatslova nejprve v jednotlivých řádcích, poté v jednotlivých sloupcích a nakonecv řetězcích uložených v mřížce diagonálně. Abychom hledali podřetězce vevšech osmi směrech, je nutné, v případě, kdy jsme dosud nenalezli hledanýpodřetězec, provést reverzi řetězců, v nichž zadané podřetězce hledáme, tedynapř. v případě řádek jednou slovo hledáme zleva doprava a po reverzi jejhledáme zprava doleva, analogicky pak postupujeme i pro sloupce a diago-nály.

Triviální algoritmus

Triviální algoritmus (viz algoritmus 3.10), jak již jeho název napovídá, jenejjednodušším algoritmem pro vyhledávání podřetězců v řetězci.

Algoritmus 3.10: Triviální algoritmus [15]Data: Prohledávaný řetězec T , hledaný podřetězec PVýsledek: Pozice x, na které začíná v prohledávaném řetězci T

hledaný podřetězec P

1 n = T.délka;2 m = P.délka;

// Hledáme na každé pozici v prohledávaném řetězci

3 s = 0;4 for s ≤ n−m do5 if P [0 . . .m] == T [s . . . (s +m− 1)] then

// Podřetězec nalezen na pozici s

6 print Podřetězec se v řetězci nachází na pozici s;7 end8 s = s + 1;9 end

Princip algoritmu je velmi jednoduchý (viz obrázek 3.15). Algoritmuspro každou pozici prohledávaného řetězce testuje, zdali se na této pozicinevyskytuje hledaný podřetězec [15].

Například pro prohledávaný řetězec acaabc, v němž hledáme podřetězecaab (viz obrázek 3.15), nejprve otestujeme, zdali se hledaný podřetězec nena-chází hned na první pozici (s = 0) prohledávaného řetězce. Protože na prvnípozici se hledaný podřetězec nenachází, přesuneme se o jednu pozici doprava,kde se hledaný podřetězec opět nenachází. V další iteraci algoritmus se opětposuneme o jednu pozici doprava (tedy na třetí pozici), kde se již hledaný

64

podřetězec nachází. Dle našich požadavků můžeme v algoritmu pokračovatdále, abychom našli všechna umístění hledaného podřetězce v řetězci, nebov případě, kdy je naším cílem nalezení jen jednoho výskytu podřetězce v ře-tězci, můžeme algoritmus ukončit.

Obrázek 3.15: Průběh triviálního algoritmu pro hledání podřetězcův řetězci pro podřetězec aab hledaný v řetězci acaabc

Zdroj: převzato z [15].

Asymptotická časová složitost triviálního algoritmu pro vyhledávání pod-řetězců v řetězci činí O((n−m+1)m), kde n je délka prohledávaného řetězcea m je délka hledaného podřetězce [15].

Rabin-Karpův algoritmus

Rabin-Karpův algoritmus (viz algoritmus 3.11) slouží pro vyhledávání pod-řetězců v zadaném řetězci a je vhodný především pro případy, kdy hledámevíce podřetězců v jednom řetězci. Algoritmus pracuje ve dvou krocích, prv-ním z nich je předzpracování, které probíhá s asymptotickou časovou složi-tostí O(m) [15], kde m označuje délku hledaného podřetězce. Druhou částípak je vlastní vyhledávání podřetězce, jehož asymptotická časová složitostv nejhorším případě činí O((n−m+1)m), kde n je délka prohledávaného ře-tězce [15], tedy asymptotická časová složitost je v nejhorším případě shodnás asymptotickou časovou složitostí triviálního algoritmu, který byl popsánvýše v kapitole 3.4.4. Asymptotická časová složitost Rabin-Karpova algo-ritmu v průměrném případě dosahuje příznivějších hodnot [15].

Algoritmus pracuje obdobně jako triviální algoritmus, ovšem namístoporovnávání znaků hledaného podřetězce a části prohledávaného řetězce po-rovnává otisky (hashe) hledaného podřetězce a prohledávaného řetězce. Po-kud se otisky části prohledávaného řetězce a hledaného podřetězce shodují,neznamená to ještě, že jsme nalezli hledaný podřetězec, neboť dva rozdílnéřetězce mohou mít shodný otisk. Proto je při shodě otisků nutné porov-nat jednotlivé znaky podřetězce a části řetězce, na které testujeme výskythledaného podřetězce.

65

Algoritmus 3.11: Rabin-Karpův algoritmus (převzato z [15])Data: Prohledávaný řetězec T , hledaný podřetězec P , základ d

(základ se obvykle volí jako počet znaků abecedy hledanéhopodřetězce a prohledávaného řetězce), prvočíslo q prorozptylovou (hashovací) funkci

Výsledek: Pozice x, na které začíná v prohledávaném řetězci Thledaný podřetězec P

1 n = T.délka;2 m = P.délka;3 h = dm−1 mod q;4 p = 0;5 t0 = 0;

// Předzpracování dat - výpočet otisků pro hledané podřetězce

6 i = 0;7 for i < m do8 p = (dp+ P [i] mod q);9 t0 = (dt0 + P [i] mod q);

10 end// Hledáme na každé pozici v prohledávaném řetězci

11 s = 0;12 for s < n−m do13 if p == ts then14 if P [0 . . .m] == T [s . . . (s +m− 1)] then

// Podřetězec nalezen na pozici s

15 print Podřetězec se v řetězci nachází na pozici s16 end17 end18 ;19 if s < n - m then

/* Přepočítáme otisk pro další testovaný úsek prohledávaného

řetězce */

20 ts+1 = (d(ts − T [s]h) + T [s+m]) mod q;21 end22 s = s + 1;23 end

66

Obrázek 3.16: Průběh Rabin-Karpova algoritmu při vyhledávání řetězce31415 v řetězci 2359023141526739921

Zdroj: převzato z [15].

Princip algoritmu lze demonstrovat na obrázku 3.16, kde v dolní části ob-rázku jsou znázorněny počítané otisky pro jednotlivé části prohledávanéhořetězce. V horní části je pak uveden prohledávaný řetězec 235902314152673-9921. Hledaným podřetězcem je v tomto konkrétním případě 31415. Algorit-mus postupuje od první pozice prohledávaného řetězce a zkontroluje shoduna otisk pěti následujících znaků s otiskem hledaného podřetězce. Pokud seotisky neshodují, algoritmus postupuje o jednu pozici vpravo a opět zkon-troluje shodu otisku části prohledávaného řetězce a hledaného podřetězce.Pokud se otisky shodují, algoritmus zkontroluje shodu části prohledávanéhořetězce s hledaným podřetězcem znak po znaku stejně jako triviální algorit-mus. Pokud se testovaná část prohledávaného řetězce neshoduje s hledanýmpodřetězcem, algoritmus postoupí, stejně jako v případě neshody otisků,o jednu pozici vpravo. V opačném případě algoritmus nalezl hledaný podře-tězec.

Knuth-Morris-Prattův algoritmus

Knuth-Morris-Prattův algoritmus (viz algoritmus 3.12) vylepšuje triviálníalgoritmus (viz kapitola 3.4.4) tím, že v případě částečné nalezené shodyprohledávaného řetězce a hledaného podřetězce se neposune pouze o jedenznak doprava, ale posune se o více znaků, které nemohou být začátkem hle-daného podřetězce. Průběh Knuth-Morris-Prattova algoritmu je rozdělen dodvou částí - předzpracování dat a vlastní vyhledávání hledaného podřetězce.

V rámci předzpracování dat (viz algoritmus 3.13) algoritmus pro hledanýpodřetězec vytvoří tzv. chybovou funkci (anglicky „failure function“), kteráse používá pro určení počtu znaků, o které se může algoritmus v průběhuvyhledávání hledaného podřetězce v zadaném řetězci posunout, aniž by zby-tečně kontroloval pozice, na nichž se hledaný podřetězec nemůže nacházet.

67

Časová asymptotická složitost předzpracování dat činí O(m), vlastní vy-hledávání podřetězce v zadaném řetězci pak dosahuje asymptotické složitostiO(n), kde n značí délku prohledávaného řetězce a m pak značí délku hleda-ného podřetězce [15]. Celková asymptotická složitost Knuth-Morris-Prattovaalgoritmu činí O(m+ n).

Algoritmus 3.12: Knuth-Morris-Prattův algoritmus (převzato z [15])Data: Prohledávaný řetězec T , hledaný podřetězec PVýsledek: Pozice x, na které začíná v prohledávaném řetězci T

hledaný podřetězec P

1 n = T.délka;2 m = P.délka;3 π = VYPOČTI-CHYBOVOU-FUNKCI(P);4 q = 0; // počet shodných znaků

5 i = 0;6 for i < n do7 while q > 0 ∧ P [q + 1] 6= T [i] do8 q = π[q]; // další znak se neshoduje

9 end10 if P [q + 1] == T [i] then11 q = q + 1 // další znak se shoduje

12 end13 if q == m then

// Už jsme nalezli všechny znaky

14 print Podřetězec se v řetězci nachází na pozici i - m;15 end16 i = i+ 1;17 end

3.4.5 Řešení úlohyPro řešení úlohy byl použit triviální algoritmus vzhledem ke své snadné im-plementaci, kdy lze snadno procházet znaky do všech osmi směrů ze zadanépozice. Dalším důvodem pro výběr triviálního algoritmu byl malý rozsahvstupních dat, kdy triviální algoritmus je dostatečně rychlý pro vyřešeníúlohy v zadaném časovém intervalu.

68

Algoritmus 3.13: Knuth-Morris-Prattův algoritmus - chybová funkce(převzato z [15])Data: Hledaný podřetězec PVýsledek: Hodnoty chybové funkce π

1 m = P.délka;2 π[1 . . .m];3 π[1] = 0;4 q = 2;5 k = 0;6 for q ≤ m do7 while k > 0 ∧ P [k + 1] 6= P [q] do8 k = π[k];9 end

10 if P [k + 1] == P [q] then11 k = k + 1;12 end13 π[q] = k ;14 i = i+ 1;15 end16 return π;


Obrázek 3.17: Zpráva o validaci úlohy Where’s Waldorf?

69

4 Závěr

První část práce představuje a popisuje některé známé online systémy pronácvik programování, konkrétně je v první části práce popsáno celkem 7systémů, kterými jsou systémy CodeChef, CodinGame, HackerRank, SphereOnline Judge, TopCoder, UVa Online Judge a Timus Online Judge. Popissystémů se zaměřuje především na zaměření těchto systémů a způsob práces nimi, počet podporovaných programovacích jazyků a počet úloh dostup-ných uživateli pro nácvik programování.

Dalším cílem bakalářské práce byl výběr sady úloh pro výuku programo-vání na počátku bakalářského studia na Fakultě aplikovaných věd Západo-české univerzity v Plzni. V druhé části práce je vybraná sada úloh popsána.Úlohy byly vybrány na serveru UVa Online Judge vzhledem k vysokému po-čtu dostupných úloh a snadnému použití daného systému. Vzhledem k tomu,že je systém UVa Online Judge využíván v několika předmětech vyučova-ných na Fakultě aplikovaných věd, lze očekávat, že alespoň někteří studentijiž budou mít zkušenosti s tímto systémem.

Sada vybraných úloh obsahuje 20 úloh, které jsou různě obtížné. Úlohybyly vybrány tak, aby pokryly hlavní témata vyučovaná na počátku baka-lářského studia. Většina úloh proto představuje grafové úlohy, v nichž jeúkolem například najít nejkratší cestu mezi dvěma vrcholy nebo zkonstruo-vat minimální kostru grafu. Zastoupeny však jsou i jednodušší úlohy vhodnépro začátky programování.

V praktické části bakalářské práce jsou jednotlivé úlohy analyzovány.Ve vlastním textu bakalářské práce jsou analyzovány čtyři úlohy - Joseph’sCousin, All Roads Lead Where?, Expensive Subway a Where’s Waldorf?;analýza dvou úloh (The Tourist Guide a Shortest Names) je součástí přílohpráce, analýza zbývajících úloh byla provedena stejným způsobem jako ana-lýza úloh The Tourist Guide a Shortest Names. Analýza zbývajících úlohje uložena na přiloženém CD. U každé úlohy je uvedeno originální zadánív angličtině, české přeložené zadání, analýza vhodných algoritmů pro ře-šení dané úlohy a řešení úlohy včetně zdrojových kódů programového řešenív programovacím jazyce Java. Programová řešení všech úloh byla úspěšnězvalidována na serveru UVa Online Judge.

Bakalářská práce může být v budoucnu rozšířena o popis dalších zají-mavých úloh vhodných pro výuku programování nebo dalších systémů pronácvik programování.

70

Literatura

[1] Programming Competition,Programming Contest,Online ComputerProgramming [online]. Directi Group, 2009. [cit. 2016/10/17]. Dostupné z:www.codechef.com/.

[2] FAQ | CodeChef [online]. Directi Group, 2009. [cit. 2016/10/17].Dostupné z: www.codechef.com/wiki/faq.

[3] Terms and conditions - CodinGame [online]. CodinGame, 2012.[cit. 2016/10/19]. Dostupné z: www.codingame.com/home.

[4] about us | technical recruiting | hiring the best engineers [online].HackerRank, 2016. [cit. 2016/10/20]. Dostupné z:www.hackerrank.com/aboutus.

[5] Scoring | HackerRank [online]. HackerRank, 2016. [cit. 2016/10/20].Dostupné z: www.hackerrank.com/scoring.

[6] Sphere Online Judge (SPOJ) - Info [online]. Sphere Research Labs, 2016.[cit. 2016/10/20]. Dostupné z: www.spoj.com/info/.

[7] Sphere Online Judge (SPOJ) - Contests [online]. Sphere Research Labs,2016. [cit. 2016/10/20]. Dostupné z: www.spoj.com/contests/.

[8] Sphere Online Judge (SPOJ) - User tutorial [online]. Sphere Research Labs,2016. [cit. 2016/10/20]. Dostupné z: www.spoj.com/tutorials/USERS/.

[9] Topcoder about TopCoder [online]. TopCoder, 2016. [cit. 2016/10/20].Dostupné z: www.topcoder.com/about-topcoder/.

[10] Topcoder - Help [online]. TopCoder, 2016. [cit. 2016/10/22]. Dostupné z:community.topcoder.com/tc?module=Static&d1=help&d2=pracArena.

[11] Guide to using the Problem set @ Timus Online Judge [online]. UralFederal University, 2016. [cit. 2016/10/28]. Dostupné z:acm.timus.ru/help.aspx?topic=judge.

[12] UVa Online Judge - Verdict information [online]. Universidad deValladolid, 2016. [cit. 2016/10/22]. Dostupné z: uva.onlinejudge.org/index.php?option=com_content&task=view&id=16&Itemid=31.

[13] Atkin, A. O. L. – Bernstein, D. J. Prime Sieves Using Binary QuadraticForms. Mathematics of Computation. December 2003, 73, 246,s. 1023–1030. ISSN 0025-5718. doi: 10.1090/S0025-5718-03-01501-1.

71

www.codechef.com/

www.codechef.com/wiki/faq

www.codingame.com/home

www.hackerrank.com/aboutus

www.hackerrank.com/scoring

www.spoj.com/info/

www.spoj.com/contests/

www.spoj.com/tutorials/USERS/

www.topcoder.com/about-topcoder/

community.topcoder.com/tc?module=Static&d1=help&d2=pracArena

acm.timus.ru/help.aspx?topic=judge

uva.onlinejudge.org/index.php?option=com_content&task=view&id=16&Itemid=31

uva.onlinejudge.org/index.php?option=com_content&task=view&id=16&Itemid=31

[14] Bang-Jensen, J. – Gutin, G. Digraphs: theory, algorithms, andapplications. Springer, 2009. ISBN 978-0857290410.

[15] Cormen, T. H. et al. Introduction to Algorithms. The MIT Press, 3edition, 2014. ISBN 978-0-262-53305-8.

[16] Kolář, J. Teoretická informatika. Česká informatická společnost, 2000.ISBN 80-900853-8-5.

[17] Skiena, S. S. – Revilla, M. A. Programming challenges: the programmingcontest training manual. Springer, 2003. ISBN 0-387-00163-8.

[18] Sorenson, J. An Introduction to Prime Number Sieves. ComputerSciences Technical Report 909. January 1990. Dostupné z:http://research.cs.wisc.edu/techreports/1990/TR909.pdf.

[19] Černý, J. Základní grafové algoritmy. České vysoké učení technické, 2013.ISBN 978-80-01-05258-7.

72

http://research.cs.wisc.edu/techreports/1990/TR909.pdf

Seznam použitých zkratek

ACM Association for Computing Machinery - sdružení počítačových pro-fesionálů

Java Objektově orientovaný programovací jazyk vyvinutý firmou Sun Micro-Systems

ANSI C Imperativní nízkoúrovňový programovací jazyk

C++ Objektové rozšíření jazyka C

C++11 Standard jazyka C++ z roku 2011

Python Vysokoúrovňový skriptovací programovací jazyk

LISP List processing - rodina multiparadigmatických programovacích ja-zyků

Nice Objektově orientovaný programovací jazyk

LUA Imperativní programovací jazyk navržený jako skriptovací jazyk

F Sharp Multiparadigmatický programovací jazyk pro .NET

PHP PHP: Hypertext Preprocessor - skriptovací programovací jazyk ur-čený především pro programování dynamických webových stránek

Clojure Dialekt jazyka LISP

Dart Strukturovaný programovací jazyk vyvíjený společností Google

Swift Multiparadigmatický programovací jazyk vyvinutý společností Apple

ELO Statistické ohodnocení hráče dle jeho herních výsledků

Ruby Interpretovaný skriptovací programovací jazyk

SQL Standard Query Language - dotazovací jazyk pro práci s relačnímidatabázemi

Nim Imperativní programovací jazyk

Julia Vysokoúrovňový programovací jazyk pro numerické výpočty

73

LOLCODE Ezoterický programovací jazyk používající zkomolené názvypříkazů a klíčových slov

Whitespace Ezoterický programovací jazyk používající netisknutelné znakyjako příkazy

C Sharp Výsokoúrovňový programovací jazyk vyvinutý firmou Microsoft

VB.NET Objektově orientovaný programovací jazyk pro platformu .NET

Go Kompilovaný multiparadigmatický jazyk vytvoří společností Google

Haskell Funkcionální programovací jazyk používající odložené vyhodnoco-vání

Scala Multiparadigmatický programovací jazyk integrující rysy funkcionál-ního a objektově orientovaného programování

Rust Multiparadigmatický kompilovaný jazyk vyvinutý organizací Mozilla

BFS Breadth-first search, algoritmus prohledávání grafu do šířky

DFS Depth-first search, algoritmus prohledávání grafu do hloubky

FIFO First In, First Out - princip, kdy je první prvek zpracován nejdříve

74

Seznam obrázků

2.1 Logo systému CodeChef . . . . . . . . . . . . . . . . . . . . 92.2 Logo systému CodinGame . . . . . . . . . . . . . . . . . . . 112.3 Vizualizace průběhu programového řešení úlohy Onboarding 122.4 Logo systému HackerRank . . . . . . . . . . . . . . . . . . . 132.5 Logo systému Sphere Online Judge . . . . . . . . . . . . . . 152.6 Logo systému TopCoder . . . . . . . . . . . . . . . . . . . . 172.7 Logo systému UVa Online Judge . . . . . . . . . . . . . . . 18

3.1 Princip funkce Eratosthenova síta . . . . . . . . . . . . . . . 293.2 Zpráva o validaci úlohy Joseph’s Cousin . . . . . . . . . . . 303.3 Reprezentace grafu spojovým seznamem . . . . . . . . . . . 353.4 Reprezentace neorientovaného grafu maticí sousednosti . . . 353.5 Ukázka průběhu algoritmu BFS . . . . . . . . . . . . . . . . 383.6 Ukázka průběhu Dijkstrova algoritmu . . . . . . . . . . . . . 393.7 Zpráva o validaci úlohy All Roads Lead Where? . . . . . . . 453.8 Minimální kostra grafu . . . . . . . . . . . . . . . . . . . . . 503.9 Hledání minimální kostry grafu pomocí Kruskalova algoritmu 533.10 Hledání minimální kostry grafu Prim-Jarnikovým algoritmem 543.11 Počáteční stav při běhu Borůvkova algoritmu . . . . . . . . . 573.12 První iterace běhu Borůvkova algoritmu . . . . . . . . . . . 583.13 Druhá (poslední) iterace běhu Borůvkova algoritmu . . . . . 583.14 Zpráva o validaci úlohy Expensive Subway . . . . . . . . . . 593.15 Průběh triviálního algoritmu pro hledání podřetězců v řetězci

pro podřetězec aab hledaný v řetězci acaabc . . . . . . . . . 653.16 Průběh Rabin-Karpova algoritmu při vyhledávání řetězce 31415

v řetězci 2359023141526739921 . . . . . . . . . . . . . . . . 673.17 Zpráva o validaci úlohy Where’s Waldorf? . . . . . . . . . . 69

75

Seznam příloh

Příloha 1 Úloha 10099 - The Tourist Guide . . . . . . . . . . 77Příloha 2 Úloha 12506 - Shortest Names . . . . . . . . . . . 83

76

Příloha 1

Úloha 10099 - The Tourist Guide

Úloha 10099 - The TouristGuide

Originální zadání úlohy10099 - The Tourist Guide

Mr. G. works as a tourist guide. His current assignment is to takesome tourists from one city to another. Some two-way roads connectthe cities. For each pair of neighboring cities there is a bus servicethat runs only between those two cities and uses the road that directlyconnects them. Each bus service has a limit on the maximum numberof passengers it can carry. Mr. G. has a map showing the cities andthe roads connecting them. He also has the information regardingeach bus service. He understands that it may not always be possiblefor him to take all the tourists to the destination city in a single trip.For example, consider the following road map of 7 cities. The edgesconnecting the cities represent the roads and the number written oneach edge indicates the passenger limit of the bus service that runs onthat road.

Now, if he wants to take 99 tourists from city 1 to city 7, he willrequire at least 5 trips and the route he should take is: 1 - 2 - 4 - 7.But, Mr. G. finds it difficult to find the best route all by himself sothat he may be able to take all the tourists to the destination city inminimum number of trips. So, he seeks your help.

78

InputThe input will contain one or more test cases. The first line of eachtest case will contain two integers: N(N ≤ 100) and R representingrespectively the number of cities and the number of road segments.Then R lines will follow each containing three integers: C1, C2 andP . C1 and C2 are the city numbers and P (P > 1) is the limit onthe maximum number of passengers to be carried by the bus servicebetween the two cities. City numbers are positive integers rangingfrom 1 to N . The (R+1)-th line will contain three integers: S , D andT representing respectively the starting city, the destination city andthe number of tourists to be guided.The input will end with two zeroes for N and R.OutputFor each test case in the input first output the scenario number. Thenoutput the minimum number of trips required for this case on a sepa-rate line. Print a blank line after the output of each test case.Sample Input7 101 2 301 3 151 4 102 4 252 5 603 4 403 6 204 7 355 7 206 7 301 7 990 0Sample OutputScenario #1Minimum Number of Trips = 5

Z originálního zadání úlohy byl převzat obrázek cest uvedený v zadání.Originální zadání úlohy je dostupné na adrese https://uva.onlinejudge.org/external/100/10099.pdf [cit. 2017/04/07].

79



Česká verze zadání úlohy10099 - Průvodce turistů

Pan G. pracuje jako průvodce turistů. Jeho nynějším úkolem je dopra-vit několik turistů z jednoho města do druhého. Města jsou spojenadvousměrnými silnicemi. Mezi každou dvojicí silnicí spojených městjezdí autobus. Každý autobus má omezení, kolik pasažérů může pře-vézt. Pan G. má k dispozici mapu s městy a silnicemi, která je spojují.Dále také ví, kolik pasažérů uvezou jednotlivé autobusy. Ví, že ne vždyje možné dopravit turisty mezi dvěma městy naráz. Uvažujme násle-dující silniční mapu se sedmi městy. Hrany spojující města představujísilnice, ohodnocení hran představuje limit počtu pasažérů, které mo-hou autobusy na příslušných cestách přepravit.

Chce-li pan G. dopravit 99 turistů z města 1 do města 7, bude musetjet nejméně pětkrát po cestě 1 - 2 - 4 - 7. Pan G. považuje hledánínejlepší cesty za příliš obtížné, proto vás žádá o pomoc s určenímnejlepší cesty, aby mohl přepravit turisty s minimálním počtem jízd.VstupVstupní data sestávají z jednoho anebo více testovacích případů. Prvnířádka každého testovacího případu obsahuje dvě celá čísla - N (N ≤100), které označuje počet měst, a R představující počet silnic meziměsty. Na následujících R řádkách nalezneme vždy tři celá čísla C1,C2 a P . C1 a C2 jsou čísla měst, která jsou spojena silnicí, a P (P >

1) představuje omezení počtu pasažérů v autobusu, který jezdí mezizadanou dvojicí měst. Města jsou číslována přirozenými čísly od 1 doN . (R + 1)-tá řádka obsahuje tři celá čísla S, D a T , která značípočáteční město, cílové město a počet pasažéru k přepravení.

80

Vstupní data končí dvojicí nul.VýstupPro každý testovací případ vypište pořadí testovacího případu a mi-nimální potřebný počet cest s turisty. Oddělte výstupní data po sobějdoucích testovacích případů prázdnou řádkou.Vzorový vstup7 101 2 301 3 151 4 102 4 252 5 603 4 403 6 204 7 355 7 206 7 301 7 990 0Vzorový výstupScenario #1Minimum Number of Trips = 5

Řešení úlohyPro řešení úlohy lze použít dynamické programování. Nejprve si vytvořímetabulku o rozměrech N ×N , kde N značí počet měst, kterou inicializujemenulami. Následně do tabulky doplníme ohodnocení hran mezi jednotlivýmidvojicemi silnicí spojených měst (tedy vytvoříme matici sousednosti).

Následně postupujeme podobně jako při Floyd-Warshallově algoritmu,pouze použijeme jiný vztah pro výpočet matic v jednotlivých iteracích algo-ritmu. Pro výpočet prvků du,v matice Di vi-té iteraci algoritmu použijemevztah

du,v = max{Di−1u,v ,min{Di−1

u,i +Di−1i,v }} (4.1)

Na konci výpočtu obsahuje matice maximální možný počet osob, kterélze přepravit mezi každou dvojicí měst. Následně postačí vydělit počet tu-

81

ristů maximálním možným počtem osob, které lze na zadané trase přepravit.Nesmíme zapomenout na průvodce, který musí jet v autobuse spolu s turisty.

Výsledek validaceÚloha byla úspěšně zvalidována, doba běhu činila 0,400 sekundy (viz obrázek4.1).

Obrázek 4.1: Zpráva o validaci úlohy The Tourist Guide

82

Příloha 2

Úloha 12506 - Shortest Names

Úloha 12506 - Shortest Names

Originální zadání úlohy

12506 - Shortest Names

In a strange village, people have very long names. For example: aaaaa,bbb and abababab.You see, it’s very inconvenient to call a person, so people invented agood way: just call a prefix of the names. For example, if you want tocall „aaaaa“, you can call „aaa“, because no other names start with„aaa“. However, you can’t call „a“, because two people’s names startwith „a“. The people in the village are smart enough to always callthe shortest possible prefix. It is guaranteed that no name is a prefixof another name (as a result, no two names can be equal).If someone in the village wants to call every person (including himsel-f/herself) in the village exactly once, how many characters will he/sheuse?InputThe first line contains T (T ≤ 10), the number of test cases. Each testcase begins with a line of one integer n (1 ≤ n ≤ 1000), the numberof people in the village. Each of the following n lines contains a stringconsisting of lowercase letters, representing the name of a person. Thesum of lengths of all the names in a test case does not exceed 1 000 000.OutputFor each test case, print the total number of characters needed.Sample Input13aaaaabbbababababSample Output5

Originální zadání úlohy je dostupné na adrese https://uva.onlinejudge.org/external/125/12506.pdf [cit. 2017/04/01].

84



Česká verze zadání úlohy

12506 - Nejkratší jména

V jedné prapodivné vesnici měli lidé velmi dlouhá jména, napříkladaaaaa, bbb a abababab.Jak můžete vidět, je velmi nepohodlné říkat osobě celým jménem,proto lidé začali jména zkracovat - lidé se oslovovali jen začátky jmentak, aby nikdo jiný ve vesnici neměl stejný začátek jména. Například,pokud byste chtěli oslovit osobu „aaaaa“, postačí ji oslovit „aaa“,protože žádné jiné jméno nezačíná „aaa“. Avšak nemůžete tuto osobuoslovit jen „a“, protože dvě osoby mají stejný začátek jména. Lidé vevesnici jsou dost chytří na to, aby se oslovovali nejkratším možnýmprefixem jména. Je zaručeno, že žádné jméno není prefixem jinéhojména (tedy žádná dvě jména nemohou být shodná).Pokud chce nějaký vesničan oslovit všechny osoby (včetně sebe), kolikpotřebuje písmen?VstupPrvní řádka vstupních dat obsahuje číslo T (T ≤ 10), které udávápočet testovacích případů. Každý testovací případ začíná číslem n (1 ≤n ≤ 1000), které označuje počet osob ve vesnici. Dalších n řádekobsahuje řetězce reprezentující jména jednotlivých vesničanů (všechnapísmena jsou malá). Součet délky všech jmen nepřekročí 1 000 000.VýstupPro každý testovací případ vypište počet potřebných písmen pro oslo-vení všech vesničanů.Vzorový vstup13aaaaabbbababababVzorový výstup5

Řešení úlohyPro řešení úlohy použijeme datovou strukturu trie. Každému vrcholu triepřiřadíme hodnotu udávající, kolikrát je dané písmeno použito ve jménu ně-jaké osoby. Pokud je vrchol listem, bude mít hodnotu jedna, pokud nejde

85

o list, bude hodnota uzlu rovna součtu hodnot potomků. Dále již postačí se-číst všechny hodnoty vrcholů trie, které jsou větší než jedna. Tím dostanemepotřebný počet písmen pro oslovení všech osob ve vesnici.

Pro vzorová vstupní data dostaneme trii zobrazenou na obrázku 4.2. Čísloza pomlčkou značí hodnotu, kolikrát bylo dané písmeno použito ve jménunějaké osoby. Listy trie jsou označeny žlutě.

∅ - 3

a - 2

a - 1

a - 1

a - 1

a - 1

b - 1

a - 1

b - 1

a - 1

b - 1

a - 1

b - 1

b - 1

b - 1

b - 1

Obrázek 4.2: Datová struktura trie pro vzorová vstupní data

86

Výsledek validaceÚloha byla úspěšně zvalidována, doba běhu činila 0,260 sekundy (viz obrázek4.3).

Obrázek 4.3: Zpráva o validaci úlohy Shortest Names

87

Date post:	18-Mar-2022
Category:	Documents
Upload:	others
View:	4 times
Download:	0 times

Bakalářskápráce Sadaúlohprovýuku programování

Documents