První série začátečnické kategorie třicátého devátého ročníku KSP

Celý leták v PDF.

Řešení úloh

• 39-Z1-1: Neapolská opera
• 39-Z1-2: Sicilská vražda
• 39-Z1-3: Kevin v Itálii
• 39-Z1-4: Záchrana Italské MHD

39-Z1-1 Neapolská opera (Zadání)

Myšlenka úlohy není složitá: chceme načíst jednotlivé řádky, na každém najít největší číslo, a ta přes všechny řádky sečíst. Povíme si, jak takovou myšlenku naprogramovat v Pythonu.

Bude se nám hodit umět načíst seznam čísel oddělený mezerou. Funkce input() čte jednu řádku vstupu, vrací ji však jako řetězec. Metoda .split(oddelovac) řetězec rozdělí podle oddělovače, případně podle bílých znaků, pokud oddělovač vynecháme. Napsáním řádek = input().split() tak dostaneme v proměnné řádek seznam mezerou oddělených částí vstupu. Jednotlivé položky seznamu jsou však ale stále řetězce. K převedení řetězce na číslo se hodí funkce int(řetězec).

Můžeme si tedy vytvořit pomocné pole čísla, na začátku prázdné. Pak můžeme iterovat přes náš řádek a každou jeho položku převést na číslo a přidat ji do pole čísla. To určitě funguje, Python má však i jednodušší syntaxi pro zapsání té samé věci:

čísla = [int(řetězec) for řetězec in řádek]

Z toho už si můžeme vytvořit funkci:

def načti_řádek():
	řádek = input().split()
	return [int(x) for x in řádek]

Teď už se můžeme pustit do zbytku úlohy. Nejdřív přečteme N a M pomocí N, M = načti_řádek(). Python vezme vrácený seznam a jeho první prvek přiřadí do N a druhý do M (a kdyby měl seznam jiný počet prvků než dva, bude si stěžovat).

Pak už děláme samotný výpočet. Vždy načteme jeden řádek čísel a hledáme v něm maximum. To samozřejmě můžeme dělat ručně tak, že za průběžné maximum nastavíme nejdřív první prvek řádku a pak řádek procházíme, porovnáváme každý prvek s průběžným maximem a případně maximum aktualizujeme. Mnohem snažší je ale použít vestavěnou funkci max. Té prostě předhodíme seznam a ona nám vrátí jeho největší prvek.

Zbývá maxima sečíst: pořídíme si proměnnou soucet, zpočátku nulovou, do které postupně přičítáme a na konci ji vypíšeme. Zmíníme, že Python má také funkci sum, která podobně jako max bere seznam a vrací jeho součet. Můžete si zkusit rozmyslet, jak ji v této úloze použít.

39-Z1-2 Sicilská vražda (Zadání)

Naším cílem je najít v seznamu N dvojic otázku, která má víc než 1 možnou odpověď. Ale jak takovou otázku najdeme? Můžeme si držet seznam všech zatím dotázaných otázek a ke každé z nich si držet dosavadní odpověď. Dále si budeme pro každou otázku držet všechny indexy řádků, které jsme našli s odpovědí na ni.

Nyní vždy když dostaneme další dvojici otázka–odpověď, projdeme celý seznam otázek. Pokud jsme dosud nepoložili tuto otázku, přidáme ji do seznamu odpovědí a založíme zápis v seznamu indexů, kde bude jen jeden index, a to ten aktuální. Předpokládejme nyní, že otázka je již zodpovězená, v tu chvíli porovnáme odpověď, kterou máme zapsanou s tou, kterou jsme právě obdrželi. Pokud se odpovědi shodují, přidáme momentální index řádku do seznamu s indexy odpovědí na danou otázku. Ovšem pokud jsme našli jinou odpověď na stejnou otázku, pak jsme našli hledanou konfliktní otázku. Zapíšeme si tedy někam stranou novou odpověď a k ní i index aktuálního řádku.

Takto projdeme všechny dvojice a pak se podíváme na hodnoty. Pokud jsme žádnou konfliktní otázku nenašli, vrah už unikl. U konfliktní otázky máme dvě různé odpovědi. Pokud každou z nich řekl právě jeden člověk, nevíme, který z nich je vrah, a odpověď je NE. Jinak víme, že odpověď, kterou řeklo více lidí, je pravdivá. Vybereme tedy druhou odpověď a její index je index našeho vraha.

Abychom analyzovali časovou složitost, pojďme se podívat na seznam našich odpovědí a jak ho spravujeme. Nejjednodušší je zkrátka pokaždé projít seznam a porovnávat, zda otázka, kterou jsme právě obdrželi, se shoduje s otázkou, kterou máme uloženou na daném indexu. Jedno přidání nové odpovědi by nás pak stálo O(DN), kde D je největší délka otázky. Vzhledem k tomu, že máme N dvojic na zpracování, celé by nás to pak stálo O(DN²).

Ovšem stále to jde lépe. A dokonce i jednodušeji. Místo pracného třídění si budeme držet hešovací tabulku. Pokud ještě hešovací tabulky neznáte, můžete si o nich přečíst v naší kuchařce. Nyní si prostě pro každý klíč (v našem případě otázku) uložíme jeho hodnotu (odpověď). Držíme si k tomu stále seznam indexů, také v hešovací tabulce, a přidáváme do něj, podle toho jak seznam procházíme. Přidání 1 otázky o maximální délce D nás stojí v průměru O(D), tedy N přidání stojí v průměru O(DN).

39-Z1-3 Kevin v Itálii (Zadání)

Úloha od nás chce, abychom pro různé dotazy zjistili, zda existuje legální cesta z bodu A_i do bodu B_i. Pro začátek předpokládejme, že cesta existuje. Jak se ale dá najít? Víme, že Kevin od nás nechce zjistit, kterými linkami má jít, a linky nemají přesné hodiny, kdy mají odjezdy. Tyto informace nám pomohou k sestavení správné struktury na uložení mapy MHD do počítače.

Jak si ale takovou MHD uložit v počítači? Pojďme se podívat na jednu efektivní strukturu – seznam sousedů. Pro každou stanici si uložíme seznam stanic, do kterých vede cesta o délce jedna, tedy následujících zastávek linek. Delší cesty pak vzniknou řetězením těchto přechodů. V informatice se takováhle množina vrcholů (zastávek) a hran (spojů mezi sousedními zastávkami linky) nazývá graf.

Graf vyrobíme tak, že pro každé dvě po sobě jdoucí zastávky linky přidáme hranu z první do druhé, s výjimkou spoje na konečnou, na které autobus nezastavuje. Celkový počet hran je proto nejvýše lineární v počtu zastávek na vstupu. Když nevíme, kolik zastávek existuje, vyplatí se použít slovník, ve kterém bude pro každou zastávku pole s jejími sousedy.

Teď, když jsme si náš graf reprezentovali, si napišme jednoduchý algoritmus na hledání v grafu. Použijeme prohledávání do hloubky (DFS) který si zde pro úplnost popíšeme. Pro začátek si vytvořme pole navštívených vrcholů, kde si vždy zapíšeme, když jsme na dané zastávce již byli. Druhé pole, které si vytvoříme, bude představovat zásobník – budeme do něj moct vkládat a vykládat prvky jen z nejvyššího místa.

Algoritmus začne tím, že do zásobníku vloží první vrchol, kde Kevin nastupuje, a hned ho označí jako navštívený. Pak opakujeme následující kroky, dokud není zásobník prázdný nebo nenajdeme finální vrchol. Vybereme vrchol ze zásobníku a zkontrolujeme, jestli není finální. Pokud není, vložíme do zásobníku všechny jeho sousedy, které jsme ještě nenavštívili, a při vkládání je označíme jako navštívené. Označujeme je už při objevení, aby se stejný vrchol do zásobníku nedostal vícekrát. Pak znovu opakujeme cyklus.

Tímhle způsobem navštívíme všechny vrcholy (zastávky) a nikdy nevytvoříme nekonečný cyklus. Když jsme našli na cestě finální stanici, tak vypíšeme ANO, ale jestli budeme mít prázdný zásobník, vypíšeme NE. Algoritmus má složitost O(N + M), kde N je počet zastávek a M je počet přímých spojů mezi nimi, protože každý vrchol a každou hranu zpracujeme právě jednou. Celková složitost je ale O(Q(N + M)), protože pro každý dotaz musíme spustit algoritmus znovu. (Se správným předvýpočtem můžeme dostat algoritmus se složitostí O(N + M + Q), ale o tom zas někdy příště.)

39-Z1-4 Záchrana Italské MHD (Zadání)

Úlohu nejprve převedeme do řeči teorie grafů: máme neorientovaný graf s N vrcholy a M hranami. Chceme jeho vrcholy obarvit dvěma barvami – třeba bílou a černou – tak, aby spolu nesousedily dva bílé nebo dva černé vrcholy, nebo zjistit, že to nejde. Ačkoliv to po nás zadání nechtělo, vyřešíme ještě o něco obecnější úlohu, kdy na začátku už nějaké vrcholy (potenciálně žádné) mají svou barvu přiřazenou.

Pro začátek předpokládejme, že graf je souvislý (mezi každými dvěma vrcholy existuje cesta) a že na začátku má alespoň jeden vrchol přiřazenou barvu. Pak si můžeme rozmyslet, že pokud existuje řešení, tak je unikátní: obarvený vrchol vynucuje barvu svých sousedů, ti vynucují barvu svých sousedů, a tak dále. Pokud v nějakém okamžiku zjistíme, že nějaký vrchol by měl mít obě barvy současně, tak víme, že řešení nemůže existovat.

Stačí tedy najít libovolný již obarvený vrchol a z něj pustit prohledávání do šířky (fungovalo by i do hloubky) s drobnou úpravou: stojíme-li v již obarveném vrcholu u a koukáme na jeho souseda v, tak už víme, jakou v musí mít barvu. Tu mu buď přiřadíme (nemá-li ji ještě), nebo zkontrolujeme, že jeho skutečná barva sedí. Separátně si jako při klasickém prohledávání do šířky udržujeme pro každý vrchol, zda již jsme ho navštívili, a nenavštívené vrcholy přidáváme do fronty.

Takové řešení má časovou i paměťovou složitost O(N + M). Na konci buď získáme jediné správné obarvení, nebo někdy v průběhu zjistíme, že obarvení nemůže existovat.

Zbývá se zbavit našich dvou předpokladů. Pokud v grafu neexistuje obarvený vrchol, tak můžeme libovolný vrchol vzít a obarvit ho na černo. Určitě platí, že pokud graf jde obarvit, tak jde obarvit tak, aby daný vrchol byl černý, protože barvy jsou zaměnitelné. Tím jsme problém převedli na předchozí případ, který už umíme vyřešit, a strávili jsme jen O(N) času navíc zjišťováním existence obarveného vrcholu.

Pokud graf není souvislý, stačí ho rozdělit na komponenty souvislosti a každou z nich vyřešit zvlášť. To můžeme udělat třeba opakovaným prohledáváním do šířky, které postupně pouštíme na všechny ještě nerozřazené vrcholy. Časová složitost bude lineární v součtu velikostí všech částí, což je O(N + M).