Inverseaza reviziile

Diferente pentru problema/permsort2 intre reviziile #1 si #6

Diferente intre titluri:

permsort2

Permsort2

Diferente intre continut:

== include(page="template/taskheader" task_id="permsort2") ==

Poveste şi cerinţă...

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.
 
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 de intrare $permsort2.in$ ...

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

În fişierul de ieşire $permsort2.out$ ...

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 ≤ 100 000$
* Dacă $M &le; 2*N$ veţi obţine punctaj maxim. Dacă $2*N < M &le; 5*N$ veţi obţine $50%$ din punctaj. Pentru $M > 5*N$ nu se vor acorda puncte.
* Pentru $70%$ din teste $N &le; 50 000$

h2. Exemplu
table(example). |_. permsort2.in |_. permsort2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6
6 5 4 1 2 3
| 2
S 4
P 6

|
h3. Explicaţie

...

După prima operaţie permutarea devine:
$6 5 4 3 2 1$
A două operaţie inversează tot şirul, iar permutarea devine sortată.

== include(page="template/taskfooter" task_id="permsort2") ==
 

== include(page="template/taskfooter" task_id="permsort2") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 

9062