| Fişierul intrare/ieşire: | similar.in, similar.out | Sursă | ad-hoc |
| Autor | Din Folclor | Adăugată de |  Andreescu Mihai •mihai995 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Similar
Marcel are un seif a cărui cheie este un şir de caractere care conţine numai caractere mici ale alfabetului englez. Gigel vrea să-i spargă seiful. Marcel ştie asta, aşa că a pus un dispozitiv care blochează orice tentativă de deschidere a seifului dacă cheia a fost introdusă greşit.
Într-o zi, însă, a tastat greşit cheia, iar seiful s-a blocat. Pentru a evita astfel de situaţii, Marcel a mai adăugat o regulă: o tastare se consideră greşită doar dacă gradul de similitudine al cheii introduse este mai mare de o anumită valoare. El poate comite următoarele greşeli: poate tasta o altă literă sau poate lovi mai multe taste simultan, adăugând caractere în plus. Deoarece unele erori sunt mai probabile decât altele, Marcel a definit o penalizare pentru fiecare dintre aceste erori, în funcţie de poziţia la care s-a produs. Gradul de similitudine este suma acestor penalizări.
Cerinţă
Pentru o cheie introdusă, cheia corectă penalizările de inserare şi schimbare ale fiecărui caracter, să se determine cel mai mic grad de similitudine care se obţine.
Date de intrare
Fişierul de intrare similar.in va conţine pe prima linie cheia introdusă A, pe a doua linie cheia corectă B, pe a treia linie penalizările la ştergere, iar pe a patra linie, penalizările de modificare. Al i-lea element al unei linii cu penalizările de ştergere sau modificare caracterizează al i-lea element al sirului introdus.
Date de ieşire
În fişierul de ieşire similar.out va conţine un singur număr, reprezentând similitudinea minimă a celor două şiruri.
Restricţii
- $ 1 ≤ |A|, |B| ≤ 2000
- $ 0 ≤ penalizare ≤ 2000000000
Exemplu
| similar.in | similar.out |
|---|---|
| antomionel tonio 1 0 3 7 2 6 2 4 2 2 5 5 5 5 1 5 5 5 5 5 | 10 |
Explicaţie
Se vor elimina primele 2 caractere, ultimele 3 caractere, iar m se va schimba în n, obţinând un cost total de 1 + 0 + 1 + 4 + 2 + 2 = 10
