Fișierul intrare/ieșire | cifsort.in, cifsort.out | Sursă | Concurs Incalzire |
---|---|---|---|
Autor | Teodor Plop | Adăugată de | Teodor Plop • teodor94 |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Cifsort
Se dă un număr N și un vector cu N numere naturale. Asupra elementelor vectorului se pot aplica următoarele operații:
- Adaugă o cifră la începutul sau la finalul unui număr.
- Sterge o cifră de la începutul sau de la sfârșitul unui număr.
Să se afișeze numărul minim de operații ce trebuie aplicate astfel încât să se sorteze vectorul inițial.
Date de intrare
Fișierul de intrare cifsort.in conține pe prima linie numărul natural N, reprezentând numărul de elemente ale vectorului. Pe cea de-a doua linie se vor găsi N numere naturale separate între ele prin câte un spațiu, reprezentând elementele vectorului.
Date de ieșire
În fișierul de ieșire cifsort.out se va găsi un singur număr natural, reprezentând numărul minim de operații ce trebuie aplicate pentru sortarea vectorului.
Restricții
- 1 ≤ N ≤ 100.000
- 1 ≤ v[i] ≤ 1.000.000, unde v[i] este element al vectorului.
Exemplu
cifsort.in | cifsort.out |
---|---|
4 21 22 13 32 |
8 |
Explicație
1. Șterge cifra 2 din al doilea număr. Vectorul devine 21 2 13 32.
2. Adaugă cifra 1 la finalul celui de-al doilea număr. Vectorul devine 21 21 13 32.
3. Șterge cifra 1 din cel de-al treilea număr. Vectorul devine 21 21 3 32.
4. Adaugă cifra 2 la începutul celui de-al treilea număr. Vectorul devine 21 21 23 32.
5. Șterge cifra 3 din al treilea număr. Vectorul devine 21 21 2 32.
6. Adaugă cifra 2 în al treilea număr. Vectorul devine 21 21 22 32.
7. Șterge cifra 2 de la începutul primului număr. Vectorul devine 1 21 22 32.
8. Adaugă cifra 3 la finalul primului număr. Vectorul devine 13 21 22 32.
Am terminat sortarea vectorului. Numărul minim de operații aplicate este 8.