== include(page="template/taskheader" task_id="triaj") ==
Poveste şi cerinţă...
{!>problema/triaj?cats.jpg!}
p<>. Într-o zonă unde se face triajul vagoanelor sunt exact $1013$ linii ferate paralele, numerotate de la $1$ la $1013$, legate între ele prin două linii laterale plus o linie suplimentară ca în figură.
Pe linia $1$ se află iniţial $N$ vagoane, fiecare vagon având un număr scris pe el. Numerele de pe vagoane nu sunt neapărat distincte. $Ronnie „The Rocket” O’Sullivan$, care s-a lăsat de snooker şi s-a angajat la $CFR$ ca să o impresioneze pe sora lui $Alex$, doreşte să ordoneze crescător vagoanele tot pe linia $1$, putând face doar următorul tip de operaţie: selectează o linie şi un capăt (stânga sau dreapta) din care extrage o secvenţă de oricâte vagoane şi plasează fiecare vagon pe orice linie în orice capăt. El poate efectua cel mult două operaţii de extragere din fiecare linie, câte maximum una pentru fiecare capăt. Dar poate efectua oricâte operaţii de plasare a vagoanelor pe orice linie. Linia suplimentară şi cele laterale sunt doar pentru a asigura transportul vagoanelor dintr-o parte în alta, pe acestea neputând staţiona vagoane.
h2. Cerinţă
p<>. Să se determine o succesiune de operaţii de extragere şi plasare a vagoanelor pe care le poate efectua $Ronnie$ astfel încât în final pe linia $1$ vagoanele să fie ordonate crescător după numerele asociate.
h2. Date de intrare
Fişierul de intrare $triaj.in$ ...
p<>. Fişierul de intrare $triaj.in$ conţine numărul natural $N$. Pe linia a doua se află $N$ numere naturale separate prin câte un spaţiu reprezentând, de la stânga la dreapta, valorile asociate celor $N$ vagoane aflate pe linia $1$.
h2. Date de ieşire
În fişierul de ieşire $triaj.out$ ...
p<>. Fişierul de ieşire $triaj.out$ va conţine pe prima linie un număr natural $M$ reprezentând numărul de operaţii efectuate. Pe următoarele $M$ linii se vor afla descrise fiecare din cele $M$ operaţii. Fiecare linie mai întâi conţine trei numere naturale $L, C şi V$, unde $L$ este numărul liniei de unde se extrag vagoane, $C$ este capătul de unde se extrag $(0 –$ capătul stâng, $1 –$ capătul drept), $V$ numărul de vagoane extrase. Urmează pe aceeaşi linie $2 * V$ numere naturale, câte două pentru fiecare vagon reprezentând linia şi capătul unde va fi introdus.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N ≤ 1 000 000$
* Numerele de pe vagoane sunt valori naturale cel mult egale cu $2^30^$
* Pentru fiecare test, dacă ordonarea vagoanelor se face corect, va fi acordat punctajul în funcţie de $x$, acesta fiind numărul maxim de extrageri de la un capăt al unei linii:
** Dacă $x ≤ 1$, se primeşte întregul punctaj
** Dacă $x ≤ 2$, se primeşte $80%$ din punctaj
** Dacă $x ≤ 4$, se primeşte $60%$ din punctaj
** Dacă $x ≤ 8$, se primeşte $40%$ din punctaj
** Dacă $x > 8$, se primeşte $20%$ din punctaj
* Pentru $15%$ din teste, valorile de pe vagoane sunt de cel mult $2 000$
* Pentru încă $20%$ din teste, $N ≤ 2 000$
* Pentru încă $40%$ din teste, valorile de pe vagoane sunt de cel mult $1 000 000$
* Ancorat în sinergia progresului $CFR$, infatigabilul $Ronnie$ a evitat cu sagacitate meandrele inextricabile ale crizei economice, având un salariu mirobolant.
h2. Exemplu
table(example). |_. triaj.in |_. triaj.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. triaj.in |_. triaj.out |_. Explicaţii |
| 4
2 6 13 2
| 4
1 1 4 2 1 13 1 6 1 2 1
13 0 1 1 0
6 0 1 1 0
2 0 2 1 0 1 0
| *Prima operaţie:* se extrag de la linia 1, capătul drept, 4 vagoane, deci în ordinea 2, 13, 6, 2. Vagonul cu
valoarea 2 se pune la linia 2, capătul drept; cel cu valoare 13 se pune la linia 13, capătul drept; al treilea
vagon (de valoare 6) se pune la capătul drept al liniei 6; ultimul vagon se pune la capătul drept al liniei 2.
*A doua operaţie:* se extrage de la linia 13, de la capătul stâng, un vagon, care se pune pe la capătul stâng al
liniei 1.
*A treia operaţie:* se extrage de la linia 6, din capătul stâng al liniei, un vagon, care se pune capătul stâng al
liniei 1.
*A patra operaţie:* Se extrag de la linia 2 cele două vagoane de valoare 2 şi se depun ambele pe la capătul stâng
la linia 1. |
== include(page="template/taskfooter" task_id="triaj") ==
