První série třicátého prvního ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 15. října 2018. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Odměna série: Sladkou odměnu si vyslouží každý, kdo vyřeší 4 úlohy alespoň na polovinu bodů

Zadání úloh

Žila byla jednou jedna dívenka. Bydlela s maminkou v domečku na kraji vesnice, otec totiž utekl ještě dříve, než se narodila. Její maminka byla švadlena, a protože jednou trochu neodhadla množství látky, spousta červené jí zbyla.

Nevěděla, co si s ní počít. Když přišla móda červených čepečků, mnoho jich vyrobila. Jenomže jak to tak bývá, móda rychle přešla. Lidé je však už měli objednané, tak dceruška musela obcházet sousedství a přesvědčovat je, že si čepečky musí vzít. Od té doby jí nikdo neřekl jinak než Červená karkulka.

Tato práce ji ale strašně nebavila, proto přemýšlela, jak si ji co nejvíce zjednodušit.


Praktická opendata úloha31-1-1 Karkulčin byznys (12 bodů)


Karkulka má po vesnici roznést několik červených čepečků. Stojí zde N domů, všechny leží na jedné přímce a jejich pozice známe. Každý dům si objednal několik červených čepečků. Máme zadanou pozici Karkulčina domu, kde Karkulka začíná s přesně tolika čepečky, kolik potřebuje. Může se pohybovat jen doleva a doprava, přičemž každý metr pohybu ji stojí přesně tolik jednotek energie, kolik má ještě nerozdaných čepečků. Když je Karkulka na pozici s domem, může tam vyložit příslušný počet čepečků, jinak čepečky nikam jinam pokládat nemůže. Kudy má jít, aby ji to stálo co nejméně energie a nebolely ji pak nožičky?

Toto je praktická open-data úloha. V odevzdávacím systému si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku jsou dvě kladná celá čísla: počet domů N a pozice Karkulčina domu (ten mezi oněch N domů nepočítáme). Následuje N řádků popisujících jednotlivé domy. Na každém z nich jsou opět dvě kladná celá čísla: tentokráte pozice domu a počet objednaných čepečků. Máte zaručeno, že žádné dva domy se nenacházejí na stejné pozici a že domy jsou na vstupu seřazené vzestupně podle pozic.

Formát výstupu: Vypište jediné číslo: minimální možný počet jednotek energie, kterou musí Karkulka na roznesení čepečků vynaložit. Pozor, na reprezentaci výsledku můžete potřebovat 64bitová čísla (long long v C, long v Javě; v Pythonu to není potřeba řešit).

Ukázkový vstup:
3 6
1 3
7 5
20 5
Ukázkový výstup:
156

Karkulka začíná na pozici 63 + 5 + 5 = 13 čepečky. V optimálním řešení nejprve Karkulka navštíví dům na pozici 7, což ji stojí |6 - 7|·13 = 13 jednotek energie, poté navštíví dům na pozici 1, což ji stojí |7 - 1|·8 = 48 jednotek energie, a nakonec donese zbylé čepečky do domu na pozici 20, což ji stojí |20 - 1| ·5 = 95 jednotek energie.

Jednoho dne řekla maminka Karkulce: „Karkulko, babička má dneska svátek. Běž ji navštívit a přines jí bábovku a láhev vína. Ale jdi přímo po cestě a nikde se nezdržuj, mohlo by se ti něco zlého přihodit.“

Karkulka tedy šla. Cesta vedla přes hluboký, temný les. Vtom kde se vzal, tu se vzal, stojí před ní obrovský šedý vlk. „Kam jdeš, Karkulko?“ zeptal se. „K babičce,“ odpověděla Karkulka, „má dnes svátek a já jí nesu bábovku a láhev vína.“ „A kde babička bydlí?“ vyptával se vlk. „Támhle za lesem,“ odpověděla důvěřivá Karkulka a prozradila vlkovi i adresu.

Vlk měl zrovna obrovský hlad, a tak vymyslel na Karkulku léčku. „Karkulko,“ povídá vlk, „nechceš natrhat babičce květiny? Určitě bude moc ráda!“


Teoretická úloha31-1-2 Skoro nejkratší cesta (10 bodů)


Karkulka chce babičce natrhat květiny, ale vzpomněla si, co jí maminka kladla na srdce. Ráda by ji poslechla, ale květiny vedle cesty vypadají tak nádherně! Rozhodla se tedy, že si prodlouží cestu jen o kousek.

Les je propletený pěšinkami a křižovatkami. Protože Karkulce strašně dlouho trvá, než se zorientuje, kam z křižovatky vyrazit, dává si pozor hlavně na to, kolika křižovatkami projde. Zároveň chce ale sbírat květiny. Půjde tedy cestou, která má právě jednu křižovatku navíc oproti nejkratší cestě. Pomůžete Karkulce spočítat, kolika různými cestami se může vydat?

Pokud již znáte grafy (třeba díky tomu, že jste si přečetli přiloženou kuchařku), můžete tento hvozd chápat jako neorientovaný neohodnocený graf. V jednom jeho vrcholu stojí Karkulka a v jiném se nachází babiččin dům.

V příkladě na následujícím obrázku jedna z nejkratších cest vede přes křižovatky B a C. Karkulka může jít cestami ABC, ABD, BCD nebo BDC, celkem má tedy na výběr ze čtyř různých cest.

Naznačené rozřezání bábovky

Jen co se Karkulka vydala trhat květiny, vlk už pádil k babiččině domu. „Kdo tam?“ zeptala se babička, když vlk zaklepal. „To jsem já, Karkulka,“ odpověděl sladkým hláskem vlk. Babička otevřela dveře a chramst, vlk ji hned spolknul.

Karkulce netrvalo trhání květin dlouho a brzy také přišla k babiččině domečku. Vlk nechal otevřené dveře, a tak vešla rovnou do kuchyně. S tím však vlk nepočítal. Ještě si nestačil obléknout babiččinu košili a nasadit babiččiny brýle, a tak zavolal: „Karkulko, to jsem ráda, že jsi tu! Zrovna se mi pomíchalo koření na poličce a potřebuji, abys je seřadila, ještě než půjdeš za mnou do ložnice.“

Vlk uměl dokonale napodobit babiččin hlas, a tak si Karkulka ničeho podezřelého nevšimla. Byla zvyklá babičku poslouchat, a hned se tedy do úkolu pustila.


Teoretická úloha31-1-3 Řazení kořenek (10 bodů)


Babička má lahvičky s kořením naskládané vedle sebe na jedné dlouhé poličce. Stojí tam bez ladu a skladu, jak to babičce zrovna přišlo pod ruku, a Karkulka je chce seřadit podle abecedy. Může vždy vzít jednu lahvičku a posunout ji o několik míst doleva nebo doprava, a zařadit ji tak na libovolné jiné místo na poličce. Protože se bojí, aby nějakou lahvičku nerozbila, chce je setřídit na co nejméně přesunů. Poradíte jí, jak to má udělat?

Pro zjednodušení se nemusíte zaobírat řazením slov – můžete předpokládat, že každá lahvička má na sobě napsanou pozici, na které se bude vyskytovat po seřazení.

Například se na poličce mohou vyskytovat kořenky v pořadí 2, 3, 5, 4, 1, 6, 7 (rovnou označujeme kořenky jejich pořadím v abecedě). Jedním ze správných řešení je pak vzít lahvičku 1 a dát ji na začátek a poté lahvičku 5 a přesunout ji o jedno místo doprava. Lze si snadno všimnout, že přesunutím jedné kořenky se posloupnost setřídit nedá.

Jakmile Karkulka koření seřadila, vešla k babičce do ložnice. Babička ležela na posteli, čepec na hlavě, brýle na nose. Karkulce se však něco nezdálo. „Babičko,“ povídá Karkulka, „co to tu tak smrdí?“

To vlk nečekal. Myslel, že se Karkulka třeba zeptá, proč má tak velké oči nebo zuby, ale takhle otázka ho hluboce urazila. Přesto se však vzpamatoval, pohotově vyskočil a Karkulku sežral. Svalil se zpátky na postel a hned usnul.

Náhodou šel kolem babiččina domu zrovna jeden ze zdejších myslivců.


Teoretická úloha31-1-4 Myslivci (8 bodů)


V babiččině vesnici stojí N hájoven a v každé bydlí jeden myslivec. Také se zde nachází M domků, ve kterých bydlí ostatní obyvatelé. Všechny hájovny i domy leží na jedné přímce, jejich polohu máme zadanou. Každý den se každý myslivec vydá na návštěvu do jednoho domu a večer se vrátí zpátky do své hájovny. Myslivci se vzájemně nenavštěvují. Kolik nejméně se každý myslivec nachodí, než navštíví všechny domy? Jinými slovy, pro každou z N hájoven chceme zjistit součet vzdáleností z této hájovny ke všem domkům.

Například se hájovny mohou nacházet na pozicích 3 a 6 a ostatní domky na pozicích 8, 1 a 4. Součet vzdáleností od první hájovny je pak 8 a od druhé 9.

Myslivec vešel do pokoje, uviděl v posteli vlka a hned mu bylo vše jasné. Nebylo to poprvé, co se tohle stalo, zkrátka všechna děvčátka z vedlejší vesnice, která jdou sama hlubokým lesem, se zapovídají s vlkem a takhle to skončí. Myslivec rozpáral vlkovi břicho a nejdřív vyskočila Karkulka a hned za ní i babička, obě dvě šťastné, že zbytek života nemusí strávit ve vlkovi.

Vlkovi do břicha zašili kameny, a když se pak probudil a šel se napít, spadl do studny stejně jako všichni vlci před ním, kteří si chtěli pochutnat na zdejších obyvatelích.

Na oslavu vytáhla Karkulka bábovku, kterou přinesla. Babička si však najednou uvědomila, že během toho zmatku zůstala její zubní protéza nejspíš ve vlkově žaludku, a tak musela bábovku odmítnout. Karkulka si tedy rozdělila bábovku jen s myslivcem – přesně půl na půl.

Ilustrace: Zasněný hroch

Teoretická úloha31-1-5 Krájení bábovky (13 bodů)


Bábovka má tvar kolmého hranolu s konvexní podstavou (tj. takovou, že úsečka nakreslená mezi libovolnými dvěma body podstavy leží celá v podstavě). Karkulka s myslivcem ji chtějí rozpůlit co nejkratším svislým řezem. Kudy má takový řez vést? Pokud existuje více vhodných nejkratších řezů, vyberte si libovolný z nich.

Na následujícím obrázku je uveden příklad bábovky s čtyřúhelníkovou podstavou. Je na něm naznačeno několik řezů (čárkovaně), které rozdělí dort přesně na poloviny. Nejkratší takový možný (tj. ten hledaný) je vyznačen tučně.

Naznačené rozřezání bábovky

Bábovka je snědená, všichni jsou živí a zdraví (až na chudáka vlka), Karkulka se může vrátit domů. Tak tedy… zazvonil zvonec a… však to znáte!

Zuzka Urbanová & Klárka Tauchmanová


Seriálová úloha31-1-6 Hroznýšovo okno (15 bodů)


Letošní seriál se bude zabývat psaním interaktivních aplikací a obecně programů, které musí reagovat na více vstupů a obsluhovat více výstupů najednou. Naučíme se vyrobit GUI (Graphical User Interface) a obecně psát programy tak, aby na ně uživatel nemusel čekat, když zrovna počítají něco dlouhého.

K takovým účelům samozřejmě existuje spousta různých nástrojů, na GUI například .NET framework od Microsoftu, GTK, Qt nebo WxWidgets, bez GUI třeba asyncio v Pythonu nebo libUCW pro C. My si pro výukové účely vybereme PyQt5, což je binding knihovny Qt5 (jinak určené pro C++) do Pythonu. Předvedené principy však zhusta platí pro ledasjaký jiný nástroj.

Instalace

Pravděpodobně nejvíc standardní metodou, jak si v Pythonu pořídit PyQt5, je Pip. Pokud nevíte, co to je Pip, nebo jej neumíte použít, napsali jsme návod na Pip.

$ pip3 install pyqt5

Pokud jste linuxáci a preferujete systémový balík, pak například v Debianu hledejte python3-pyqt5.

Tím máme vyřešenou instalaci. To bylo snadné.

Hello world

Pojďme si vyzkoušet, jestli to vůbec funguje. Pořídíme si triviální GUI.

#!/usr/bin/python3

from PyQt5.QtWidgets import \
    QApplication, QMessageBox
import sys

app = QApplication(sys.argv)
box = QMessageBox(text="ahoj světe")
box.show()
app.exec()

Program by měl zobrazit okýnko s textem „ahoj světe“ a po jeho odkliknutí skončit. Pokud to udělá, je velmi pravděpodobné, že máte PyQt5 nainstalované a funguje.

A teď co vlastně program dělá:

  • from PyQt5.QtWidgets import … – PyQt5 je, stejně jako samotné Qt5, rozděleno na několik částí; v začátku využijeme především QtWidgets, QtCore a QtGui. Balík QtWidgets obsahuje různé grafické prvky, v tomto případě QMessageBox, a také samotný objekt QApplication.
  • import sys potřebujeme na argumenty příkazové řádky, které ke svému běhu Qt potřebuje znát.
  • QApplication je základní objekt aplikace. Stará se o samotné prostředí, nastavuje se v něm řada parametrů GUI (jako například interval pro dvojklik nebo styl oken) a nakonec se v něm schovává smyčka událostí (viz dále).
  • QMessageBox je to okýnko, které jste před chvílí viděli. Metodou show je třeba jej zobrazit, jinak ho neuvidíte a nebudete moci odkliknout.
  • app.exec nakonec celou aplikaci spustí, okýnko nakreslí a vyřídí vaše kliknutí na OK, aby jej mohl zase smazat a skončit. Pokud na tomhle řádku dostanete podivný syntax error, použijte exec_ (s podtržítkem na konci).

Událostmi řízené programování

Programy, které si představujeme ve vzorových řešeních, jsou dávkové. Takový program přečte vstup, zpracuje jej a vydá výstup. Mezitím na uživatele nereaguje. Není interaktivní. Stejným druhem programů pravděpodobně řešíte například opendatové úlohy.

Abychom ale dokázali na uživatele reagovat (téměř) hned, musíme přistoupit k programu z jiné strany.

Jádrem programu bude smyčka událostí (event loop). Můžeme si ji pro začátek představit jako magického hlídacího psa, který si pamatuje všechno, co má hlídat a co v takovou chvíli má dělat. Hlídací pes většinu doby tvrdě spí, jakmile se však objeví nějaká událost, hned vyskočí a zavolá všechno, co se má při události spustit.

Místo postupného vykonávání zadaného programu si tedy zaregistrujeme nějaké události a jejich obsluhu. To se dělá zavoláním příslušné funkce; ukážeme si to. Když pak událost nastane (například stisk myšítka či klávesy nebo třeba vyprší časový limit), předá se popis této události obslužné funkci (tzv. handler či hook), která událost zpracuje. Jakmile nejsou žádné události k vyřízení, hlídací pes jde zase spát a počká, než se objeví nějaká další.

Takovému přístupu říkáme událostmi řízené programování (event-driven programming). Pořádné vysvětlení si ale necháme do některého z dalších dílů, nyní nám bude stačit takovýto úvod.

Ilustrace: Závodící hroši

Netrpělivý program

Předvedeme si další typ události: časovač. Na tom si také ukážeme, jak se události vyřizují. Použijeme na to objekt typu QTimer z balíku QtCore, který zařídí, aby se nějaká akce vykonala se zpožděním.

Následující program zobrazí zprávu na omezenou dobu:

#!/usr/bin/python3

from PyQt5.QtCore import QTimer
from PyQt5.QtWidgets import \
    QApplication, QMessageBox

import sys

app = QApplication(sys.argv)

box = QMessageBox(text="ahoj světe")
box.show()

timer = QTimer(singleShot=True)
timer.timeout.connect(box.close)
timer.start(2000)

app.exec()

Tři řádky, které přibyly, nastavují časovač a jeho akci:

  • QTimer(singleShot=True) vytvoří samotný objekt časovače a nastaví, že se spustí pouze jednou.
  • timer.timeout.connect(box.close) připojí na událost
    timeout obslužnou funkci b.close. S výhodou využíváme toho, že QMessageBox má metodu close, která jej zavře, takže ji můžeme přímo zavolat.
  • timer.start(2000) nastaví budík na 2 sekundy (hodnota je v milisekundách). Až uplynou, vyvolá se událost timeout a zavolají se všechny obslužné funkce, které jsme si k ní zaregistrovali.

Pokud bychom chtěli budík típnout, můžeme zavolat timer.stop(). Když to stihneme včas (před uplynutím nastavené doby), k události timeout nedojde.

Úkol 1 [4b]

Napište program, který po dvou sekundách box se zprávou neuzavře, ale zprávu přepíše například na text „budík už zvoní“. K tomu se hodí metoda setText třídy QMessageBox.

QWidget

Použít jako základ programu QMessageBox je ve skutečnosti dost nešťastné rozhodnutí. Pro počáteční ilustraci, jak fungují události v rámci Qt, to stačí, jinak je ale určený k zobrazování zpráv pro uživatele jako modální dialog; to znamená, že zbytek aplikace zamrzne, dokud uživatel box neodklikne. Později si ukážeme, jak se používá běžně.

GUI napsané v Qt se skládá z QWidgetů naskládaných do sebe. Každý prvek (i celé okno) je widget. QMessageBox v ukázce je také widget, ve kterém je rozmístěná zpráva, ikonka (pokud ji nastavíme) a tlačítka.

A aby Qt vědělo, jak widgety rozmístit uvnitř jiných widgetů, používá na to QLayout. Těch samozřejmě také existují různé typy, například QVBoxLayout a QHBoxLayout pro umístění prvků nad sebe či vedle sebe, nebo QGridLayout pro rozmístění prvků do tabulky.

Stopky

Napíšeme si program, který bude ukazovat čas, který uplynul od stisku tlačítka start.

#!/usr/bin/python3

from PyQt5.QtCore import QTimer
from PyQt5.QtWidgets import \
    QApplication, QWidget, QLabel, \
    QPushButton, QVBoxLayout

import sys

class Stopky(QWidget):
    def __init__(self, *args, **kwargs):

	# Inicializace QWidgetu samotného
        super().__init__(*args, **kwargs)

	# Výroba ovládacích prvků
        self.label = QLabel(self)
        self.button = QPushButton(self,
	              text="start")
        self.button.clicked.connect(self.start)

	# Umístění ovládacích prvků
        self.layout = QVBoxLayout(self)
        self.layout.addWidget(self.label)
        self.layout.addWidget(self.button)

	# Zobrazení stopek
        self.setLayout(self.layout)
        self.show()

    def start(self):
	# Vyrob časovač
        self.timer = QTimer()
        self.timer.timeout.connect(self.tick)
        self.timer.start(1000)

	# Počáteční čas je nula
        self.elapsed = 0
        self.updateLabel()

    def tick(self):
	# Uplynula další sekunda
        self.elapsed += 1
        self.updateLabel()

    def updateLabel(self):
	# Zobrazení uplynulého času
        self.label.setText(str(self.elapsed))

# Spuštění celého programu
app = QApplication(sys.argv)
stopky = Stopky()
app.exec()

Program je nyní celý schován v objektu Stopky, což je také hlavní okno programu. V konstruktoru objektu se okno sestaví a zobrazí a taktéž se připojí událost k tlačítku. Obslužná funkce tlačítka pak spustí časovač a jeho obslužná funkce periodicky zvyšuje čítač a zobrazuje jeho změněnou hodnotu.

Ilustrace: Letící hroch

Úkol 2 [4b]

Přidejte do výše uvedeného programu tlačítko „stop“, které stopky zastaví.

Úkol 3 [4b]

Přidejte do výše uvedeného programu ještě jeden QLabel, který bude zobrazovat, v jakém intervalu se stopky aktualizují (nyní je to jedna sekunda). Přidejte také dvě tlačítka, kterými je možno interval zvyšovat a snižovat.

Úkol 4 [3b]

Zařiďte, aby změna intervalu v předchozím úkolu byla okamžitá bez čekání na předchozí tik časovače.

Poznámka: Úkoly 2, 3 a 4 je možno vyřešit jedním programem.

Stopkami dnešní náhled do PyQt5 uzavřeme a příště si povíme trochu víc teorie, která se ke GUI a UŘP (Událostmi řízené programování) váže, a ukážeme další ovládací prvky a události, které se ve Qt dají použít.

Maria Matějka