*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).

1. (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?

1. (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$.

1. (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