Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bonus3.in, bonus3.out | Sursă | IIOT 2019-20 Runda 3 |
| Autor | Alexandru Petrescu | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bonus3
Fiindca ar fi fost prea usor sa primiti doar 7 probleme cu pizza 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, toate inversiunile sa aiba un punct comun. Formal, sa existe o pozitie k in asa fel incat pentru orice pereche (i < j) cu Pi > Pj, sa se garanteze ca i ≤ k < j.
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 ≤ 100
- 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.in | bonus3.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. Pentru prima permutare orice k e valid (pentru ca nu exista inversiuni). Pentru a doua, k = 1 e solutie (toate inversiunile sunt realizate de 4 cu elemente din dreapta), iar pentru a treia k = 3 respecta conditia (toate inversiunile sunt realizate de 1 cu elemente din stanga)
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.
