Detalii evaluare #50647465

Rezumat problemă

#2191 lant2

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.

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 #50647465 Utilizator Constantin Antonio (Antonel14)
Fișier lant2.cpp Dimensiune 2.19 KB
Data încărcării 18 Aprilie 2024, 13:51 Scor / rezultat 100 puncte

Evaluare


Mesaj compilare


Rezultat evaluare

Test Timp Mesaj evaluare Scor posibil Scor obținut
0 0 secunde OK. 10 10
1 0 secunde OK. 10 10
2 0 secunde OK. 10 10
3 0 secunde OK. 10 10
4 0 secunde OK. 10 10
5 0 secunde OK. 10 10
6 0 secunde OK. 10 10
7 0 secunde OK. 10 10
8 0 secunde OK. 10 10
9 0 secunde OK. 10 10
Punctaj total 100

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