3. Pofidérnejšie kasíno

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Prefixovi na

Po tom, ako ste odhalili chyby v kasíne z minulej série a takmer ste nás doviedli do krachu, naši bezpečnostní experti spravili v kasíne mnoho zmien. Už nestačí uhádnuť správny tip len raz, ale z daného počtu pokusov musíte uhádnuť aspoň nejaký minimálny počet (pre každú hru iný). Zároveň vám už nehovoríme, aké čísla naše kasíno vygenerovalo a ani neprezradíme, ako presne je kasíno implementované.

Ďalšie bezpečnostné opatrenia zahŕňajú to, že do kasína už nemôžete vstupovať osobne, ale posielate tam svojho robota, ktorý bude hrať za vás.

Úloha

V kasíne sú tri hry označené A, B, C. Princíp fungovania týchto hier je rozpísaný na konci tohto zadania. Vašim cieľom je vymyslieť a naprogramovať stratégiu, ktorá bude schopná správne uhádnuť dosť veľa tipov v danej hre.

Jednotlivé hry môžete hrať cez netcat, podobne ako v predošlej podúlohe, avšak teraz za hranie cez netcat nezískavate body. Slúži to len na to, aby ste si mohli vyskúšať, ako jednotlivé hry fungujú. Návod na inštaláciu progamu netcat nájdete v zadaní predošlej série. Spustite ho nasledovnými príkazmi:

-- Linux / Mac OS
nc 158.195.16.154 9948
-- Windows
cd cesta_k_netcatu
nc.exe 158.195.16.154 9948

Akonáhle sa s hrami zoznámite a rozmyslíte si, ako budete hry hrať, môžete vašu stratégiu naprogramovať. Tu si môžete stiahnuť ukážové programy C++ alebo v Pythone, ktoré sme pre vás pripravili, aby ste sa nemuseli trápiť komunikáciou s kasínom. Použitie týchto šablón je dobrovoľné, môžete si kľudne vytvoriť kompletne vlastné programy. Ak by ste chceli, aby sme vám vytvorili ukážkové programy aj v inych programovacích jazykoch, napíšte Prefixovi.

Na odovzdanie programu nemusíte vyriešiť všetky podúlohy, ani ich nemusíte riešiť v poradí. Kľudne odovzdajte aj program, ktorý rieši len časti niektorých podúloh. Za každú hru môže program získať 3 body, jeden za každý level. Level je len skupina vstupov, pre ktoré platí nejaké obmedzenie (napríklad, že čísla na vstupe sú menšie ako 5).

Dôležité upozornenie: do vysledného bodovania sa počíta len posledný odovzdaný program. To znamená, že ak aj odovzdáte program, ktorý úspešne rieši hru A, ale ako posledný odovzdáte program, ktorý rieši iba hru B, tak sa vám zarátajú body len za hru B. Preto sa uistite, že ako posledný pred koncom série ste odovzdali program, ktorý rieši všetky podúlohy, ktoré chcete odovzdať. Program môžete odovzdať najviac stokrát, ak by ste chceli odovzdať viackrát, najprv sa ozvite Prefixovi. Pre úplnosť doplníme, že beh vášho programu je obmedzený na 2 sekundy, čo by vás ale nemalo výrazne obmedzovať, lebo v skutočnosti stačí oveľa kratší čas.

Okrem programov odovzdajte aj popis riešenia. Popisy všetkych hier, ktoré ste riešili odozvdajte spoločne v jednom súbore, pretože opravovatelia uvidia len posledný odovzdaný súbor. Do popisu stručne napíšte, ako ste jednotlivé hry riešili. Aké úvahy a výpočty vás doviedli ku tej stratégii, ktorú ste nakoniec naprogamovali? Prečo váš program tipoval práve tie hodnoty aké tipoval?

V hrách A (kocky) pre \(n = 6\) a B (dvere) pre \(n=5\) a \(k=2\) navyše vypočítajte, aká je pravdepodobnosť uhádnutia správnej hodnoty v jendom kole (t.j. keby ste hrali veľmi veľa tipov, akú časť z nich by ste priemerne uhádli)? Ak túto pravdepodobnosť správne spočítate aj v hre C (mince) pre \(n = 7, c_1 = 1, c_2 = 2, m_1 = 3, m_2 = 4\), môžete získať jeden bonusový bod.

Pravdepodobnosť, nemusíte vypočítať ručne a môžete na jej výpočet použiť program. V takom prípade skopírujte zdrojový kód použitého programu do popisu riešenia. Nestačí napísať výsledok, chceme vidieť aj postup, výpočet alebo program, ktorý vás k výsledku doviedol. V každej hre môžete za popis získať najviac 2 body.

Ak budete mať akékoľvek otázky ohľadom úlohy, toho ako funguje netcat, Python, C++, samotné odovzdávanie alebo budete chcieť spraviť viac ako sto submitov, napíšte Prefixovi. Rád vám pomôže.

Hra A – kocky (5 bodov)

V kasíne máme štyri \(n\)-steny. Každý \(n\)-sten má na stranách čísla od \(1\) po \(n\) . Ak má napríklad 7 stien, tak má na stranách čísla od 1 po 7. Môžete si to predstaviť ako hracie kocky s \(n\) stranami. \(T\)-krát hodíme týmito štyrmi \(n\) stenami a vy si máte po každom hode tipnúť súčet čísel, ktoré na týchto \(n\) stenoch padli. Následne vyhodnotíme, ako dobre sa vám darilo a podľa toho vám pridelíme body.

Upresnenia: Na prvom riadku vstupu je písmeno A, na druhom číslo \(n\) (počet stien) a na treťom \(T\) (počet tipov). V prvom leveli platí, že \(n = 6\). V druhom leveli sme boli zhovievaví, a netreba uhádnuť až tak veľa tipov. Počet stien však môže byť hocikoľko od 6 do 10. V treťom leveli musíte hádať najlepšie ako viete a \(n\) leží medzi 6 a 10.

Príklad:

Input:

A
6
5

Output:

1
1
1
1
1

Poznámka, takýto výstup by dostal 0 bodov, pretože na 4 kockách padne vždy súčet aspoň 4. Ak tipnete 1, neuhádnete.

Hra B – dvere (5 bodov)

V kasíne máme \(n\) dverí, za práve jednymi je schovaná výhra. Najprv vy ukážete na jedny dvere a potom my spomedzi zvyšných dverí otvoríme \(k\), za ktorými nie je schovaná výhra. Potom je vašou úlohou tipnúť dvere s výhrou (môžte tipovať aj tie, na ktoré ste ukázali ako prvé). Takto si zahráme \(T\) hier, pričom na začiatku každej hry náhodne vyberieme dvere s výhrou (každé dvere majú na začiatku rovankú šancu byť výherné) a budeme počítať, koľkokrát sa vám ich podarí uhádnuť.

Upresnenia: Na prvom riadku vstupu je písmeno B, na druhom sú čísla \(n\) a \(k\) a na treťom riadku je číslo \(T\) (počet hier). Následne odohráme postupne \(T\) hier, v každej najskôr váš program vypíše číslo (číslo dverí), my vám napíšeme zoznam \(k\) dverí, ktoré sú bez výhry a váš program tipne, za ktorými dverami je výhra.

V prvom leveli platí, že \(n = 3\), \(k = 1\), v druhom leveli \(3\leq n\leq 8\), \(k = 1\). V treťom leveli \(3\leq n\leq 10\), \(1\leq k\leq n-2\).

Príklad:

Input:

B
5 2
1
1 2

Output:

5
2

Tentokrát mala hra len jedno kolo, program ukázal na piate dvere, dozvedel sa, že v dverách 1 a 2 sa nič nenachádza. Napriek tomu tipol druhé dvere a teda opäť nevyhral.

Hra C – mince (5 bodov + bonus)

V kasíne máme \(n\) mincí a každá má na jednej strane číslo \(c_1\) a na druhej \(c_2\). Zároveň si vyberieme nejaké čísla \(m_1\) a \(m_2\). Hodíme všetkými mincami a sčítame čísla na vrchných stranách (mince sú férové a nepadajú na hranu). Prezradíme vám aký je zvyšok súčtu po delení \(m_1\) a spýtame sa vás na zvyšok súčtu po delení \(m_2\). Inak povedané, ak si označíme súčet \(s\), tak vám prezradíme \(s \% m_1\) a vy musíte uhádnuť \(s \% m_2\).

Upresnenia: Na prvom riadku vstupu je písmeno C, na druhom sú čísla \(n, c_1, c_2, m_1, m_2\) a na treťom riadku je číslo \(T\) (počet hier). Následne odohráme postupne \(T\) hier, v každej vám povieme prvý zvyšok a vy tipnete druhý zvyšok.

V prvom leveli platí, že \(n = 1\), v druhom leveli \(n = 5\) a zároveň sme menej prísni v tom, koľkokrát musíte správne tipnúť odpoveď. V treťom leveli \(1\leq n\leq 10\), a treba uhádnuť čo najviac tipov. Vo všetkých troch leveloch platí, že \(1\leq c_1, c_2, m_1, m_2\leq 10\)

Príklad:

Input:

C
2 3 1 4 5
2
2
0

Output:

1
4

Hodíme dvoma mincami, ktoré majú na stranách čísla 1 a 3. V prvom pokuse sa program dozvedá, že zvyšok súčtu po delení 4 je 2. To znamená, že súčet je 2 alebo 6, nevie však, čo z toho. Keďže su obe rovnako pravdepodobné, tipne si, že súčet bol 6 a teda vypíše \(6 \% 5 = 1\). V druhom prípade má šťastie, zvyšok po delení 4 bol 0, takže program vie, že súčet bol 4. Vypíše teda \(4 \% 5 = 4\)