Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.

Detalii evaluare #63570196

Rezumat problemă

lant2
#2191

Ion este un lingvist pasionat. Recent el a descoperit un text scris într-o limbă necunoscută. Textul este scris pe mai multe linii şi este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spaţii sau/şi semne de punctuaţie (,:;.!?-). Ion a fost frapat că există multe similitudini între cuvintele din text. Fiind foarte riguros, Ion definește similitudinea a două cuvinte după cum urmează. Fie c1 şi c2 două cuvinte. Cuvântul c1 poate fi obţinut din cuvântul c2 printr-o succesiune de operaţii elementare. Operaţiile elementare ce pot fi folosite sunt:

  • move(c1, c2) – Mută primul caracter din c1 la sfârşitul cuvântului c2 (de exemplu, dacă c1="alba" şi c2="neagra", după efectuarea operaţiei move(c1, c2), c1 va fi "lba", iar c2 va fi "neagraa")
  • insert(c1, x) – Inserează caracterul x la începutul lui c1 (de exemplu, dacă c1="alba" şi x='b', după executarea operaţiei insert(c1,x), c1 va fi "balba")
  • delete(c1) – Şterge primul caracter din c1 (de exemplu, dacă c1="alba", după executarea operaţiei delete(c1), c1 va fi "lba")

Definim similitudinea dintre c1 şi c2 ca fiind numărul minim de operații insert şi delete ce trebuie să fie executate pentru a transforma cuvântul c1 în cuvântul c2 (operațiile move nu se numără).
Fie c0 primul cuvânt din text. Începând cu c0 putem construi lanțuri de k-similitudine.
Un lanţ de k-similitudine este o succesiune de cuvinte distincte din text cu următoarele proprietăți:

  • dacă cuvântul x apare în lanţ înaintea cuvântului y, atunci prima apariţie a lui x în text precedă prima apariţie a lui y în text;
  • dacă x şi y sunt cuvinte consecutive în lanţ (în ordinea x y), atunci similitudinea dintre x şi y este mai mică sau egală decât k;
  • lanţul este maximal (adică nu putem adăuga încă un cuvânt la sfârşitul acestui lanţ, astfel încât să fie respectate proprietăţile precedente).

Scrieţi un program care să determine numărul de lanţuri de k-similitudine care încep cu c0.

Olimpiada județeană de informatică, 2005
Fișiere Pracsiu Dan (dnprx) Emanuela Cerchez concurs
Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate Grafuri orientate Distanta Levenshtein
Rezolvă

Detalii

Problema lant2 Operații I/O lant2.in/lant2.out
Limita timp 0.1 secunde Limita memorie Total: 64 MB / Stivă 8 MB
Id soluție #63570196 Utilizator Cretu Elena (elena_cretu)
Fișier lant2.cpp Dimensiune 2.00 KB
Data încărcării 09 Martie 2026, 21:58 Scor/rezultat Eroare de compilare

Evaluare

Mesaj compilare

lant2.cpp: In function 'void citire()':
lant2.cpp:32:10: error: 'k' was not declared in this scope
     fin>>k;

          ^
lant2.cpp: In function 'int dist_editare(char*, char*)':
lant2.cpp:53:34: error: 'int dist_editare(char*, char*)' redeclared as different kind of symbol
 int dist_editare(char *a, char *b)

                                  ^
lant2.cpp:14:5: error: previous declaration of 'int dist_editare'
 int dist_editare;

     ^
lant2.cpp:57:5: error: 'lga' was not declared in this scope
     lga=strlen(a);

     ^
lant2.cpp:58:5: error: 'lgb' was not declared in this scope
     lgb=strlen(b);

     ^
lant2.cpp:55:9: warning: unused variable 'lgp' [-Wunused-variable]
     int lgp,lgq,i,j;

         ^
lant2.cpp:55:13: warning: unused variable 'lgq' [-Wunused-variable]
     int lgp,lgq,i,j;

             ^
lant2.cpp: In function 'void constr_graf()':
lant2.cpp:79:42: error: 'dist_editare' cannot be used as a function
             if(dist_editare(cuv[i],cuv[j])<=k)

                                          ^
lant2.cpp:79:45: error: 'k' was not declared in this scope
             if(dist_editare(cuv[i],cuv[j])<=k)

                                             ^

Cum funcționează evaluarea?

www.pbinfo.ro permite evaluarea a două tipuri de probleme:

  • probleme la care rezolvarea presupune scrierea unui program complet
  • probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.

Problema lant2 face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:

  • Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
  • Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.

Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.

Du-te sus!