Zadanie

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\)

Táto úloha bola zameraná na pravdepodobnosť – v každej podúlohe chceme tipovať tak, aby sme mali čo najväčšiu šancu na výhru, a v niektorých bolo navyše treba v popise ukázať, prečo to tak je.

Podúloha a)

V tejto podúlohe bolo dôležité všimnúť si, že nie všetky čísla padajú rovnako často. Prečo?

Predstavme si, že hádžeme štyrmi šeststennými kockami. Na to, aby padol súčet \(4=1+1+1+1\), musí na každej kocke padnúť jednotka. Sú však štyri možnosti, ako môže padnúť súčet \(5 = 1+1+1+2 = 1+1+2+1 = 1+2+1+1 = 2+1+1+1\), každá z týchto možností je rovnako pravdepodobná, ako že padne súčet 4. Pre súčet 6 máme dokonca desať možností.

Vo všeobecnosti, má každá kocka \(n\) možností, ktoré môžu padnúť a teda logicky štyri kocky majú \(n\cdot n\cdot n\cdot n = n^4\) možností čo môžu padnúť. Každá z týchto \(n^4\) možností je rovnako pravdepodobná a vieme si tiež pre každý súčet \(S\) spočítať, koľkými možnosťami vieme tento súčet dosiahnuť.

Aby sme to nemuseli počítať ručne, napíšeme si program, ktorý to spočíta za nás.

pocet_stien = int(input())
kolko_padne = [0 for i in range(pocet_stien*4+1)]
for a in range(1,pocet_stien+1):
    for b in range(1,pocet_stien+1):
        for c in range(1,pocet_stien+1):
            for d in range(1,pocet_stien+1):
                kolko_padne[a+b+c+d] += 1
for i in range(4, pocet_stien*4+1):
    print(i, kolko_padne[i])

Napríklad pre \(n = 6\), máme dokopy \(6^4 = 1296\) možností, ako môžu jendotlivé kocky padnúť. Takto vyzerá tabuľka, keď tieto možnosti zoskupíme podľa súčtu padnutých hodnôt. Na prvom riadku tabuľky je súčel \(S\), a na druhom riadku počet možností, koľkými daný súčet mohol padnúť.

\(S\) 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
\(P\) 1 4 10 20 35 56 80 104 125 140 146 140 125 104 80 56 35 20 10 4 1

Z tohoto vidíme, že 14 vážne padá najčastejšie, a vieme aj vypočítať pravdepodobnosť, že padne. Padne \(146\)-krát z \(1296\) prípadov, a teda pravdepodobnosť je \(\frac{146}{1296}\), a to je približne \(0.11\), teda \(11\%\).

Ostatné prípady vieme vyriešiť podobne. Keďže \(n\) je maximálne 10, vieme si rýchlo overiť, že pre každé \(n\) je najväčšia pravdepodobnosť práve v strede, teda najčastejšie padá hodnota \(2(n+1)\).

Pokiaľ sme boli leniví písať štyri forcykly, mohli sme jednoducho spraviť program, ktorý miliónkrát hodí štyrmi kockami, čím by sme tiež zistili, že \(2(n+1)\) padá najčastejšie. Nepomohlo by nám to však v teoretickej časti, lebo by sme nevedeli presne vyjadriť pravdepodobnosť tohto súčtu.

from random import randint
pocet_stien = int(input())
kolko_padne = [0 for i in range(pocet_stien*4+1)]
for i in range(1000000):
    kolko_padne[sum([randint(1, pocet_stien) for _ in range(4)])] += 1
for i in range(4, pocet_stien*4+1):
    print(i, kolko_padne[i])

Podúloha b)

Toto je zovšeobecnenie celkom známeho problému Monty Hall. Ukazuje sa, že sa nám vždy oplatí v druhom kole zmeniť dvere. Prečo je to tak, vieme jednoducho určiť tym, že si pre každé dvere spočítame pravdepodobnosť, že je za nimi výhra.

Predpokladajme, že máme \(n\) dverí. Takže keď si náhodne vyberieme dvere, pravdepodobnosť, že sme vybrali tie správne je \(\frac{1}{n}\). Potom nám otvorí vedúci hry \(k\) dverí, čím nijako neovplyvní, či bola výhra za prvými vybratými dverami. Šanca, že sme ich vybrali správne je stále len \(\frac{1}{n}\).

Zároveň však o \(k\) dverách vieme, že za nimi nie je výhra, inak povedané pravdepodobnosť, že za nimi je výhra, je 0. Vieme, že za nejakými dverami výhra musí byť, pretože súčet pravdepodobností pre všetkých \(n\) dverí dohromady je \(1\).

Ostalo nám \(n-k-1\) dverí (všetky mínus otvorené mínus náš prvý typ), pre ktoré súčet pravdepodobností musí byť \(1 - k\cdot 0 - \frac{1}{n}\) (všetky mínus otvorené mínus náš prvý tip). Každé z týchto \(n-k-1\) dverí sú pre nás nerozlíšiteľné, teda majú z nášho pohľadu rovnakú pravdepodobnosť na výhru. Táto pravdepodobnosť je celková pravdepodobnosť predelená počtom dverí, číže

\[P_{n,k} = \frac{1 - \frac{1}{n}}{n-k-1}\] \[P_{n,k} = \frac{n-1}{n(n-k-1)}\]

To je viac ako \(\frac{1}{n}\) (ľahko porovnáme vzorky, ak ich prenásobíme spoločným menovateľom \(n(n-k-1)\)). Tak sme dokázali, že vždy je lepšie v druhom kole svoje rozhodnutie zmeniť a teda vybrať iné dvere ako sme vybrali v prvom.

Možností ako riešenie implementovať bolo viacero. Najjednoduchšie je vybrať si vždy najprv dvere s číslom 1 a potom postupne prechádzať dvere s vyššími číslami, až kým nenájdeme také, ktoré neboli otvorené (pozri implementáciu v C++ na konci vzorového riešenia). Dalo sa však aj postupovať tak, že si vytvoríme množinu dverí bez prvých, naraz odstránime z tejto množiny čísla, ktoré sme videli na vstupe a vypíšeme náhodný prvok zostávajúcej množiny (pozri implementáciu v Pythone na konci vzorového riešenia).

Pre \(n = 5\), \(k = 2\) je pravdepodobnosť, že náš program uhádne správne dvere \(\frac{5-1}{5(5-2-1)} = \frac{4}{10} = 0.4\).

Podúloha c)

Túto podúlohu vyriešime veľmi podobne ako podúlohu a), ale namiesto toho, aby sme našli správnu odpoveď dopredu, bude ju hľadať sám program po tom ako dostane vstupné dáta (počet mincí, hodnoty mincí a zvyšky).

Taktiež nechceme spočítať jeden najčastejší druhý zvyšok, ale chceme ho nájsť osobitne pre každý možný prvý zvyšok. V podstate chceme spočítať dvojrozmernú tabuľku (dvojrozmerné pole) P[][], rozmerov \(m_1 \times m_2\), pričom na políčku P[i][j] bude počet možností, ako hodmi \(n\) mincí dosiahneme zvyšok \(i\) po delení \(m_1\) a \(j\) po delení \(m_2\).

Ak nás potom bude zaujímať, aký je najčastejší druhý zvyšok pre prvý zvyšok \(i\), stačí nájsť najväčšiu hodnotu v \(i\) tom riadku tabuľky.

Ako čo najjednoduchšie vyskúšať všetky možnosti? Jedna možnosť je použiť rekurziu, ako je to v C++ riešení na konci. Aké sú možnosti hodu 0 mincami? No ak ničím nehodíme, dostaneme súčet nula, takže máme jednu mužnosť. Aké sú možnosti pri hode \(n\) mincami, pre \(n>0\)? No buď padne \(c_1\), alebo \(c_2\) a pre obe možnosti potrebujeme vyskúšať, ako sa dá hodiť \(n-1\) mincami.

Druhá možnosť, ako sa dá vidieť v Pythonovom riešení, je postupne prejsť všetky čísla od \(0\) po \(2^n-1\). Ak si tieto čísla zapíšeme v binárnej sústave, dostaneme všetky možnosti, ako môže vyzerať posledných \(n\) bitov. Potom nám už len stačí namapovať si – ak \(i\)-ty bit od konca je 0, padla na \(i\)-tej minci prvá strana, inak padla druhá strana. Vo forcykli prejdeme všetky tieto čísla, každé si prevedieme na postupnosť hodov, spočítame jej súčet a jeho zvyšky po delení \(m_1\) a \(m_2\), a na pozíciu v poli pripočítame 1.

Vytváranie poľa \(P\) je relatívne pomalé – či už ide o rekurziu, alebo musíme prejsť všetky čísla od \(0\) po \(2^n-1\) a pre každé prejsť \(n\) bitov tohoto čísla. Z tohoto dôvodu ho spočítame len raz, a potom dokola využívame.

Bonus: Pre \(n=7\), \(c_1=1\), \(c_2=2\), \(m_1=3\), \(m_2=4\) dostaneme takúto tabuľku P.

21 21 0 0
0 7 35 1
7 0 1 35

Z tabuľky vieme vyčítať, že v 42 zo 128 prípadoch je prvý zvyšok 0. Vtedy máme \(\frac{21}{42} = 0.5\) šancu, že uhádneme. V pokiaľ je prvý zvyšok 1 alebo 2 (oba tieto prípady nastávajú s pravdepodobnosťou \(\frac{43}{128}\)) máme šancu \(\frac{35}{43}\) uhádnuť. Celková šanca, že uhádneme je \(\frac{21}{42}\cdot\frac{42}{128} + \frac{35}{43}\cdot\frac{43}{128} +\frac{35}{43}\cdot\frac{43}{128} = \frac{21+35+35}{128} = \frac{91}{128}\), čo je približne \(0.71\), teda až \(71\%\). A to je výrazne väčšia šanca, ako keby sme tipovali zvyšok náhodne.

from random import randint, choice

def tipniA(pocet_stien):
    print(2*pocet_stien+2, flush=True)

def tipniB(pocet_dveri, kolko_otvorim):
    print(1)
    prazdne_dvere = [int(x) for x in input().split()]
    ostatne = list(set(list(range(2,pocet_dveri+1))) - set(prazdne_dvere))
    print(choice(ostatne), flush=True)

pripraveneP = None
def pripravP(n, hodnota1, hodnota2, modulo1, modulo2):
    global pripraveneP
    if pripraveneP: return pripraveneP
    pripraveneP = [[0 for i in range(modulo2)] for j in range(modulo1)]
    for mask in range(2**n):
        hodnota = 0
        for i in range(n):
            if (1<<i) & mask: hodnota += hodnota1
            else: hodnota += hodnota2
        pripraveneP[hodnota % modulo1][hodnota % modulo2] += 1
    return pripraveneP

def tipniC(n, hodnota1, hodnota2, modulo1, modulo2):
    pocty = pripravP(n, hodnota1, hodnota2, modulo1, modulo2)
    moznosti = pocty[int(input())]
    print(moznosti.index(max(moznosti)), flush=True)

hra = input()
parametre_hry = [int(x) for x in input().split()]
pocet_tipov = int(input())
tipovacia_funkcia = {'A':tipniA, 'B':tipniB, 'C':tipniC}[hra]
for t in range(pocet_tipov):
    tipovacia_funkcia(*parametre_hry)
#include <iostream>
#include <vector>
using namespace std;

void hrajA() {
    int n, testov, najlepsia = 0;
    cin >> n >> testov;
    // Zistim si ako casto pada ktora moznost
    vector<int> pocetMoznosti(4*n+5, 0);
    for(int a=1; a<=n; ++a)
        for(int b=1; b<=n; ++b)
            for(int c=1; c<=n; ++c)
                for(int d=1; d<=n; ++d)
                    pocetMoznosti[a+b+c+d]++;
    // Vyberiem najlepsiu
    for(int i=0; i<pocetMoznosti.size(); ++i) 
        if (pocetMoznosti[i] > pocetMoznosti[najlepsia])
            najlepsia = i;
    for(int i=0; i<testov; ++i)
        cout << najlepsia << endl;
}

void hrajB() {
    int n, k, testov, dvere;
    cin >> n >> k >> testov;
    for(int i=0; i<testov; ++i) {
        cout << 1 << endl;
        vector<bool> suOtvorene(n+1, false);
        // Zistim, ktore dvere su otvorene
        for(int j=0; j<k; ++j) {
            cin >> dvere;
            suOtvorene[dvere] = true;
        }
        // Najdem prve zavrete dvere s cislom aspon 2
        dvere = 2;
        while(suOtvorene[dvere]) dvere++;
        cout << dvere << endl;
    }
}

typedef vector<int> vi;
typedef vector<vi> vii;
vii P;
int n, c1, c2, mod1, mod2, testov;

void vyskusajHody(int n, int doterajsiSucet) {
    if (n == 0) {
        P[doterajsiSucet % mod1][doterajsiSucet % mod2]++;
        return;
    }
    vyskusajHody(n-1, doterajsiSucet + c1);
    vyskusajHody(n-1, doterajsiSucet + c2);
}

void hrajC() {
    cin >> n >> c1 >> c2 >> mod1 >> mod2 >> testov;
    P = vii(mod1, vi(mod2, 0));
    // Spocitam si spravne odpovede
    vyskusajHody(n, 0);
    for(int i=0; i<testov; ++i) {
        int zvysok1, najlepsi = 0;
        cin >> zvysok1;
        // Najdem najlepsi zvysok2
        for(int j = 0; j<mod2; ++j) {
            if (P[zvysok1][j] > P[zvysok1][najlepsi])
                najlepsi = j;
        }
        cout << najlepsi << endl;
    }
}

int main() {
    char poduloha;
    cin >> poduloha;
    switch(poduloha) {
        case 'A': hrajA(); break;
        case 'B': hrajB(); break;
        case 'C': hrajC(); break;
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.