#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:
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;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
;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
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 | #49528781 | Utilizator | |
Fișier | lant2.cpp | Dimensiune | 1.55 KB |
Data încărcării | 05 Martie 2024, 22:36 | Scor / rezultat | 40 puncte |
lant2.cpp: In function 'int drumuri(int)': lant2.cpp:50:1: warning: no return statement in function returning non-void [-Wreturn-type] } ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0 secunde | OK. | 10 | 10 | ||
1 | Depășit | Limita de timp depășită | 10 | 0 | ||
2 | Depășit | Limita de timp depășită | 10 | 0 | ||
3 | 0.004 secunde | OK. | 10 | 10 | ||
4 | 0 secunde | OK. | 10 | 10 | ||
5 | Depășit | Limita de timp depășită | 10 | 0 | ||
6 | 0 secunde | OK. | 10 | 10 | ||
7 | Depășit | Limita de timp depășită | 10 | 0 | ||
8 | Depășit | Limita de timp depășită | 10 | 0 | ||
9 | Depășit | Limita de timp depășită | 10 | 0 | ||
Punctaj total | 40 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema lant2 face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
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ă.