Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | edist.in, edist.out | Sursă | Selectie Girls Programming Camp |
| Autor | Paul-Dan Baltescu | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Edist
Fie un şir oarecare de caractere. Asupra lui definim urmatoarele 3 operatii:
- inserare: pe o poziţie oarecare se adauga un caracter oarecare
- ştergere: se sterge caracterul de pe o pozitie oarecare din sir
- inlocuire: se inlocuieste caracterul de pe o pozitie oarecare din sir cu orice alt caracter.
Se dau doua siruri S1 si S2 continand doar litere mici ale alfabetului englez avand N si, respectiv, M caractere. Distanta de editare a celor doua siruri este numarul minim de operatii definite mai sus ce trebuie aplicat asupra primului sir pentru a-l transforma in cel de-al doilea sir. Acelasi tip de operatie poate fi aplicat de mai multe ori. Aflati distanta de editare a celor doua siruri, stiind ca aceasta este mai mica sau egala cu un numar intreg K dat.
Date de intrare
Pe prima linie a fişierului de intrare edist.in se afla trei numere intregi: N, M si K. Pe a doua linia a fisierului se afla N litere mici din alfabetul englez reprezentand sirul S1. Pe a treia linie a fisierului se afla M litere mici din alfabetul englez ce reprezinta sirul S2.
Date de ieşire
În fişierul de ieşire edist.out se va afla un singur numar intreg reprezentand distanta de editare a celor doua siruri.
Restricţii
- 1 ≤ N ≤ 20 000
- 1 ≤ K ≤ 500
- Pentru 70% din teste, N ≤ 2 000$.
Exemplu
| edist.in | edist.out |
|---|---|
| 5 6 5 harpa armura | 4 |
Explicaţie
O posibila modalitate de a transforma sirul harpa in armura folosind 4 operatii este:
1. stergem litera h din primul sir,
2. inlocuim litera p cu litera m,
3. adaugam litera u inainte de ultima litera din primul sir,
4. adaugam litera r inainte de ultima litera din primul sir.
