Julka nedávno na instagrame pozerala video o krájaní cibule. Veľmi ju to nadchlo a rozhodla sa že sa stane majsterkou cibule. Zistila že je naozaj veľa rôznych druhov. Spísala si to do zoznamu a následne s tým Lukáša šikanovala. Nútila ho hádať o akú odrodu cibule sa jedná.
Lukášovi to však moc nešlo :(. Preto mu Julka začala radiť, pre každé písmenko mu povedala, či ho má dobre, zle, alebo sa toto písmenko vyskytuje niekde inde v názve odrody.
Lukáš sa vtedy zamyslel: Na koľko najmenej pokusov dokáže uhádnuť odrodu? Pomôžte mu!
Najprv dostanete na vstupe zoznam všetkých odrôd cibule, čo sú dovolené slová, ktoré môžeš hádať. V tejto úlohe musíš zistiť hľadané $5$-písmenové slovo na čo najmenej pokusov. Po každom pokuse ti testovač vypíše správu vo formáte “{tvoj-pokus} {protokol}”. Protokol vyzerá napríklad takto: “DDDDD”. To znamená, že každé písmeno je na správnom mieste. Okrem toho môže byť aj “Z” ako “toto písmeno sa v celom slove nevyskytuje” alebo “M” čo znamená “toto písmeno sa v slove vyskytuje ale na inom mieste”. Ak vypíšete slovo, ktoré nie je v zozname dovolených slov, protokol je “IGN”.
Na začiatku dostanete číslo $m$ - počet odrôd cibule. Nasleduje $m$ riadkov s všetkými dovolenými slovami. Potom vypíšete svoje slovo, na čo vám testovač odpíše.
POZOR: Bodovanie v tejto úlohe je špeciálne. Dostávate body na základe toho, na koľko pokusov v priemere uhádnete riešenie. Ak váš program neuhádne slovo do $50$ pokusov, dostávate v danom vstupe $0$ bodov a nepokračujete na ďalšie vstupy v sade.
Keďže sa jedná o interaktívnu úlohu, je nutné po vypísaní každého riadku flushnúť výstup, aby
ho testovač uvidel. V C++ by malo stačiť cout << nieco << endl;, ale môžete explicitne
použiť príkaz cout.flush();. V Pythone vypisujte príkazom print(slovo, flush=True)
alebo po vypísaní zavolajte sys.stdout.flush(). Pre iné jazyky hľadajte ekvivalent k
príkazu flush. Vstup od testovača načítavate klasicky pomocou input() alebo cin >> line
Všetky dovolené 5-písmenové slová nájdete v slovníku tu. Prehľadávanie internetu pre optimálne stratégie je odporúćané.
>>>3
>>>jarna
>>>cerve
>>>biela
<<<jarna
>>>jarna ZMZZD
<<<biela
>>>biela DDDDD
(>>> znamená, že ide o vstup vášho programu, <<< zas, že ide o jeho výstup. Tieto značky sú len ilustračné, na testovači sa nevyskytujú.)
Slovník v tomto prípade je “jarna,biela a cerve”. Lukáš si tipol “jarna”, no všetky písmenká až na posledné boli zle, okrem 2. ktoré bolo iba na zlom miest. Tak Lukáš skúsil biela, ktoré už bolo celé dobre
Súťaž PRASK zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre stredoškolákov
Tímová matematicko-fyzikálna súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania