Spnzr

Bubu si Puffy s-au apucat de jocuri de noroc. Deși pare ciudat, ei joacă celebrul joc numit spânzurătoarea. Dar fiindcă ei s-au plictisit, acum vor să joace cu voi. Ei vă dau un dicționar cu N cuvinte formate numai cu litere mici ale alfabetului, iar apoi T cuvinte secrete pentru care veți ști doar lungimea lor. Voi va trebuie să „ghiciți” fiecare cuvânt secret, având la dispoziție funcțiile:

std::vector<int> ask(char ch);
bool guess(const std::string& word);

Funcția ask înseamnă că întrebați dacă litera ch apare în cuvântul secret. Costul acestei operatii este 1. Funcția returnează pozițiile (indexate de la 0) la care se află litera în cuvântul secret.

Funcția guess înseamnă o "ghicire" a cuvântului. În cazul în care cuvântul coincide cu cel secret, costul operației este 0. În caz contrar, costul operației este 3 + numărul de „ghiciri” invalide, efectuate anterior pentru cuvântul curent. Funcția returnează adevărat dacă cuvântul ghicit coincide cu cuvântul secret, fals altfel.

Cerinţa

Dându-se un dicționar cu N cuvinte și T cuvinte secrete pentru care se citesc doar lungimile lor, scrieți un program care obține un cost cât mai mic pentru a „ghici” toate cuvintele.

Intercțiune

Programul vostru nu va citi şi nu va scrie din/în niciun fişier. În schimb, va avea de implementat următoarele funcții:

void init(int n, std::vector<std::string>& dict);
std::string solve(int len);

Funcția init va fi apelată doar o dată la începutul fiecărui test și va furniza numărul de cuvinte din dicționar și cuvintele din dicționar.
Funcția solve va fi apelată de T ori și va furniza numărul de litere al cuvântului curent pe care trebuie să-l ghiciți. Funcția va returna cuvântul secret curent.
Nu trebuie să implementația funcția main, dar puteți declara variabile/funcții suplimentare. Puteți să apelați funcțiile ask și guess descrise mai sus.

Restricţii şi precizări

• 1 ≤ N ≤ 70 000
• 1 ≤ T ≤ 75
• 5 ≤ lungimea unui cuvânt ≤ 21
• Pentru 20% din teste N ≤ 25 000
• Cuvintele din dicționar conțin doar litere mici ale alfabetului englez și este asemănător cu dicționarul explicativ al limbii române.
• Toate cuvintele au probabilitate egală să apară într-un test.
• Problema a fost adaptată.
• Trebuie să includeți fișierul spnzr.h.

Punctaj

Punctajul pentru un test va fi 0 dacǎ apare una dintre următoarele situaţii:

• programul vostru depǎşeşte timpul maxim de execuţie/test;
• programul vostru nu respectǎ protocolul de comunicare;
• programul vostru nu „ghicește” toate cele T cuvinte secrete.

Punctajul pentru un test va fi calculat în funcție de un scor prestabilit de comisie, după o anumită formulă.

Exemplu de interactiune

Este apelată funcția init(2,{"banana","benene"}) de către comisie.
Este apelată funcția solve(6) de către comisie.

În solve:
Concurentul apelează ask('n'). Funcția returnează {2,4}, costul este 0+1=1.
Concurentul apelează ask('b'). Funcția returnează {0}, costul este 1+1=2.
Concurentul apelează guess("benene"). Funcția returnează false, costul este 2+3=5.
Concurentul apelează ask('a'). Funcția returnează {1,3,5}, costul este 5+1=6.
Concurentul apelează guess("banana"). Funcția returnează true, costul este 6+0=6.
solve returnează "banana", costul total este 6.