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 |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
