Fişierul intrare/ieşire:bonus3.in, bonus3.outSursăIIOT 2019-20 Runda 3
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu alexpetrescu
Timp execuţie pe test0.1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bonus3

Fiindca ar fi fost prea usor sa primiti doar 7 probleme in concurs, comisia s-a gandit sa va dea in cadou si o permutare. Dar pentru ca traim in zilele noastre, se doreste, din punct de vedere moral cel putin, sa o dati si voi mai departe. Modificata. Cat mai putin. In asa fel incat sa respecte anumite proprietati.

Se da o permutare. Sa se realizeze cat mai putine interschimbari de cate 2 elemente consecutive din permutare, in asa fel incat, pentru permutarea finala, Pi - Pi-1 = 1 pentru cel putin N - 2 indici i intre 2 si N.

Date de intrare

Fişierul de intrare bonus3.in contine pe prima linie numarul T de teste. Fiecare test contine pe prima linie ordinul permutarii, numarul natural N, si pe a doua linie permutarea, adica N numere distincte intre 1 si N.

Date de ieşire

În fişierul de ieşire bonus3.out se afla T linii, pe fiecare linie fiind numarul minim de interschimbari cerut la testul corespunzator.

Restricţii

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ 50.000
  • Pentru 10 puncte, N ≤ 7
  • Pentru inca 20 de puncte, N ≤ 50
  • Pentru inca 10 puncte, una din permutarile finale pentru care se poate obtine numar minim de interschimbari este permutarea identitate (1, 2, ..., N)
  • Pentru inca 10 puncte, raspunsul este intotdeauna cel mult egal cu 2

Exemplu

bonus3.inbonus3.out
5
4
1 2 3 4
4
4 1 2 3
4
2 3 4 1
5
3 2 1 5 4
6
1 2 4 3 5 6
0
0
0
4
1

Explicaţie

Sunt T = 5 teste. In primele 3 teste, permutarile deja respecta proprietatea ceruta, deci nu e nevoie de interschimbari.
Permutarea a patra poate fi adusa din 4 interschimbari de elemente consecutive fie la 1 2 3 4 5 fie la 2 3 4 5 1.
In permutarea a cincea e suficient sa interschimbam pe 3 cu 4 si se obtine permutarea identitate.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?