== include(page="template/taskheader" task_id="similar") ==
Poveste și cerință...
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.
h2. 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.
h2. Date de intrare
Fișierul de intrare $similar.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $similar.out$ ...
În fișierul de ieșire $similar.out$ va conține un singur număr, reprezentând similitudinea minimă a celor două șiruri.
h2. Restricții
* $... ≤ ... ≤ ...$
* $ 1 ≤ |A|, |B| ≤ 2000$
* $ 0 ≤ penalizare ≤ 2000000000$
h2. Exemplu
table(example).
|_. similar.in |_. similar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| antomionel
tonio
1 0 3 7 2 6 2 4 2 2
5 5 5 5 1 5 5 5 5 5
| 10
h3. 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
== include(page="template/taskfooter" task_id="similar") ==
