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

Jaro už klepe na dveře a příroda i nejeden organizátor se pomalu probouzejí ze zimního spánku. Od minulé série jsme na vás nezapomněli a přichystali jsme si pro vás další várku úloh. Těšit se můžete také na pokračování seriálu a kuchařku o těžkých problémech.

Připomínáme, že do celkového hodnocení se vám z každé série započte 5 nejlépe vyřešených úloh. Každému řešiteli, který získá v tomto ročníku z každé série alespoň 5 bodů, pošleme KSP propisku, blok, placku a třeba i něco navíc.

Díky řešení KSP se také můžete vyhnout přijímacím zkouškám na MFF UK! Stačí, když získáte alespoň polovinu bodů z ročníku (tedy 150 bodů) a my vám vystavíme osvědčení, díky kterému vás přijmou na MFF bez zkoušek. Pozor ale: pokud studujete poslední ročník střední školy a chcete letošní osvědčení využít, musíte mít potřebné body již po této sérii. V takovém případě se nám ozvěte mailem.


Zadání úloh

Jednoho krásného zimního dne, kdy se sněhové vločky k zemi jako drobounká pírka snášely, seděla jedna královna u okna a vyšívala. Jak tak v zamyšlení z okna ven koukala, bodla jehlou do prstu, až na okenní římsu tři krůpěje krve skanuly. Tu si královna pomyslela, že by měla ráda takové děťátko, které by bylo rudé jako ta krev, bílé jako ten sníh a černé jako okenní rám z ebenového dřeva. Neuplynul ani rok a královně se narodila krásná dceruška. Sotva však královna svou dcerku poprvé políbila, navždy oči zavřela.

Netrvalo dlouho a král si našel novou královnu, jež ho svou krásou a medovým hlasem učarovala. A tak Sněhurka (jak malému děťátku pro jeho sněhobílou pleť říkat začali) macechu získala. Nová královna byla převelice pyšná a na své kráse si velmi zakládala. Ráno, hned jak vstala, se kouzelného zrcadla ptávala: „Zrcadlo, zrcadlo, pověz, kdo je na světě i v zemi zdejší ze všech k-tý nejkrásnější?“


Teoretická úloha31-4-1 Kouzelné zrcadlo (10 bodů)


Macecha se chce ujistit, že se na žebříčku nejkrásnějších lidí stále nachází na k-tém místě. Kouzelné zrcadlo má přístup k údajům o lidech z celého světa. Mezi údaji se mimo jiné nachází dvě posloupnosti obsahující osoby srovnané podle krásy, od nejkrásnější po nejméně krásnou (jedna posloupnost pro ženy, druhá pro muže). Krása osoby je zde určena nějakou hodnotu, každá osoba má tuto hodnotu unikátní a navíc platí, že při srovnání dvou osob má krásnější osoba hodnotu nižší. Zrcadlo chce najít k-tou nejkrásnější osobu, tj. k-tou nejmenší hodnotu sjednocení obou posloupností. Jak to má udělat, aby mohlo královně odpovědět co nejrychleji?

Řešení

Komentáře

Zrcadlo ji ujistilo, že to ona je stále v této zemi k-tá nejkrásnější. Macecha pak byla po celý zbytek dne v dobré náladě, protože věděla, že její zrcadlo lhát nemůže. Tak to šlo den po dni, měsíc po měsíci.

Jak šel čas, malá Sněhurka postupně rostla do krásy. Jednoho rána, v den, kdy bylo Sněhurce zrovna patnáct let, se macecha jako obvykle postavila před zrcadlo a zeptala se: „Zrcadlo, zrcadlo, pověz, kdo je na světě i v zemi zdejší ze všech k-tý nejkrásnější?“ Kouzelné zrcadlo odpovědělo: „Jsi krásná, paní má, avšak v zemi zdejší Sněhurka je k-tá nejkrásnější.“ To macechu nesmírně rozzlobilo. Dlouho se nerozmýšlela a okamžitě si k sobě nechala povolat myslivce. Přikázala mu, aby Sněhurku zavedl do lesa, zabil ji a na důkaz splnění příkazu přinesl královně její srdce.

Ještě téhož dne myslivec nabídl Sněhurce, jestli si s ním nechce vyjít do lesa, že pro ni má zajímavý úkol. Nedávno totiž hluboko v lese objevil jednu mýtinku, na které ještě nikdy v životě nebyl. Proto potřebuje pomoct s klasifikací stromů, které v jejím okolí rostou. Nemusel Sněhurce říkat dvakrát, šla do lesa ráda.


Teoretická úloha31-4-2 Stromy na mýtince (11 bodů)


Myslivec potřebuje pomoct s klasifikací stromů na nově objevené mýtince. Stromů se ale na mýtince nachází opravdu hodně, takže není v lidských silách je klasifikovat jednotlivě. Myslivec si však všiml, že některé stromy mají v určitém slova smyslu „stejnou strukturu“. Jedna větev roste tady, ale vedlejší strom má úplně stejnou větev, jen vyrůstá z jiného místa na stromě… Kdyby dokázal stromy rozdělit na skupinky tak, aby v jedné skupince byly stromy se „stejnou strukturou“, pracovalo by se mu s nimi o dost lépe a jejich klasifikaci by měl hotovou mnohem rychleji.

Příklad k úloze

Trochu formálněji: na vstupu je několik uspořádaných zakořeněných stromů (tj. zakořeněných stromů, kde každý vrchol má určené pořadí synů „zleva doprava“). Řekneme, že dva stromy jsou izomorfní, pokud po vhodném přejmenování vrcholů dostaneme dva stejné stromy (tj. se stejným kořenem, strukturou a pořadím synů ve vrcholech). Vaším úkolem je rozdělit stromy na několik hromádek, aby dva stromy byly na stejné hromádce, právě když jsou izomorfní.

Na příkladu na předchozí stránce jsou hromádky izomorfismu tři: {T1}, {T2}{T3, T4}. Vhodný izomorfismus z T3 na T4 přejmenovává vrcholy následovně: 4 → 3, 3 → 1, 2 → 4, 1 → 2. Všimněte si že T1T2 izomorfní nejsou, neboť žádné přejmenování vrcholů nezachovává správné pořadí synů vrcholu 1.

Řešení

Komentáře

Zatímco se Sněhurka snažila úkol vyřešit, myslivec se pomalu odplížil a spěchal zpátky na zámek. Nedokázal totiž ubohé Sněhurce ublížit. Vzpomněl si však, oč ho královna žádala. Proto cestou zabil srnku, vyňal z ní srdce, a to pak královně přinesl na „důkaz“ splnění úkolu.

Když Sněhurka nakonec úkol vyřešila, s hrůzou zjistila, že myslivec mezitím zmizel. I vydala se ho hledat. Klopýtala hlubokým lesem cestou necestou, dál a dál od rodného zámku. Ale myslivec nikde… Už se pomalu začínalo smrákat, když tu se najednou les rozestoupil a Sněhurka se ocitla na paloučku, kde stála hezká chaloupka. „Přespím tu,“ pomyslela si, „a ráno mě myslivec určitě najde.“

Když vešla dovnitř, úžasem oněměla. V malé světničce stál dlouhý stoleček a na něm leželo N talířků. U každého talířku lžička, nůž a vidlička a před talířkem sklenička. U stěny pak v řadě vedle sebe stálo N čistě povlečených postýlek. Protože už měla Sněhurka po celém dnu pořádný hlad, neodolala, z každého talířku si vzala jedno sousto a z každého pohárku se trochu napila. A že byla hodně unavená, zalezla do jedné z postýlek.

Ilustrace: N trpaslíků v postýlkách

Než však stihla Sněhurka oči zamhouřit, dorazil do chaloupky první trpaslík. Byl ale natolik vyčerpaný z celodenní práce v dole, že pouze Sněhurku, která právě ležela v jeho postýlce, požádal, aby se přesunula někam jinam. „Do které z postýlek si mohu lehnout, sličný pane trpaslíku?“ zeptala se Sněhurka zdvořile. „Tamhle, vedle dveří, visí na zdi rozpis nočních směn všech trpaslíků. Tam můžeš zjistit, kdy se kdo vrátí domů.“


Praktická opendata úloha31-4-3 Nejvíc spánku (8 bodů)


Sněhurka je po náročném bloudění lesem velice unavená a chtěla by se co nejdéle prospat. V chaloupce se nachází N postýlek, každá postýlka patří právě jednomu z N trpaslíků. Sněhurka má k dispozici rozpis nočních směn všech trpaslíků, což je seznam zprava otevřených intervalů, kdy jsou jednotliví trpaslíci v dole. Proto ví, od kdy do kdy je která postýlka volná. Chtěla by si vybrat, ve kterých postýlkách bude spát, aby naspala co nejvíce. Sněhurka je tak unavená, že když jednou do nějaké postýlky zaleze, vstane, až když ji z ní její majitel vyhodí. Zároveň ale nechce lézt do postýlky, která je studená, a proto zaleze pouze do té, z které její majitel právě odešel a která je tedy stále pěkně vyhřátá.

Jinými slovy, máme N intervalů ⟨a, b). Chceme vybrat podmnožinu s co největší celkovou délkou, ve které se žádné dva intervaly neprotínají.

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 vstupu se nachází kladné celé číslo N udávající počet intervalů. Na každém z následujících N řádků jsou vždy dvě celá čísla ai, bi (0 ≤ ai < bi ≤ 109) udávající levý a pravý okraj intervalu ⟨ai, bi), kdy je i-tý trpaslík v dole.

Formát výstupu: Na jediném řádku vypište celé číslo: největší možnou celkovou délku Sněhurčina spánku. Délka intervalu ⟨a, b) je b - a.

Ukázkový vstup:
6
0 5
0 1
4 10
0 2
2 3
6 8
Ukázkový výstup:
9

Optimální je vybrat intervaly ⟨0, 2), ⟨2, 3)⟨4, 10).

Řešení

Trpaslíci si Sněhurku brzy oblíbili. Pomáhala jim s úklidem, vařila a celkově se o ně pěkně starala. Každé ráno, když trpaslíci odcházeli do práce, Sněhurku varovali: „Dávej na sebe pozor. Hlavně nikomu cizímu neotvírej a dovnitř ho nepouštěj!“

Takhle by mohli všichni v chaloupce žít šťastně navěky, kdyby se jednoho dne zlá královna špatně nevyspala. Protože si chtěla spravit náladu, postavila se před zrcadlo a zeptala se: „Zrcadlo, zrcadlo, pověz, kdo je na světě i v zemi zdejší ze všech k-tý nejkrásnější?“ „Jsi krásná, paní má, avšak v zemi zdejší Sněhurka je k-tá nejkrásnější,“ pravilo kouzelné zrcadlo. Královna se začala vzteky dusit. „Kde je?“ vypravila ze sebe. A zrcadlo odpovědělo: „Za devíti lesy žije a den ode dne krásnější je.“ Rozzuřená královna se rozhodla, že se Sněhurky jednou pro vždy zbaví. Zavřela se do své komnaty a tam čarovala a zaříkávala tak dlouho, dokud jedovaté jablko nevyrobila. Pak se přestrojila za prostou selku, vzala si košík s ovocem a vydala se k chaloupce.


Teoretická úloha31-4-4 Otrávené ovoce (12 bodů)


Kuchařková úloha

Zlá královna chce dopravit otrávené ovoce ze zámku do chaloupky skrz hluboký les. Jako v každém lese se i zde nacházejí jak mýtinky, tak i cestičky, které vždy nějakou dvojici mýtinek spojují. Protože to ale není les obyčejný, každá cestička má daný směr, ve kterém po ní lze projít. Další speciální výsadou lesa je, že se v něm vyskytuje spousta prapodivných stvoření. Každé takovéto stvoření žije v blízkosti nějaké cestičky a pokud procházející kolemjdoucí vlastní ovoce, kterým se dané stvoření živí, kolemjdoucího o něj obere. Stvoření jsou ale tuze vybíravá, živí se pouze konkrétními druhy ovoce a ničím jiným. Sama královna se s žádným prapodivným stvořením tváří v tvář setkat nechce, a proto si nechá ovoce přes les přepravit svými služebníky. Pověřila svého rádce, aby zjistil, kolik na to potřebuje služebníků. Rádce přemýšlel a počítal, ale nedopočítal se a královně chce dokázat, že je tento úkol nad jeho síly.

Les si lze představit jako orientovaný neohodnocený graf, zámek představuje start a chaloupka cíl. Otrávené ovoce představuje množinu věcí, kterou chceme přepravit ze startu do cíle. Každá hrana je ohodnocena množinou ovoce, které nám zůstane, pokud přes ni projdeme. K dispozici máme několik služebníků, každý z nich dostane nějakou podmnožinu otráveného ovoce. Úkolem je zjistit, kolik nejméně služebníků musí královna vyslat, aby zvládli dopravit všechno ovoce ze startu do cíle, nebo případně říct, že to nejde. Dokažte, že tento problém je NP-úplný.

Na následujícím příkladu si pro množinu otráveného ovoce M = {1, 2, 3, 4}, zámek ve vrcholu A a chaloupku ve vrcholu E vystačíme se třemi služebníky: prvnímu dáme množinu {1, 4} a pošleme ho cestou ACDE, druhému dáme množinu {2} a pošleme ho cestou ACE a třetí dostane {3} a půjde po cestě ABDE. Rozmyslete si, že méně služebníků ovoce přepravit nedokáže.

Příklad k úloze

Řešení

Komentáře

Jakmile se královna i s ovocem bezpečně dostala na druhou stranu lesa, počkala na okamžik, kdy budou všichni trpaslíci pryč, a pak zaklepala na dveře chaloupky. Sněhurka nic netušila a s úsměvem královně otevřela. V přestrojení svou macechu nepoznala, a tak se vesele zeptala: „Co si přejete, babičko?“ „Přinesla jsem ti jablíčko, děvenko, je dobré, sladké, jen ochutnej!“ švitořila úlisně královna. Sněhurka královně poděkovala a vzala si jablko do ruky. Vypadalo tak krásně! Bylo to to nejčervenější a nejšťavnatější jablko, jaké kdy Sněhurka viděla. Dlouho se nerozmýšlela a hned se do něj zakousla.

V tu chvíli královna zajásala, odhodila svůj převlek a sledovala, jak Sněhurka v mdlobách padá k zemi. Jed zafungoval! „Konečně jsem se jí zbavila,“ vyjukla radostí a uháněla zpátky do svého zámku.

Když se trpaslíci vrátili domů a uviděli Sněhurku ležet na zemi, velmi se zarmoutili. Neměli ji nechávat doma samotnou! Uložili Sněhurku do skleněné rakve a tři dny a tři noci plakali nad její smrtí. Čtvrtého rána však zaslechli zvonění kopyt, a jak se větve lesa rozestoupily, stál před nimi nádherný princ na bílém koni. „Kdo je ta krásná dívka?“ zeptal se, jakmile spatřil Sněhurku. „To je Sněhurka,“ odpověděli trpaslíci, „ale jdeš pozdě, princi.“ A znovu se rozplakali.

Princ sestoupil z koně a přiblížil se ke Sněhurce. „Je tak nádherná… Vypadá, jako by jen spala!“ Odkryl víko a přizvedl k sobě Sněhurčino tělo. V tu chvíli Sněhurce z krku vyskočil kus otráveného jablka a Sněhurka otevřela oči. „Ona žije!“ „Stal se zázrak!“ volali trpaslíci jeden přes druhého.

Když Sněhurka na prince pohlédla, okamžitě se do něj zamilovala. Nasedli společně na princova koně a vydali se na zámek za Sněhurčiným otcem. Jak byl král rád, že se se svou ztracenou dcerou znovu shledal! Sněhurka pak svému otci pověděla, co se jí přihodilo a jak se ji zlá královna pokusila zabít. Když si král vyslechl celý příběh, nechal královnu z království navždy vyhnat. Statečnému princi za záchranu Sněhurky přislíbil její ruku a k-tinu království k tomu.


Teoretická úloha31-4-5 Dělení království (12 bodů)


Princ si chce spočítat, kolik že je to ta k-tina celého království. Ví, že celé království má hodnotu h, což je nějaké celé číslo, a chce spočítat desítkový zápis zlomku h/k s vyznačenou periodou. Ovšem princ si toho moc nepamatuje, k dispozici má jen svou hlavu s konstantním počtem paměťových buněk a kus pergamenu, na který se mu ale tak tak vejde samotný výsledek, takže už na něj nemůže napsat nic dalšího.

Čísla h i k se vejdou do jedné paměťové buňky a běžné operace s nimi umíme provádět v konstantním čase. To znamená, že je například umíme v konstantním čase násobit, sčítat a celočíselně dělit, ale neumíme už například v konstantním čase napočítat od 1 do k nebo čísla dělit desetinně s neomezenou přesností. Pokud vám tento model přijde zvláštní, dosaďte si za něj například klasická 64bitová čísla ve vašem oblíbeném programovacím jazyce.

Známe řešení, které potřebuje konstantní pomocnou paměť a pracuje v čase O(N), kde N je počet cifer výsledku. Najdete nějaké stejně dobré? Poslat samozřejmě můžete i pomalejší řešení, důležité však je, aby také pracovalo s konstantní pomocnou pamětí. (Algoritmus s nekonstantní pamětí jste už možná potkali jako úlohu 31-Z2-4.)

Příklad: pro h = 5251, k = 700 princ na pergamen zapíše číslo 7,50
142857
.

Řešení

Komentáře

Nedlouho poté se konala veliká svatba a jestli neumřeli, žijí princ se Sněhurkou šťastně dodnes.

Zuzka Urbanová & Klárka Tauchmanová

Ilustrace: Sněhurka s princem před zámkem

Seriálová úloha31-4-6 Kde je hroznýš? Kuk! (15 bodů)


Prosíme řešitele, aby tuto úlohu odevzdávali jako prostý text; PDF se těžko spouští a testuje.

V minulém dílu seriálu o Qt jsme přepsali simulátor nadchodu tak, aby měl oddělený datový model a ovládací rozhraní, neboli podle principu Model–View. Dnes nás čeká napsat si vlastní View. A protože chceme auta a chodce zobrazovat graficky, učiníme krok stranou a prvně si prostě napíšeme vlastní widget.

Kterak si poříditi widget

Nakreslíme si něco úplně obyčejného, třeba sluníčko. To zařídíme implementováním metody paintEvent. V této metodě si pořídíme QPainter, což je obsáhlý objekt s obsáhlou dokumentací, jehož metodami kreslíme obsah widgetu.

Jak to vypadá, si ukážeme na příkladu:

from PySide2.QtWidgets import \
        QApplication, QWidget
from PySide2.QtGui import QPainter, QColor, \
        QPen, QBrush
from PySide2.QtCore import Qt

import sys
app = QApplication(sys.argv)

class Sun(QWidget):
    beams = 42
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.show()

    def paintEvent(self, event):
        # Rozměry widgetu, do kterého kreslíme
        w = self.width()
        h = self.height()

        # Poloměr sluníčkového kolečka
        r = min(w, h) / 4

        # Kreslič sám
        painter = QPainter(self)
        painter.setRenderHint(
                QPainter.Antialiasing)

        # Modré pozadí
        painter.setBrush(QColor(128, 192, 255))
        painter.setPen(QPen())
        painter.drawRect(0, 0, w, h)

        # Žluté svítíčko tlustou žlutou čárou
        painter.setBrush(QBrush())
        painter.setPen(QPen(QColor(220, 180, 0),
                                3))

        # Používáme transformaci souřadné
        # soustavy, kdy si nulu dáme doprostřed
        # widgetu
        painter.translate(w/2, h/2)
        painter.drawEllipse(-r, -r, r*2, r*2)

        # Paprsky
        for i in range(self.beams):
            # Nakreslíme paprsek
            painter.drawLine(0, r, 0, r*2)

            # A pootočíme soustavu souřadnic
            painter.rotate(360/self.beams)

s = Sun()
app.exec_()

Nakreslili jsme nejprve modrý obdélník, přes něj žluté kolečko a žluté čáry. Kreslíme tak, že si nejprve vybereme pero (tím se kreslí čára) a štětec (tím se maluje vnitřek oblasti). Přitom jsme si posouvali souřadnou soustavou, jak bylo zrovna potřeba. Tato posunutí, rotace apod. platí pouze pro tento jeden QPainter a při příštím kreslení si pořídíme zase nový, čistý kreslič s nulou vlevo nahoře.

Pojďme si tedy vyzkoušet, jak widget ovládat, a to především myšem. Máme na výběr několik metod – můžeme implementovat:

My si to ukážeme na jednoduchém příkladu, ve kterém levé myšítko zvýší počet paprsků a pravé myšítko počet paprsků zase sníží.

    def mousePressEvent(self, event):
        # Obsluha myšítkových událostí
        btn = event.button()
        print(btn)
        if btn == Qt.MouseButton.LeftButton:
            self.beams += 1

        if btn == Qt.MouseButton.RightButton \
                and self.beams > 0:
            self.beams -= 1

        # Vyžádáme si překreslení
        self.update()

Metodou button události QMouseEvent zjistíme, které tlačítko ji vyvolalo (u pohybu myše žádné), metodou buttons zjistíme, která jsou zrovna stisknutá.

Pokud je potřeba widget překreslit, zavoláme na něj nakonec update, což vyvolá právě událost překreslení, kdy se celý widget kreslí od znova.

Danger!Není vždy třeba překreslovat celý widget. Všimněte si nepoužitého argumentu event události paintEvent. To je objekt typu QPaintEvent, ve kterém je uložená informace o tom, kterou oblast je třeba překreslit. Pokud je kreslení náročnější na čas, může se to hodit využít. Pokud však překreslíte víc, nic se nestane.

Úkol 1 [3b]

Upravte obsluhu myšítek tak, aby se po jedné vteřině držení myšítka začal zvyšovat či snižovat počet paprsků o jeden každých 250 milisekund, dokud uživatel myšítko nepustí.

Úkol 2 [2b]

Připište metodu mouseMoveEvent (a upravte vykreslování) tak, aby se sluníčko schovalo (nevykreslilo), pokud najedete kurzorem nad jeho střed. Pro tento úkol se budou hodit metody x a y, případně pos, kterými zjistíme relativní pozici myšítka ve widgetu. Také je třeba zapnout si u widgetu setMouseTracking(True), jinak se event vyvolá jenom při stisknutém myšítku.

Danger!Pokud v rámci obsluhy událostí potřebujete nějak měřit vzdálenost ujetou kurzorem, třeba chcete napsat drag-and-drop ovládání, může se stát, že widget mezitím změnil svoji polohu nebo velikost. Proto si můžete říct i o pozici kurzoru v kontextu celé obrazovky metodou globalPos.

Píšeme vlastní View

Když už víme, jak si můžeme kreslit vlastní widgety, pořídíme si i náš vlastní View. Držte si klobouky, jedeme s kopce. Zdědíme QAbstractItemView a máme hned několik problémů.

Především se jedná o scrollovatelnou oblast (což je milé, ale dá nám trochu víc práce to zvládnout). Takže musíme kvůli zobrazování implementovat více metod, než kdybychom zdědili widget. Nicméně ukáže se (v poslední sérii), že do View se dá připojit Delegate na ovládání jednotlivých prvků. Proto budeme trpěliví a všechny metody poctivě implementujeme. Tedy ne všechny metody, jenom ty, které nás nějak ovlivňují. V poslední sérii to budeme muset udělat pořádně.

Taktéž už nyní nekreslíme do samotného widgetu, ale do self.viewport(), což je subwidget, který je obalený scrollovátky.

Pojďme se ale zatím podívat na to, jak takový vlastní View vlastně může vypadat.

Zobrazovátko ukazuje (poměrně hloupým a jednoduchým způsobem) pozice chodců a aut na chodníku a silnici. Mimochodem, v protokolu serveru přibylo jedno pole na řádku cestovatele, které říká, ze které strany oblasti dotyčný vstupuje.

Celé psaní View je vlastně poměrně jednoduché – pouze obsluhujeme události – jen je těch událostí a požadavků poměrně hodně. Důkladně si prostudujte přiložený kód, je komentovaný.

V této sérii je důležité připomenout, že máme webové fórum, na kterém je možné pokládat otázky. Je možné, že se vám tentokrát bude hodit.

A nyní přichází na řadu vaše úkoly, kterak zobrazovátko vylepšit.

Úkol 3 [2b]

Zařiďte, aby se auta nemotala mezi chodci, ale aby způsobně podjížděla pod mostem. Nyní se vykreslují, jako by se jednalo o úrovňové křížení.

Úkol 4 [2b]

Naučte chodce chodit po pravé straně chodníku, přičemž polohu mezi pravým okrajem chodníku a jeho středem zvolte náhodně při vstupu chodce do oblasti.

Nyní už umíme spoustu zajímavých věcí a můžeme si dovolit úkol, který shrnuje i zkušenosti z předchozích sérií.

Úkol 5 [6b]

Rozšiřte silnici v obou směrech na alespoň dva jízdní pruhy a naučte auta předjíždět. Auto, které se do provozu nevejde ani ve dvou pruzích, zpomalte na rychlost vozu před ním, dokud vůz před ním neuhne.

Tento úkol bude pravděpodobně vyžadovat výrazné úpravy modelu. Dobře si rozmyslete, jak to udělat tak, abyste příliš neplýtvali procesorovým časem při přepočtech poloh vozidel.

Stejně jako v minulých sériích je možno odevzdat více podúloh v jednom programu. To je v této sérii vše, v příštím, posledním dílu seriálu o Qt se konečně podíváme na to, jak Model ovládat pomocí Delegates.

Maria Matějka

Řešení