Permsort2

permsort2

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

Poveste şi cerinţă...

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

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.

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

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

* $... ≤ ... ≤ ...$

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

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

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

|
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") ==