#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 | #49462173 | Utilizator | |
Fișier | lant2.cpp | Dimensiune | 2.80 KB |
Data încărcării | 03 Martie 2024, 00:29 | Scor / rezultat | Eroare de compilare |
lant2.cpp:23:11: error: '::main' must return 'int' void main() ^ lant2.cpp: In function 'int main()': lant2.cpp:26:1: error: 'ofstream' was not declared in this scope ofstream fout(OutFile); ^ lant2.cpp:26:1: note: suggested alternative: In file included from /usr/include/c++/4.8/ios:38:0, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/fstream:38, from lant2.cpp:1: /usr/include/c++/4.8/iosfwd:160:34: note: 'std::ofstream' typedef basic_ofstream<char> ofstream; ^ lant2.cpp:26:10: error: expected ';' before 'fout' ofstream fout(OutFile); ^ lant2.cpp:30:1: error: 'fout' was not declared in this scope fout<<nr[0]<<endl; ^ lant2.cpp:30:14: error: 'endl' was not declared in this scope fout<<nr[0]<<endl; ^ lant2.cpp:30:14: note: suggested alternative: In file included from /usr/include/c++/4.8/istream:39:0, from /usr/include/c++/4.8/fstream:38, from lant2.cpp:1: /usr/include/c++/4.8/ostream:564:5: note: 'std::endl' endl(basic_ostream<_CharT, _Traits>& __os) ^ lant2.cpp:25:5: warning: unused variable 'i' [-Wunused-variable] int i; ^ lant2.cpp: In function 'void Citire()': lant2.cpp:45:2: error: 'ifstream' was not declared in this scope {ifstream fin(InFile); ^ lant2.cpp:45:2: note: suggested alternative: In file included from /usr/include/c++/4.8/ios:38:0, from /usr/include/c++/4.8/istream:38, from /usr/include/c++/4.8/fstream:38, from lant2.cpp:1: /usr/include/c++/4.8/iosfwd:157:34: note: 'std::ifstream' typedef basic_ifstream<char> ifstream; ^ lant2.cpp:45:11: error: expected ';' before 'fin' {ifstream fin(InFile); ^ lant2.cpp:47:2: error: 'fin' was not declared in this scope fin>>k; fin.get(); ^
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ă.