Fişierul intrare/ieşire:edist.in, edist.outSursăSelectie Girls Programming Camp
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Edist

Fie un şir oarecare de caractere. Asupra lui definim următoarele 3 operaţii:

  • inserare: pe o poziţie oarecare se adauga un caracter oarecare
  • ştergere: se şterge caracterul de pe o poziţie oarecare din şir
  • înlocuire: se înlocuieşte caracterul de pe o poziţie oarecare din şir cu orice alt caracter.

Se dau două şiruri S1 si S2 conţinând doar litere mici ale alfabetului englez şi având N şi, respectiv, M caractere. Distanţa de editare a celor două şiruri este numărul minim de operaţii definite mai sus ce trebuie aplicat asupra primului şir pentru a-l transforma în cel de-al doilea şir. Acelaşi tip de operaţie poate fi aplicat de mai multe ori. Aflaţi distanţa de editare a celor doua şiruri, ştiind că aceasta este mai mică sau egală cu un număr întreg K dat.

Date de intrare

Pe prima linie a fişierului de intrare edist.in se afla trei numere întregi: N, M şi K. Pe a doua linia a fişierului se află N litere mici din alfabetul englez reprezentând şirul S1. Pe a treia linie a fişierului se află M litere mici din alfabetul englez ce reprezintă şirul S2.

Date de ieşire

În fişierul de ieşire edist.out se va afla un singur număr întreg reprezentând distanţa de editare a celor doua şiruri.

Restricţii

  • 1 ≤ N, M ≤ 20 000
  • 1 ≤ K ≤ 500
  • Pentru 70% din teste N, M ≤ 2 000.

Exemplu

edist.inedist.out
5 6 5
harpa
armura
4
5 5 4
carte
antet
3

Explicaţie

O posibilă modalitate de a transforma şirul harpa în armura folosind 4 operaţii este:

1. ştergem litera h din primul şir,
2. înlocuim litera p cu litera m,
3. adăugăm litera u înainte de ultima literă din primul şir,
4. adăugăm litera r înainte de ultima literă din primul şir.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content