Fișierul intrare/ieșire cifsort.in, cifsort.out Sursă Concurs Incalzire
Autor Teodor Plop Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.2 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici