Fişierul intrare/ieşire:cifsort.in, cifsort.outSursăConcurs Incalzire
AutorTeodor PlopAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.2 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici