Fişierul intrare/ieşire: | cifsort.in, cifsort.out | Sursă | Concurs Incalzire |
Autor | Teodor Plop | Adăugată de | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 8192 kbytes |
Scorul tău | N/A | Dificultate |
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.