Po týždni strávenom lozením po horách sa Katka vrátila naspäť do civilizovaného sveta a do svojho biologického labáku. Dušu jej ale ťažilo trápenie.

Jej obľúbený plyšový hroch bol teraz vážne chorý a hrozilo to najhoršie. Hory a chlad mu proste nespravili dobre. Dlhé noci sa oňho musela starať a uplatňovať všetky svoje poznatky z imunológie, mikrobiológie, analýzy, fyziológie a iných okultných náuk.

Nakoniec ale všetko dobre dopadlo. Hroch to prežil. Kaťa si ale povedala, že niečo takéto už nikdy nechce zažiť znova a teda, že hrocha už so sebou nebude na takéto túry nosiť. To by tam ale musela chodiť sama a to sa jej nechce. Rozhodla sa teda, že si ako správna biologička vyšľachtí niekoľko silných, alergiám, malátnosti, a kazom odolných vtákopyskov.

To ale nie je sranda. Také šľachtenie je mimoriadne komplikovaná vec a ani Kaťa jej úplne nerozumie. Jediné, čo teda môže robiť, je zobrať niekoľko génov, zlepiť ich za seba a dúfať, že jej vznikne vtákopysk so chcenými vlastnosťami. Aby otestovala jeho odolnosť, pošle ho na bakalársky seminár. Čím dlhšie tam vydrží, tým je odolnejší. Takto si Katka mieša a testuje už niekoľko mesiacov. Pomôžte jej tento proces trochu zautomatizovať.

Úloha

Vašou úlohou je napísať program, ktorý bude schopný vytvoriť čo najodolnejšieho vtákopyska. Na výrobu vtákopyska potrebujeme $$50$$ génov (tak málo to je, lebo je plyšový). Gény sú písmená A, C, G a T.

Dokopy máte $$n=100\,000$$ pokusov na ukuchtenie toho najodolnejšieho stvorenia aké kedy tento seminár videl (a to teda naozaj nie je ľahká úloha). Po každom pokuse sa dozviete, ako veľmi bolo vaše stvorenie odolné. Kto vytvorí najodolnejšieho vtákopyska vyhrá. Samozrejme je tu aj istý časový limit.

Bodovanie

Zo všetkých (najviac $$100\,000$$) vašich pokusov jedného odovzdaného programu sa vyberie najodolnejší vtákopysk. Čím bude tento vtákopysk odolnejší, tým viac bodov za program dostanete. [^1]

Skoro určite sa vám nepodarí vytvoriť vtákopyska, ktorý na bakalárskom seminári vydrží viac ako 85 dní (pochybujeme, že taký vôbec môže existovať). Pokiaľ váš vtákopysk vydrží $$80$$ alebo viac dní, dostanete plný počet bodov. Za $$67$$ a viac dní dostanete aspoň $$10$$ bodov, za $$53$$ a viac dní aspoň $$5$$ bodov. Ak váš vtákopysk nevydrží ani $$10$$ dní nedostanete žiadne body, iba by ste Kaťu zbytočne rozosmútili. Dostať môžete ľubovoľný celočíselný počet bodov od $$0$$ po $$15$$, veď odovzdajte nejaké riešenie a uvidíte.

Poznámka

Možno ste si všimli, že nikde nie je napísané, čo tá odolnosť vlastne znamená. No, svet je tajomné a komplikované miesto a naozaj nikto netuší, čo treba mať na zvládnutie bakalárskeho semináru. Odporúčame vám si pri testovaní vymyslieť si nejakú vlastnú funkciu a zistiť, ako na nej vaša metóda kuchtenia funguje.

Dobré je robiť veľa testov na vlasntnom počítači, nie všetko čo naprogramujete hneď odovzdávať.

Formát vstup a výstupu

V tejto úlohe budete komunikovať s naším programom (krutý svet príkorí). Jednoducho na (štandardný) výstup vypíšte reťazec $$50$$ znakov z ACGT končiaci znakom nového riadku a na vstup dostanete jedno celé číslo predstavujúce odolnosť vášho výtvoru. Toto môžete opakovať až $$100\,000$$ krát, ak sa pokúsite spýtať viac otázok, váš pokus bude považovaný za neplatný.

Ak nechcete využiť všetky pokusy, musíte namiesto reťazca znakov vypísať znak K (ako koniec).

Ak chcete dostať odpoveď, je nutné po každom vypísaní génov výstup presunúť z pamäte na štandardný výstup pomocou príkazu fflush(stdout); v C++, alebo flush(output); v Pascale.

Príklad

Komunikácia medzi vašim a našim programom by mohla vyzerať napríklad nasledovne:

Najlepší vtákopysk prežil 58 dní. Riešenie by dostalo 6 bodov.

1. Jednotlivé programy sa však naďalej hodnotia nezávisle a ráta sa len posledný odovzdaný program. Upozorňujeme vás, aby ste v tejto úlohe neodovzdávali príliš veľa programov, napríklad takých 200 už je veľa ale 10 až 30 je úplne v poriadku. Pokiaľ budete odovzdávať priveľa programov, môžeme sa rozhodnúť ohodnotiť iný ako posledný program.↩