3. Pofiderné kasíno

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

Adam má veľmi rád rezne. Preto keď zistil, že si ich v školskej jedálni môže objednať koľko len chce, bol veľmi nadšený. Rovno si ich preto objednal \(100\,000\) a tešil sa, ako ich bude všetky jesť.

Na druhý deň sa cítil ako v raji. Rezeň sem, rezeň tam… Skôr ako ich všetky zjedol si však uvedomil, že za ne bude musieť aj zaplatiť. A keďže toľko peňazí pri sebe nemá, ocitol sa v obrovských dlhoch. A kuchárky s tĺčikmi na mäso mu prišli oznámiť, že ak nezaplatí do konca PRASK kola, vyklepú ho viac, ako tých \(100\,000\) rezňov.

Adam preto potrebuje rýchlo zarobiť veľké peniaze. A kde inde ako v kasíne¹! Samozrejme, Adam vie, že v kasíne sa ho budú snažiť oklamať. On je však šikovnejší. A naviac má kamaráta, ktorý programoval stroje v kasíne a ten mu poskytol ich zdrojové kódy. Teraz už len zistiť, ako vyhrať. Pomôžete mu?

Úloha

V každej úlohe dostanete zdrojový kód jedného výherného stroja. Vašou úlohou bude nájsť v tomto programe slabinu a potom si ísť zahrať do našeho kasína. Vždy keď sa vám na nejakom automate podarí vyhrať, dostanete url adresu, na ktorej sa vám pripočítajú body. A ak prehráte, nič sa nedeje, môžete to skúsiť znovu.

Na hranie v kasíne sa potrebujete pripojiť na náš server, kde toto kasíno beží. Návod ako to spraviť pre rôzne operačné systémy je tu.

Linux:

Treba si nainštalovať netcat – je možné, že ho už máte. Ak nie, tak si ho v závislosti od distribúcie, ktorú používate nainštalujte.

Pre Ubuntu by napríklad fungoval príkaz:

sudo apt-get install netcat

Následne stačí do konzoly zadať príkaz:

nc 158.195.16.154 9947

ktorý vás pripojí na náš server a vy môžete hrať.

Windows:

K tomuto tutoriálu existuje aj videonávod.

Netcat si najskôr musíte stiahnuť. Následne si v nejakom priečinku tento .zip rozbaľte. Potom si otvoríte príkazový riadok (buď zo Start menu alebo cez spúšťač programov – stlačíte Windows + R a napíšete cmd). V ňom musíte prejsť do priečinku s rozbaleným netcat zipom. To spravíte príkazom:

cd cesta_k_netcatu

pričom hodnotu cesta_k_netcatu zistíte tak, že v prieskumníku súborov sa pozriete na adresu priečinka s týmto zipom.

Následne zadáte príkaz:

chcp 65001

ktorým nastavíte vypisovanie slovenských znakov v príkazovom riadku. Ostáva už len pripojiť sa na náš server príkazom:

nc.exe 158.195.16.154 9947

V kasíne používame Python, verziu 3.5.2.. Ak si teda chcete skúšať spúšťať programy uvedené nižšie u seba, použite túto verziu.

Ak budete mať akékoľvek otázky ohľadom úlohy, toho ako funguje netcat, Python, C++ alebo naše generátory náhodných čísel, napíšte Prefixovi. Rád vám pomôže.

Podúlohy

1. (2 body)

Adam vie, že prístroj používa veľmi jednoduchú funkciu na generovanie náhodných čísel:

def random():
    global seed1
    seed1 = (a*seed1)%10000
    return seed1

V tomto kóde je \(a\) náhodné číslo, ktoré je stanovené pri spustení kasína a počas celého behu sa nemení (zmení sa však ak napr. reštartujete kasíno). Adam toto číslo nepozná. Číslo \(seed1\) je globálna premenná, ktorá má na začiatku tiež neznámu hodnotu. Vždy keď Adam spraví ďalší pokus pomocou hodnoty \(a\) a \(seed1\) sa vypočíta nová hodnota pre \(seed1\), ktorá slúži ako výsledok. Ak je tento výsledok rovnaký ako Adamov pokus, Adam vyhráva. Znak "%" predstavuje zvyšok po delení (modulo).

2. (3 body)

Zákerný programátor tohto automatu sa chcel uistiť, že súťažiaci v žiadnom prípade nemôže vyhrať. Do už existujúceho programu preto pridal jeden riadok, ktorý mal túto podmienku zaručiť. Program bol však písaný v C++ a zlý programátor sa dopustil osudnej chyby. Zistíte akej? Ako môžete vyhrať?

//Hodnotu a nepoznáte, medzi pokusmi sa však nemení
int a;

bool vyhral(){
    int x,y;
    cout << "Ake x tipujes?";
    cin >> x;               // načíta prvé číslo
    cout << "Ake y tipujes?";
    cin >> y;               // načíta druhé číslo
    int z = x*a + y;
    if(z<0) z = -z;         // pridaný riadok
    if(z<0) return true;    // Výhra - nemožné?
    else return false;      // Prehra
}

Hint: Čo je to vlastne ten int v C++? A ako presne funguje?

3. (4 body)

Po fiasku s prístrojom z úlohy a) sa kasíno rozhodlo, že obmení svoju náhodnú funkciu. Nová funkcia vyzerá takto:

def random():
    global seed1
    seed1 = (a*seed1 + b)%9973
    return seed1

Adam v tomto prípade nepozná dokonca dve čísla – \(a\) a \(b\).

4. (6 bodov)

Koniec hier. Použitie funkcie randint z Pythonu sa už určite nebude dať nijak oklamať:

seed(int(time.time()))

def random():
    return randint(0,1000000)

Tento program funguje tak, že na začiatku sa generátor náhodných čísel nastaví podľa aktuálneho času (prvý riadok). Je to vlastne nastavenie hodnoty \(seed1\) z podúloh a) a b). Následne sa podľa tohto nastavenia postupne generuje nové číslo, ktoré je použité na generovanie toho ďalšieho…

Adam našťastie pozná približný čas, v ktorom bol tento generátor spustený (a dozviete sa ho aj vy, keď si spustíte kasíno). Nie je to však také ľahké, lebo pred vami už na ňom nejaký ľudia hrali a preto aktuálna hodnota môže byť dosť posunutá. Našťastie viete, že nebola zavolaná viac ako \(1\,000\) krát.

Hint: unixový čas