În timpul concursului limita de timp a fost majorată la 1.5s. Acum am schimbat-o înapoi la 1s pentru a încuraja găsirea unor soluții mai eficiente.
Enunț
Omul fantastic găsește o permutare de grad n. Acesta poate să modifice orice element al permutării, dar cu un cost. Astfel acesta alege și , astfel încât și divide , iar se va modifica în , cu costul . Toată lumea știe că lui nu îi place dezordinea. Acesta vrea să găsească costul minim pentru a obține un șir sortat crescător, nu neapărat strict, după finalul tuturor modificărilor. Totuși nu este tipul care ar implementa Slope-Trick la Marytone și decide să vă ceară ajutorul.
Cerință
Fiind date si permutarea , ajutați-l pe Omul fantastic.
Date de intrare
Fișierul de intrare divixori.in
conține pe prima linie un număr natural . Pe a doua linie se vor afla numere naturale, , reprezentând elementele permutării .
Date de ieșire
Fișireul de ieșire divixori.out
conține un număr natural reprezentând costul minim pentru a obține un șir sortat crescător, nu neapărat strict, după finalul tuturor modificărilor.
Restricții și precizări
- Definiția operației
- Atenție! Cerința este să implementați funcția
solve()
. Codul pe care îl veți trimite nu va conține functiamain()
— aceasta va fi înlocuită de funcțiasolve()
. Iată un exemplu de un program valid:
long long solve(int n, int p[]) {
return 0;
}
- Pentru teste în valoare de avem
- Pentru teste în valoare de avem
- Pentru teste în valoare de avem
- Pentru teste în valoare de avem
- Pentru teste în valoare de avem
Exemplul 1
divixori.in
6
1 4 2 3 6 5
divixori.out
10
Exemplul 2
divixori.in
6
6 5 4 3 2 1
divixori.out
21
Explicații
Pentru primul exemplu putem modifica din în și din în , costul total fiind .
Pentru al doilea exemplu singura modalitate este să modificăm toate elementele în , costul total fiind .