#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 | #54075601 | Utilizator | |
Fișier | lant2.cpp | Dimensiune | 2.96 KB |
Data încărcării | 19 Noiembrie 2024, 11:07 | Scor / rezultat | 0 puncte |
lant2.cpp: In function 'void read()': lant2.cpp:35:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < v.size(); i++) { ^ lant2.cpp:57:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < temp.size(); i++) { ^ lant2.cpp: In lambda function: lant2.cpp:67:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 1; j <= a2.size(); j++) { ^ lant2.cpp:70:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i <= a1.size(); i++) { ^ lant2.cpp:73:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 1; i <= a1.size(); i++) { ^ lant2.cpp:74:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = 1; j <= a2.size(); j++) { ^ lant2.cpp: In function 'void solve()': lant2.cpp:86:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 2; i <= v.size(); i++) { ^ lant2.cpp:95:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int i = 0; i < v.size(); i++) { ^ lant2.cpp:98:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int j = i + 1; j < v.size(); j++) { ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | Depășit | Limita de timp depășită | 10 | 0 | ||
1 | Depășit | Limita de timp depășită | 10 | 0 | ||
2 | Depășit | Limita de timp depășită | 10 | 0 | ||
3 | Depășit | Limita de timp depășită | 10 | 0 | ||
4 | Depășit | Limita de timp depășită | 10 | 0 | ||
5 | Depășit | Limita de timp depășită | 10 | 0 | ||
6 | Depășit | Limita de timp depășită | 10 | 0 | ||
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 | 0 |
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ă.