Zadanie

Píše sa 31. jún 2019. Prešlo už viac ako 20 rokov odkedy ste nezískali tender na napísanie programu pre jadrovú elektráreň na matfyze. Ale časy sa menia a tentoraz je šťastie na vašej strane. Ministerstvo Krajne Serióznych Projektov sa rozhodlo vykonať rutinnú 20 ročnú kontrolu bezpečnostných systémov kritických zariadení republiky a vy ste vyhrali tento tender! Hlava sa vám točí nad predstavou koľko korniet si budete vedieť kúpiť. Ale najprv práca, potom kornetá, hor sa do roboty!

Bezpečnostný systém funguje na báze Masívneho hesla, teda číselnej kombinácie, ktoré má uložené v pamäti a ktoré porovnáva s pokusmi od užívateľa. Vám však netrvalo dlho zistiť, že to kódil naozaj iba nejaký skoro-programátor. Pokus sa vyhodnotí ako nesprávny nie keď sa zadané heslo nezhoduje s Masívnym heslom, ale keď obsahuje nejaké znaky navyše! To znamená, že na poradí znakov v hesle vôbec nezáleží a že napríklad prázdne heslo bude vždy správne.

Ministerstvo nebolo veľmi nadšené vaším zistením, ale odľahlo im, lebo vraj potenciálny útočník túto chybu nevedel použiť na zistenie Masívneho hesla. To totižto používajú úplne všade a ak by ho zistiť vedel, bola by šanca, že ho niekedy v minulosti získal alebo možno v blízkej budúcnosti získa. Toto by nemohli riskovať, museli by Masívne heslo všade zmeniť a komu sa to chce.

Dokážte, že sa mýlia a že sa táto chyba dá použiť na zistenie Masívneho hesla. Navrhnite program, ktorý toto Masívne heslo nájde.

Úloha

Táto úloha je interaktívna. Namiesto kompletného vstupu budete dostávať odpovede na vaše otázky. Heslo je podmnožina, teda niekoľko rôznych celých čísel od \(1\) po \(N\), pričom Masívne heslo má dĺžku najviac \(M\) čísel.

Vaša otázka je tip na Masívne heslo. Odpoveď na vašu otázku bude kladná, pokiaľ je každý jeden prvok tejto otázky súčasťou Masívneho hesla. Teda otázka bude vyhodnotená záporne, pokiaľ obsahuje aspoň jeden prvok, ktorý nie je súčasťou Masívneho hesla. Vašou úlohou je zistiť Masívne heslo.

Môžete sa opýtať nanajvýš \(111\,111\) otázok.

Formát vstupu

Na prvom riadku dostanete čísla \(N\) – najväčšie možné číslo v hesle a \(M\) – maximálnu dĺžku Masívneho hesla, pri čom vždy platí \((0 \leq M \leq N \leq 10^5)\).

Následne dostanete odpoveď na každú vašu otázku jedným riadkom obsahujúcim JOP v prípade kladného vyhodnotenia a NOP v prípade záporného.

Formát výstupu

Každá otázka, ktorú položíte, by mala byť vypísaná na jednom novom riadku. Riadok sa začína číslom \(K\) - dĺžkou hesla. Za ním nasleduje medzera a \(K\) medzerou oddelených čísel – vaša otázka. V prípade, že si myslíte, že poznáte Masívne heslo, vypíšte -1 a na nový riadok vypíšte toto heslo v rovnakom formáte, ako otázky (teda číslo \(K\) a za ním \(K\) medzerou oddelených čísel).

Pokiaľ sa opýtate viac ako \(111\,111\) otázok, váš program bude nemilosrdne ukončený a v testovači sa to prejaví verdiktom "WA - Zlá odpoveď" alebo dokonca "EXC - Chyba počas behu programu".

Flushovanie

Programovacie jazyky štandardne používajú výstupný buffer, a až po jeho zaplnení program vypíše jeho obsah. Flushovanie vlastne znamená vypísanie (vyprázdnenie) tohto buffera. Vždy, keď vypíšete svoju otázku, musíte ešte flushnúť výstupný buffer. Inak sa váš ťah v skutočnosti nevypíše a nedostane sa k nášmu programu. V konečnom dôsledku potom dostanete hlášku "TLE - Prekročený časový limit".

Ako flushovať?

Ak programujete v C/C++ a používate printf(), na to aby ste flushli jeho buffer, použite fflush(stdout). Ak používate cout, buffer sa flushuje automaticky po vypísaní konca riadku pomocou cout<<endl. Ak programujete v Pythone, používajte print(vystup, flush=True). Ak programujete v Pascale použite flush(output).

Hodnotenie

Sú 4 testovacie sady, každá za 2 body. Platia v nich nasledovné obmedzenia:

Sada 1 2 3 4
Maximálne N \(15\) \(200\) \(3\,000\) \(100\,001\)

Navyše v druhej sade platí, že počet platných tajných hesiel je malý, teda hesiel ktoré neporušujú obmedzenie na maximálnu veľkosť Masívneho hesla.

V hodnotení popisu sa bude samozrejme klásť veľký dôraz na časovú zložitosť, ale tento krát ešte väčší na počet položených otázok. Odhad počtu položených otázok a časovej zložitosti programu nezabudnite zdôvodniť a dokázať.

Príklad

>>>3 2
0
>>>JOP
2 1 2
>>>NOP
2 1 3
>>>NOP
2 2 3
>>>JOP
-1
2 2 3

Pre lepšiu čitateľnosť sme pred riadky obsahujúce výstup testovača dopísali prompt ">>>". Tento sa v skutočnosti nikde nezjaví: ani náš program ho nevypíše, ani vy ho nemáte vypisovať.

Skúšame všetky heslá

Priamočiare riešenie ktoré vyrieši prvú sadu je jednoducho vyskúšať všetky Masívne heslá. Tých je \(2^N\), keďže každé číslo v Masívnom hesle buď je, alebo nie je, a teda za každé možné číslo sa počet možností zdvojnásobí.

Vyskúšať všetky možnosti môžeme napríklad jednoduchou rekurzívnou funkciou, v ktorej si udržiavame zoznam čísel na ktorý sa chceme opýtať (najprv prázdny), a číslo o ktorom sa práve rozhodujeme či ho do zoznamu pridáme, alebo nie. Zakaždým vyskúšame obe možnosti – pridať toto číslo do zoznamu a rekurzívne rozhodnút nad ďalším, alebo ho nepridať a rekurzívne rozhodnúť nad ďalším. Keď už sme sa rozhodli nad všetkými \(N\) číslami, opýtame sa testovača, a keď nám dá kladnú odpoveď, uložíme si tento zoznam ako kandidáta na Masívne heslo práve vtedy, keď pozostáva z viac čísel ako globálny zoznam v ktorom si udržiavame momentálnu odpoveď. Masívne heslo je totiž práve taká sada čísel na ktorú dostaneme JOP, ktorá má v sebe čísel najviac.

Po vyskúšaní všetkých odpovedí oznámime testovaču najdlhšie heslo na ktoré sme dostali JOP.

Hesiel musíme vyskúšať \(O(2^N)\), pričom zakaždým musíme vypísať až \(O(N)\) čísel v otázke. Časovú zložitosť teda máme \(O(2^N)\). Pamätáme si pritom jeden globálny zoznam a jeden zoznam v rekurzií o dĺžke najviac \(N\), a konštantne veľa premenných, čiže pamäťe zaberieme \(O(N)\).

Vylepšenie pre druhú sadu

Malou úpravou horeuvedeného riešenie vieme vyriešiť aj vstupy druhej sady, kde máme zaručené že počet platných Masívnych hesiel je malý. Ak teda v rekurzií nebudeme skúšať pridať do zoznamu ďaľšie čísla, ak už by presiahol dĺžku \(M\), vyskúšame len týchto zopár platných hesiel a získame nejaké body navyše.

Časová zložitosť je vo všeobecnom pripade rovnaká, ale pre \(M\) o dosť menšie ako \(N\) bude tesnejší odhad na opýtané otázky \(N\) nad \(M\).

Optimálne riešenie

Optimálnym riešením, ktoré sa dokonca programuje ľahšie ako už spomínaná rekurzia, je všimnúť si že sa môžeme opýtať na všetky heslá o dĺžke \(1\). Odpoveď na otázku so samotným číslom \(i\) nám potom priamo povie, či sa v Masívnom hesle \(i\) nachádza. Keď sa teda spýtame na všetky čísla od \(1\) po \(N\), teda \(N\) otázok a zároveň \(N\) čísel, budeme o každom vedieť či sa v hesle nachádza alebo nie, a tie ktoré sme zistili že v ňom sú môžeme všetky vypísať.

Pamäťová zložitosť tohoto riešenia je \(O(N)\), keďže si musíme o každom čísle pamätať či v hesle je, alebo nie (prípadne si robíme zoznam s číslami ktoré v ňom naozaj sú, ale aj tých môže byť až \(N\)). Časová zložitosť je \(O(N)\), keďže sa pýtame \(N\) otázok na konštantne veľa čísel, a nakoniec vypíšeme odpoveď v ktorej je tiež \(O(N)\) čísel.

Dôkaz správnosti

Teraz si poďme dokázať, že úlohu naozaj nevieme vyriešiť na menej otázok, alebo s lepšou časovou zložitosťou.

Čo keby bolo Masívne heslo práve jedno číslo? Potom ľubovoľná otázka s viac ako jedným číslom nám neposkytne žiadnu informáciu – odpoveď je vždy NOP, a my nevieme či je v tejto otázke to správne číslo. Jediný spôsob ako to zistiť je naozaj sa spýtať na každé číslo zvlášť. Musíme sa teda opýtať aspoň \(N\) otázok.

Keďže sa musíme opýtať aspoň \(N\) otázok, a teda aspoň toľko čísel musíme vypísať, určite úlohu nevyriešime rýchlejšie ako na \(O(N)\) operácií. Iný môžný dôkaz je to, že v heslo môžu byť všetky čísla, a bezohľadu na to ako to uhádneme, budeme ich musieť všetky vypísať.

#include <iostream>

using namespace std;

int main()
{
	int N,M;
	cin >> N >> M;

	bool heslo[N];
	int velkost = 0;

	for(int i=0;i<N;++i)
	{
		cout << "1 " << i+1 << endl;
		string odpoved;
		cin >> odpoved;

		if(odpoved == "JOP")
		{
			heslo[i] = true;
			velkost++;
		}
		else
			heslo[i] = false;
	}

	cout << "-1" << endl;

	cout << velkost;

	for(int i=0;i<N;++i)
	{
		if(heslo[i])
			cout << " " << i+1;
	}
	cout << endl;

}

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ť.