lexicografic

Lexicografic

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 250.000$
* $T ≤ 2500$

* într-un fişier de intrare suma totală a lungimilor şirurilor corespunzătoare celor $T$ teste nu va depăşi 250.000

* Într-un fişier de intrare suma totală a lungimilor şirurilor corespunzătoare celor $T$ teste nu va depăşi 250.000.

* $1 ≤ K ≤ N*(N-1)/2$
* $1 ≤ v[i] ≤ N$, pentru $1 ≤ i ≤ N$

* Vă rugăm să acordaţi atenţie *tipului de date* necesar pentru a citi valorea lui K
* Pentru acordarea punctajului pe un fişier de test este necesară rezolvarea corectă a *tuturor* celor T teste
* Pentru teste în valoare de $5$ puncte se garantează $K = N * (N - 1) / 2$
* Pentru alte teste în valoare de $7$ puncte se garantează $K = 1$
* Pentru alte teste în valoare de $23$ de puncte se garantează $T ≤ 10, N ≤ 50$
* Pentru alte teste în valoare de $4$ puncte se garantează $T ≤ 10, N ≤ 100$
* Pentru alte teste în valoare de $12$ puncte se garnatează $T ≤ 10, N ≤ 500$
* Pentru alte teste în valoare de $24$ de puncte se garnatează $T ≤ 10, N ≤ 2000$

* Vă rugăm să acordaţi atenţie *tipului de date* necesar pentru a citi valorea lui $K$.
* Pentru acordarea punctajului pe un fişier de test este necesară rezolvarea corectă a *tuturor* celor $T$ teste.
* Pentru teste în valoare de $5$ puncte se garantează $K = N * (N - 1) / 2$.
* Pentru alte teste în valoare de $7$ puncte se garantează $K = 1$.
* Pentru alte teste în valoare de $23$ de puncte se garantează $T ≤ 10, N ≤ 50$.
* Pentru alte teste în valoare de $4$ puncte se garantează $T ≤ 10, N ≤ 100$.
* Pentru alte teste în valoare de $12$ puncte se garnatează $T ≤ 10, N ≤ 500$.
* Pentru alte teste în valoare de $24$ de puncte se garnatează $T ≤ 10, N ≤ 2000$.

* Un şir $a{~1~}, a{~2~},..., a{~n~}$ este mai mic lexicografic decât un alt şir $b{~1~}, b{~2~},..., b{~n~}$ dacă există un număr întreg $P$ mai mic sau egal cu $N$ astfel încât:

$a{~1~} = b{~1~}, a{~2~} = b{~2~}, ... , a{~P–1~} = b{~P–1~}, iar a{~P~} < b{~P~}$

$a{~1~} = b{~1~}, a{~2~} = b{~2~}, ... , a{~P–1~} = b{~P–1~}, iar a{~P~} < b{~P~}$.

h2. Exemplu

h3. Explicaţie
Pentru primul test:

Şirul este format din $N = 5$ elemente, şi anume $v=(4,2,3,1,1)$. Putem efectua $K=2$ interschimbări. Interschimbând elementele @$v[1]$@ şi $v[2]$ obţinem şirul $(2,4,3,1,1)$, apoi după interschimbarea elementelor $v[3]$ şi $v[2]$ se obţine şirul minim lexicografic $(2,3,4,1,1)$.

Şirul este format din $N = 5$ elemente, şi anume $v=(4,2,3,1,1)$. Putem efectua $K=2$ interschimbări. Interschimbând elementele @v[1]@ şi @v[2]@ obţinem şirul $(2,4,3,1,1)$, apoi după interschimbarea elementelor @v[3]@ şi @v[2]@ se obţine şirul minim lexicografic $(2,3,4,1,1)$.

== include(page="template/taskfooter" task_id="lexicografic") ==