Detalii evaluare: ~63362988

Detalii evaluare #63362988

Rezumat problema
Detalii
Evaluare
Ajutor

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 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	`#63362988`	Utilizator	Spartan ® (alexroman07)
Fișier	lant2.cpp	Dimensiune	1.64 KB
Data încărcării	27 Februarie 2026, 21:09	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

lant2.cpp:10:21: error: wrong number of template arguments (1, should be 5)
 unordered_map<string> mp;

                     ^
In file included from /usr/include/c++/4.8/unordered_map:48:0,
                 from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:115,
                 from lant2.cpp:1:
/usr/include/c++/4.8/bits/unordered_map.h:97:11: error: provided for 'template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> class std::unordered_map'
     class unordered_map : __check_copy_constructible<_Alloc>
           ^
lant2.cpp:10:25: error: invalid type in declaration before ';' token
 unordered_map<string> mp;

                         ^
lant2.cpp: In function 'int distanta(std::string, std::string)':
lant2.cpp:14:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<=a.size(); i++)

                             ^
lant2.cpp:16:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<=b.size(); j++)

                                 ^
lant2.cpp: In function 'int main()':
lant2.cpp:44:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<str.size(); i++)

                                  ^
lant2.cpp:51:15: error: no match for 'operator[]' (operand types are 'int' and 'std::string {aka std::basic_string<char>}')
         if (mp[nou]==0)

               ^
lant2.cpp:55:15: error: no match for 'operator[]' (operand types are 'int' and 'std::string {aka std::basic_string<char>}')
             mp[nou]=1;

               ^

Cum funcționează evaluarea?

www.pbinfo.ro permite evaluarea a două tipuri de probleme:

probleme la care rezolvarea presupune scrierea unui program complet
probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.

Problema lant2 face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:

Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.

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ă.

Du-te sus!