Pagini recente » Diferente pentru blog/meet-in-the-middle intre reviziile 26 si 27 | Diferente pentru problema/granite intre reviziile 7 si 4 | Diferente pentru problema/jetoane2 intre reviziile 8 si 7 | Atasamentele paginii Profil Crista4321 | Diferente pentru problema/permsort2 intre reviziile 2 si 3
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="permsort2") ==
Se dă o permutare cu N elemente. Asupra permutării pot fi efectuate două tipuri de mutări:
Alegerea unui prefix şi inversarea lui.
Alegerea unui sufix şi inversarea lui.
Se dă o permutare cu $N$ elemente. Asupra permutării pot fi efectuate două tipuri de mutări:
Vi se cere să sortaţi crescător permutarea folosind operaţiile descrise. Pentru a obţine toate punctele aveţi voie să efectuaţi maximum 2 * N operaţii.
* Alegerea unui prefix şi inversarea lui.
* Alegerea unui sufix şi inversarea lui.
Vi se cere să sortaţi crescător permutarea folosind operaţiile descrise. Pentru a obţine toate punctele aveţi voie să efectuaţi maximum $2 * N$ operaţii.
h2. Date de intrare
Fişierul permsort.in conţine pe prima linie numărul N, iar pe următoarea linie N valori reprezentând o permutare.
Fişierul permsort.in conţine pe prima linie numărul $N$, iar pe următoarea linie $N$ valori reprezentând o permutare.
h2. Date de ieşire
Fişierul de ieşire permsort.out va conţine pe prima linie numărul M de operaţii efectuate. Următoarele M linii vor conţine descrierea operaţiilor efectuate astfel:
Dacă se doreşte inversarea prefixului care se termină la o anumită poziţie se va afişa caracterul P urmat de valoarea poziţiei.
Dacă se doreşte inversarea sufixului care se începe la o anumită poziţie se va afişa caracterul S urmat de valoarea poziţiei.
Fişierul de ieşire permsort.out va conţine pe prima linie numărul $M$ de operaţii efectuate. Următoarele $M$ linii vor conţine descrierea operaţiilor efectuate astfel: dacă se doreşte inversarea prefixului care se termină la o anumită poziţie se va afişa caracterul $P$ urmat de valoarea poziţiei, dacă se doreşte inversarea sufixului care se începe la o anumită poziţie se va afişa caracterul $S$ urmat de valoarea poziţiei.
h2. Restricţii
1 N 1 000 000
Dacă M <= 2 * N veţi obţine punctaj maxim. Dacă 2 * N < M <= 5 * N veţi obţine 50% din punctaj. Pentru M > 5 * N nu se vor acorda puncte.
Pentru 70% din teste N 200 000
* $1 ≤ N ≤ 1 000 000$
* Dacă $M ≤ 2*N$ veţi obţine punctaj maxim. Dacă $2*N < M ≤ 5*N$ veţi obţine $50%$ din punctaj. Pentru $M > 5*N$ nu se vor acorda puncte.
* Pentru $70%$ din teste $N ≤ 200 000$
h2. Exemplu
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
