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

Celý leták, který posíláme také papírově, v PDF.

Nový školní rok právě začal a s ním přinášíme i nový ročník KSP. Leták s úlohami první série právě držíte v ruce.

Pravidelní řešitelé si možná všimnou, že úloh není tolik jako minulé ročníky. Pro tento ročník vám v každé sérii upečeme 6 úloh. Z této šestice bude vždy jedna úloha opendatová a jedna přiřazená k seriálu, jehož téma nás bude provázet celým ročníkem. Další změna se chystá v termínu vydání autorských řešení. Ta budeme letos zveřejňovat současně s termínem série (tedy stejně jako jste zvyklí z kategorie Z).

Do celkového bodového hodnocení se z každé série stále započítává 5 nejlépe vyřešených úloh.

Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (této kategorie) alespoň 50 % bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice pro úspěšné řešitele je 150. Maturanti pozor, pokud chcete prominutí využít letos, musíte to stihnout do konce čtvrté série, pátá už bude moc pozdě.

Každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, placku a možná i další překvapení.

Pokud budete mít jakoukoliv otázku, neváhejte se zeptat. Kontaktní adresy najdete v patičce na konci letáku. Přejeme hodně štěstí!

• Termín série: 15. října 2018 v 8:00
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

• Odměna série: Každému, kdo vyřeší 4 úlohy alespoň na polovinu bodů, pošleme sladkou odměnu.

Zadání úloh

• 31-1-1: Karkulčin byznys
• 31-1-2: Skoro nejkratší cesta
• 31-1-3: Řazení kořenek
• 31-1-4: Myslivci
• 31-1-5: Krájení bábovky
• 31-1-6: Hroznýšovo okno

31-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ávátku 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).

3 6
1 3
7 5
20 5

156

Karkulka začíná na pozici 6 s 3 + 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.

Řešení

31-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.

Řešení

Komentáře

31-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á.

Řešení

Komentáře

31-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.

Řešení

Komentáře

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.

31-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ě.

Řešení

Komentáře

31-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.

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.

Ú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

Řešení

Komentáře