#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 | #51675769 | Utilizator | |
Fișier | lant2.cpp | Dimensiune | 1 B |
Data încărcării | 01 August 2024, 12:54 | Scor / rezultat | Eroare de compilare |
lant2.cpp:1:1: error: 'a' does not name a type a ^
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ă.