| 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 KB |
| Scorul tău | N/A | Dificultate |   2/5 |
Poți vedea testele pentru această problemă accesând atașamentele.Vezi soluțiile 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
