Fişierul intrare/ieşire:triaj.in, triaj.outSursăLot Botosani 2012 - Baraj 3 Seniori
AutorCosmin-Mihai TutunaruAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test10 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Triaj

Î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.

Cerinţă

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.

Date de intrare

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.

Date de ieşire

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.

Restricţii

  • 3 ≤ N ≤ 1 000 000
  • Numerele de pe vagoane sunt valori naturale cel mult egale cu 230
  • 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.

Exemplu

triaj.intriaj.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content