Pojmy

Nasledovný zoznam obsahuje základné pojmy, s ktorými sa v zadaní stretávame:

• Závodná dráha. Jednorozmerné pole zložené z políčok, na ktorých môže byť umiestnené pretekajúce auto alebo vchody/východy z tunelov.
• Pozície hráčov na závodnej dráhe. Pozície (indexy v poli) jednotlivých hráčov na dráhe budeme označovať nasledovne:
  • $h$ - označenie hráča na ťahu
  • $o$ - označenie oponenta, t.j. hráča, ktorý nie je na ťahu
  • $P_{h,t}$ - pozícia hráča na ťahu, pred vykonaním ťahu.
  • $P_{h,t+1}$ - pozícia hráča na ťahu, po vykonaní ťahu.
  • $P_{o,t}$ - pozícia oponenta, pred vykonaním ťahu.
  • $P_{o,t+1}$ - pozícia oponenta, po vykonaní ťahu.
• Tunel. Umožňuje teleportáciu pretekajúceho auta z jedného miesta dráhy na druhé. Tunel sa skladá z 2 častí: vchod a východ. Vchodom rozumieme políčko na dráhe, na ktoré keď vstúpi pretekajúce auto, tak sa zjaví na opačnom konci tunela, t.j. jeho východe.
• Hracie kocky $R_1$ a $R_2$. Závod prebieha v ťahoch, počas ktorých sa pretekajúce autá striedajú. Hráč, ktorý je na ťahu hádže 2 virtuálnymi kockami $R_1$ a $R_2$. Na každej kockej padne náhodné číslo v intervale $\langle 1,6 \rangle$. Na základe súčtu hodených čísiel na kockách sa rozhodne o tom, čo pretekajúce auto vykoná ďalej (posun vpred na dráhe, vchod do tunela a pod.).
• Eliminácia oponenta. Predstavuje situáciu počas pretekov, kedy pretekajúce auto A dopadne na políčko závodnej dráhy, ktoré je obsadené pretekajúcim autom B. Následne je auto B postavené mimo dráhy a musí začať pretekať od začiatku.

Závodná dráha

Na závodnú dráhu sa môžeme pozerať ako na postupnosť políčok, po ktorých sa pretekári pohybujú. Dĺžku závodnej dráhy $n$ určuje používateľ z klávesnice. Maximálna dĺžka závodnej dráhy je $N_{max}=100$ políčok. Auto, ktoré ako prvé prekoná dĺžku trate sa stáva víťazom, t.j. jeho index na závodnej dráhe je viac než $n-1$. Políčka závodnej dráhy môžeme rozdeliť na 3 typy:

• Prázdne políčko - predstavuje bežné miesto na dráhe, kde môže byť umiestnené pretekajúce auto a nemá iný špeciálny význam.
• Vchod do tunela - predstavuje miesto na dráhe, na ktoré keď pretekajúce auto vstúpi, dôjde k teleportácii na opačný koniec tunela.
• Východ z tunela - toto miesto na dráhe predstavuje cieľ teleportácie v rámci tunela.

Kontrola vstupných parametrov

Po zadaní vstupných parametrov musí program vyhodnotiť ich platnosť. V prípade, že niektorý zo vstupných parametrov je neplatný, program musí ukončiť svoju činnosť bez akéhokoľvek výstupu a vrátiť príslušnú návratovú hodnotu. Treba ošetriť nasledovné situácie:

• Pre inicializačnú hodnotu generátora $s$ musí platiť $s \gt 0$.
• Dĺžka závodnej dráhy $n$ musí byť v intervale $\langle N_{min},N_{max} \rangle$. V zadaní je nutné použiť hodnoty $N_{min}=10$ a $N_{max}=100$.
• Počet tunelov na dráhe musí spĺňať podmienku $t \times 2 \leq \frac{n}{2}$.

V prípade, že niektorá z vyššie uvedených podmienok nie je splnená, program skončí bez akéhokoľvek výstupu s návratovou hodnotou 1 (návratová hodnota funkcie main).

Rozmiestnenie tunelov

Po kontrole vstupných parametrov sa rozmiestnia tunely na dráhe. Tunely ručne rozmiestni používateľ zadávaním čísel z klávesnice. Počet rozmiestnených tunelov je $t$. Používateľ zadáva jednotlivé tunely načítaním dvojice čísel $\{enter,exit\}$.

• Parameter $enter$ predstavuje index políčka závodnej dráhy, kde sa nachádza vstup do tunela.
• Parameter $exit$ predstavuje index políčka, na ktorom sa nachádza východ z tunela.

Pri zadávaní tunelov musia byť splnené tieto podmienky:

• Vchod a východ tunela nesmie byť umiestnený na prvom (index 0) a poslednom políčku dráhy (index $n-1$).
• Vchod a východ tunela sa nesmie nachádzať mimo závodnej dráhy, t.j. záporné indexy alebo indexy presahujúce platný rozsah dráhy.
• Každý tunel musí mať unikátny vchod, t.j. žiadne dva tunely nesmú mať rovnaký index vchodu do tunela.
• Východ tunela nesmie byť zároveň vchodom do iného tunela (zamedzíme tak slučkám a viacnásobnej teleportácii).
• Vchod a východ tunela nesmú mať rovnaký index.

V prípade nesplnenia, niektorej z vyššie uvedených podmienok musí program skončiť bez akéhokoľvek výstupu a vrátiť hodnotu 2 (návratová hodnota funkcie main).

Presmerovanie štandardného vstupu v termináli

Pri testovaní vašich programov je vhodné si automatizovať zadávanie vstupných parametrov pomocou presmerovania štandardného vstupu z textového súboru. Presmerovanie dosiahneme použitím operátora < a následným spustením programu v tvare ./program < file.txt. Do textového súboru su napíšeme všetky vstupné parametre programu a pozície tunelov a následne program spustíme z terminálu spôsobom vizualizovaným na obrázku pod textom.

Vstup na závodnú dráhu

Na začiatku závodu je pretekár mimo dráhy. Vtedy budeme jeho pozíciu označovať hodnotou -1. Aby mohol pretekár vstúpiť na závodnú dráhu a začať pretekať (resp. nastaviť svoje auto naspäť na začiatok dráhy po eliminácii), musí v rámci jeho ťahu hodiť kockami súčet čísel, pre ktorý platí $R_1 + R_2 \gt 7$. Ak splní túto podmienku, tak si môže svoje auto umiestniť na štartovaciu pozíciu, t.j. políčko s indexom $R_1 + R_2 - 7$.

Ťah

Ak hráč má v rámci jeho ťahu auto umiestnené na závodnej dráhe, tak môže nastať jeden z nasledovných prípadov.

• Špeciálny prípad 1. Nastáva ak platí $P_{h,t} \lt P_{o,t}$ a súčasne $R_1 + R_2 = 12$.
  Špeciálny prípad 2. Nastáva ak platí $P_{h,t} \gt P_{o,t}$ a súčasne $R_1 + R_2 = 2$.
  
  V oboch prípadoch si autá pretekárov vymenia svoje pozície. Špeciálne prípady nastávajú iba ak sú obe autá na závodnej dráhe.
  
  

  \begin{equation} \begin{split} P_{h,t+1} = P_{o,t}\\ P_{o,t+1} = P_{h,t} \end{split} \end{equation}

  
  
  
  Obrázok 6: Vizualizácia špeciálneho prípadu 1 a 2.
  
  
  
• Posun na dráhe. Ak nenastane ani jeden z vyššie uvedených špeciálnych prípadov, tak dochádza k posunu auta po dráhe o $d$ políčok dopredu. Posun vypočítame ako $d = max(R_1,R_2)$, t.j. použije sa väčšie z dvoch čísel. Nová pozícia hráča po vykonaní ťahu bude vyjadrená vzťahom (2). Po vykonaní posunu je nutné ešte overiť, či nedôjde k teleportácii alebo eliminácii oponenta.
  
  

  \begin{equation} P_{h,t+1}=P_{h,t}+d \end{equation}

  
  
  
  Obrázok 7: Vizualizácia posunu na dráhe.

Teleportácia cez tunel

Keďže máme na závodnej dráhe rozmiestnené tunely, môže počas závodu dôjsť k teleportácii pretekára. Teleportácia nastáva, keď auto hráča, ktorý je na ťahu vstúpi na políčko dráhy, ktoré je označené ako vstup do tunela (t.j. keď $P_{h,t+1}$ sa zhoduje s indexom niektorého z vchodov rozmiestnených tunelov). V takomto prípade bude pretekár teleportovaný z políčka vchodu do tunela na políčko východu z tunela. Po teleportácii bude platiť, že $P_{h,t+1}$ bude rovné indexu políčka, kde sa nachádza východ z tunela.

Poznámka: možnosť teleportácie treba vyšetriť po každej zmene pozície pretekára na dráhe, t.j. pri štandardnom posune o $d$ políčok alebo aj pri vstupe pretekára na začiatok závodnej dráhy.

Eliminácia oponenta

Počas závodu môže nastať situácia, kedy je auto oponenta eliminované (postavené mimo dráhu) autom hráča, ktorý je práve na ťahu. K eliminácii dochádza vtedy, keď auto hráča na ťahu narazí do auta oponenta, t.j. keď platí $P_{h,t+1} = P_{o,t}$. Po eliminácii sa auto oponenta môže opäť zapojiť do pretekov po splnení podmienok pre vstup na závodnú dráhu, ktoré sú opísané v časti Vstup na závodnú dráhu.

Poznámka: možnosť eliminácie oponenta treba vyšetriť po každej zmene pozície pretekára na dráhe, t.j. pri štandardnom posune o $d$ políčok alebo pri vstupe pretekára na závodnú dráhu. Nezabudnite, že k eliminácii oponenta môže dôjsť aj po teleportácii, t.j. ak auto oponenta stojí na políčku, kde sa nachádza východ z tunela.

Vyhodnotenie víťaza

Víťazom závodu sa stáva hráč, ktorého auto ako prvé prekoná dĺžku závodnej dráhy, t.j. platí $P_{h,t+1} \geq n$.

Záverečná štatistika

Po skončení závodu sa zobrazí štatistika návštevnosti jednotlivých políčok závodnej dráhy. Hodnota návštevnosti políčka hovorí o tom, koľkokrát bolo dané políčko počas závodu navštívené obidvomi pretekajúcimi autami. Na začiatku závodu má každé políčko závodnej dráhy hodnotu návštevnosti 0.

Situácie, kedy započítame návštevu políčka závodnej dráhy:

• Pri vstupe pretekára na závodnú dráhu. Vtedy sa zvýši o 1 návštevnosť políčka, na ktoré je po vstupe na dráhu umiestnené auto pretekára.
• Pri špeciálnych prípadoch 1 a 2. Vtedy sa zvýši o 1 návštevnosť políčka hráča na ťahu a taktiež políčka oponenta.
• Pri štandardnom posune pretekára o $d$ políčok. Vtedy sa zvýši o 1 návštevnosť políčka po vykonaní ťahu, t.j. políčka s indexom $P_{h,t+1}$.
• Pri teleportácii. Vtedy sa zvýši o 1 návštevnosť políčka s východom z tunela. V tomto prípade nezvyšujeme návštevnosť políčka, na ktorom sa nachádza vchod do tunela.
• Pri eliminácii oponenta. Vtedy sa zvýši o 1 návštevnosť políčka, na ktorom stojí auto oponenta.

Záznam zo seminára č. 4 (8. marec 2022)