Fişierul intrare/ieşire:sobo.in, sobo.outSursăConcurs de incalzire 2004
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.65 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Sobo

Petrica, satul de munca pe santier, vrea sa faca de ceva mai apropiat capacitatii sale intelectuale. Astfel si-a luat o cutie cu N sobolani si face experimente pe ei. Printre altele el a scos harta genetica a fiecarui sobolan, care consta intr-o secventa binara de lungime L. Printre sobolani se afla unul mai special, cel mai inteligent dintre ei, pe care Gigel, prietenul lui Petrica, il vrea cu orice pret. Petrica insa nu vrea sa renunte la sobolanul inteligent atat de usor si il pune pe Gigel la urmatoarea proba: ii da hartile genetice ale tuturor sobolanilor, fara sa-i spuna care este cel special. Gigel are voie sa puna intrebari de genu: "Ce valoare are harta sobolanului inteligent in pozitia x ?" dar raspunsul are un pret, Petrica dandu-i lista preturilor tuturor pozitiilor. Asadar Gigel va trebui sa ghiceasca sobolanul destept pe baza raspunsurilor lui Petrica care sunt de forma: "Harta sobolanului inteligent are in pozitia x valoarea y" unde y este 0 sau 1. Gigel vrea sa stie care e pretul minim pe care il plateste, considerand cel mai defavorabil caz (Petrica va alege raspunsurile astfel incat costul sa fie cat mai mare posibil).

Cerinta

Gigel va plati considerabil (cu 100 de puncte) pe cel care ii va face un program care sa calculeze acest cost.

Date de intrare

Pe prima linie in fisierul de intrare sobo.in se afla numerele N, L separate prin cate un spatiu reprezentand numarul de sobolani si lungimea hartilor genetice ale acestora. Pe urmatoarele N linii se afla cate un sir de L biti (nedespartiti de spatii) reprezentand harta unui sobolan. Pe ultima linie se afla L numere separate prin spatii reprezentand costul raspunsului pentru fiecare pozitie.

Date de iesire

Pe prima linie din fisierul de iesire sobo.out se va gasi un numar intreg reprezentand costul minim in cel mai defavorabil caz pentru Gigel.

Restrictii si precizari

  • 1 ≤ N ≤ 15
  • 1 ≤ L ≤ 1000
  • Costurile raspunsurilor sunt numere intregi din intervalul [1, 11.000.000]
  • Nu exista sobolani cu harti genetice identice

Exemplu

sobo.insobo.out
4 3
101
000
011
010
2 6 7
13

Explicatii

Costul minim 13 (in cel mai defavorabil caz) este obtinut astfel: Gigel intreaba care este valoarea hartii sobolanului inteligent in pozitia 2 si Petrica ii raspunde 1 acesta fiind cel mai defavorabil caz (daca raspunsul lui Petrica ar fi fost 0 urma intrebarea lui Gigel despre valoarea in pozitia 1 si sobolanul ar fi fost identificat cu un costul 6 + 2 = 8). Asadar niciunul dintre primii doi sobolani nu este cel inteligent. Gigel mai trebuie sa afle care din ultimii doi sobolani este cel inteligent si mai cere informatii despre pozitia 3 din harta sobolanului inteligent. Indiferent de raspuns sobolanul inteligent va fi descoperit.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content