Fişierul intrare/ieşire: | cpr.in, cpr.out | Sursă | RMI 2016 |
Autor | Florin Chirica | Adăugată de | Bogdan Ciobanu •bciobanu |
Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/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 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ă .
- Se va acorda 80% din punctajul testului dacă .
- Se va acorda 60% din punctajul testului dacă .
- Se va acorda 40% din punctajul testului dacă .
- Se va acorda 20% din punctajul testului dacă .
- Nu se va acorda nimic dacă se folosesc mai mult de operaţii sau dacă operaţiile nu conduc la o listă răsturnată.
Exemplu
cpr.in | cpr.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 operaţii, iar lista a fost răsturnată.