== include(page="template/taskheader" task_id="aranjare3") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $aranjare3.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $aranjare3.out$ ...
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.
h2. Restricţii
h2. Restricţii şi precizări
* $... ≤ ... ≤ ...$
* 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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
3 2 1
| 2 9
0 1
0 1
0 1
1 2
1 2
1 2
2 0
2 0
2 0
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="aranjare3") ==
