Fişierul intrare/ieşire:similar.in, similar.outSursăad-hoc
AutorDin FolclorAdăugată demihai995Andreescu Mihai mihai995
Timp execuţie pe test0.2 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici