== include(page="template/taskheader" task_id="aranjare3") ==
Tanaka are o stivă cu $N$ elemente şi vrea să le sorteze în ordine crescătoare de la bază spre vârf. Pentru a realiza acest lucru, el poate să achiziţioneze $M$ stive suplimentare şi să efectueze $K$ operaţii. O operaţie constă în a lua un element din vârful unei stive şi a-l insera în vârful unei alte stive. Tanaka poate alege convenabil valorile lui $M$ şi $K$. Ajutaţi-l pe Tanaka să sorteze elementele astfel încât $M * K$ să aibă valoare cât mai mică şi toate valorile să ajungă pe stiva iniţială în ordine crescătoare de la bază spre vârf.
h2. Cerinţă
Afişaţi o secvenţă de $K$ operaţii care folosesc $M$ stive suplimentare în aşa fel încât să sortaţi elementele de pe stiva iniţială în ordine crescătoare de la bază spre vârf.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $aranjare.in$ va conţine pe primul rând un număr natural nenul $N$. Pe al doilea rând se află o permutare a mulţimii ${1, 2, …, N}$ ce reprezintă valorile iniţiale pe stiva lui Tanaka. Ultimul element din permutare este cel aflat în vârful stivei.
Fişierul de intrare $aranjare3.in$ ...
h2. Date de ieşire
Fişierul de ieşire $aranjare.out$ va conţine pe primul rând numerele naturale $M$ şi $K$. Pe următoarele $K$ rânduri se vor scrie perechi de numere $s t$ (câte o pereche pe fiecare rând) reprezentând mutarea elementului din vârful stivei $s$ în vârful stivei $t$. Se consideră că stiva iniţială a lui Tanaka are indicele $0$, iar cele $M$ stive suplimentare au indicii $1, 2, …, M$.
Pentru acordarea punctelor este necesar ca după executarea tuturor operaţiilor indicate în fişierul de ieşire, elementele din stiva 0 să fie ordonate crescător de la bază spre vârf.
În fişierul de ieşire $aranjare3.out$ ...
h2. Restricţii şi precizări
h2. Restricţii
* Pentru teste în valoare de $25$ de puncte avem $N = 980$. Pentru celelalte teste avem $N = 10 000$.
* Pentru testele cu $N = 980$, punctajele se acordă în modul următor:
** Dacă $M * K ≤ 60 000$, se acordă $100%$ din punctajul testului respectiv
** Dacă $60 000 < M * K ≤ 200 000$, se acordă $60%$ din punctajul testului respectiv
** Dacă $200 000 < M * K ≤ 3 000 000$ se acordă $20%$ din punctajul testului respectiv
* Pentru testele cu $N = 10 000$, punctajele se acordă în modul următor:
** Dacă $M * K ≤ 800 000$, se acordă $100%$ din punctajul testului respectiv
** Dacă $800 000 < M * K ≤ 6 000 000$, se acordă $60%$ din punctajul testului respectiv
** Dacă $6 000 000 < M * K ≤ 300 000 000$ se acordă $20%$ din punctajul testului respectiv
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. aranjare3.in |_. aranjare3.out |
| 3
3 2 1
| 2 9
0 1
0 1
0 1
1 2
1 2
1 2
2 0
2 0
2 0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="aranjare3") ==
