Fişierul intrare/ieşire:cpr.in, cpr.outSursăRMI 2016
AutorFlorin ChiricaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cut-paste-reverse

Se consideră o listă de numere întregi (1, 2, ..., N) . Pe această listă puteţi efectua o serie de operaţii de tipul cut-paste. O operaţie de acest tip <x, y, z> implică extragerea secvenţei dintre valorile x şi y şi inserarea acesteia imediat după valoarea z (sau la începutul listei în caz că z este 0). Acest triplet este considerat corect, dacă:

  • x apare înaintea lui y în listă, sau x = y.
  • z apare înafara secvenţei de la x la y, sau z = 0.

Găsiţi o serie de operaţii corecte pentru a răsturna lista, adică pentru a obţine lista (N, N-1, ..., 1). Cu cât mai puţine operaţii folosiţi, cu atât scorul va fi mai mare.

Date de intrare

Fişierul de intrare cpr.in va conţine pe prima linie numărul natural N, reprezentând lungimea listei.

Date de ieşire

Fişierul de ieşire cpr.out trebuie să conţină pe prima linie valoarea M, reprezentând numărul de operaţii cut-paste. Fiecare din următoarele M linii trebuie să conţină trei numere întregi x, y şi z, aferente operaţiei.

Restricţii

  • 1 ≤ N ≤ 5.000
  • Se va acorda punctaj maxim pe test dacă M \leq [\frac{N}{2}] + 1.
  • Se va acorda 80% din punctajul testului dacă  [\frac{N}{2}] + 1 < M \leq [\frac{2N}{3}] .
  • Se va acorda 60% din punctajul testului dacă  [\frac{2N}{3}] < M \leq [\frac{3N}{4}] .
  • Se va acorda 40% din punctajul testului dacă  [\frac{3N}{4}] < M \leq [\frac{4N}{5}] .
  • Se va acorda 20% din punctajul testului dacă  [\frac{4N}{5}] < M \leq [\frac{5N}{6}] .
  • Nu se va acorda nimic dacă se folosesc mai mult de [\frac{5N}{6}] operaţii sau dacă operaţiile nu conduc la o listă răsturnată.

Exemplu

cpr.incpr.out
6
4
2 6 0
4 5 0
3 6 4
6 5 0

Explicaţie

Lista initială este (1 2 3 4 5 6). 
În urmă primei operaţii, lista devine (2 3 4 5 6 1) (şi operaţia 1 1 6 ar fi avut acelaşi rezultat).
După cea de a doua operaţie, lista devine (4 5 2 3 6 1).
După cea de a treia operaţie, lista devine (4 3 6 5 2 1).
După cea de a patra operaţie, lista devine (6 5 4 3 2 1). 

Această soluţie obţine punctaj maxim, întrucât s-au efectuat doar 4 = [\frac{6}{2}] + 1 operaţii, iar lista a fost răsturnată.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?