Rezumat problemă

lant2

#2191

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.

Olimpiada județeană de informatică, 2005

Fișiere Pracsiu Dan (dnprx) Emanuela Cerchez concurs

Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate Grafuri orientate Distanta Levenshtein

Rezolvă

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	#64938700	Utilizator	Saleh Nadir (Al_Nadir)
Fișier	lant2.cpp	Dimensiune	1.98 KB
Data încărcării	17 Iunie 2026, 19:35	Scor/rezultat	100 puncte

Evaluare

Mesaj compilare

lant2.cpp: In function ‘int editDistance(std::string, std::string)’:
lant2.cpp:10:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   10 |     for (int i = 0; i <= a.size(); ++i)
      |                     ~~^~~~~~~~~~~
lant2.cpp:11:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   11 |         for (int j = 0; j <= b.size(); ++j)
      |                         ~~^~~~~~~~~~~
lant2.cpp:15:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   15 |     for (int i = 1; i <= a.size(); ++i)
      |                     ~~^~~~~~~~~~~
lant2.cpp:18:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   18 |     for (int j = 1; j <= b.size(); ++j)
      |                     ~~^~~~~~~~~~~
lant2.cpp:21:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   21 |     for (int i = 1; i <= a.size(); ++i)
      |                     ~~^~~~~~~~~~~
lant2.cpp:23:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   23 |         for (int j = 1; j <= b.size(); ++j)
      |                         ~~^~~~~~~~~~~
lant2.cpp: In function ‘int main()’:
lant2.cpp:75:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   75 |     for (int i = 0; i < words.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~
lant2.cpp:76:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   76 |         for (int j = i + 1; j < words.size(); ++j)
      |                             ~~^~~~~~~~~~~~~~
lant2.cpp:81:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   81 |     for (int i = 0; i < words.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~
lant2.cpp:84:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   84 |     for (int i = 0; i < words.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~
lant2.cpp:96:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::__cxx11::basic_string<char> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   96 |     for (int i = 0; i < words.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~
lant2.cpp:69:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |     freopen("lant2.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lant2.cpp:70:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |     freopen("lant2.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Rezultat evaluare

Cum funcționează evaluarea?