Problem matrice2


Se dă o matrice cu N linii și 2 coloane de numere întregi. Liniile sunt numerotate cu numere de la 1 la N, iar coloanele cu 1 și 2.
Există 4 operații care pot fi executate asupra matricii: \(S_3, J_3, S_4, J_4\) .
La o operație \(J_k\) se aleg k linii (distincte) ale matricii și se permută circular în jos, iar la o operație \(S_k\) se aleg k linii (distincte) și se permută circular în sus (k=3,4).

\[\begin{vmatrix} \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ \end{vmatrix} \rightarrow \begin{vmatrix} \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ \end{vmatrix} \\ \]

\[\text{Operație } J_3 \]

\[\begin{vmatrix} \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ \end{vmatrix} \rightarrow \begin{vmatrix} \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ \end{vmatrix} \\ \]

\[\text{Operație } S_3 \]

Operațiile \(S_4\) si \(J_4\) sunt similare, numai că în loc de 3 linii se aleg 4.

Cerința

Scrieți un program care prin efectuarea a cel mult 2N operații de tip \(S_3, J_3, S_4, J_4\) asupra matricii date să o transforme astfel încât nici una dintre coloanele ei să nu conțină un subșir strict crescător de lungime mai mare decât \(\lceil \sqrt{N} \rceil\) (adică cel mai mic întreg mai mare sau egal decât \(\sqrt{N}\) ).

Date de intrare

Fișierul de intrare matrice.in conține pe prima linie numărul natural N. Pe fiecare din următoarele N linii sunt câte 2 numere întregi separate printr-un spațiu, reprezentând elementele matricii.

Date de ieșire

Fișierul de ieșire matrice.out va conține câte o operație pe linie. O operație este identificată prin tipul ei (poate fi J3, S3, J4 sau S4) și 3 numere (pentru J3 și S3) sau 4 numere (pentru J4 și S4) în ordine strict crescătoare, reprezentând rândurile asupra cărora este executată operația. Tipul operației și celelalte numere trebuie să fie separate prin exact un spațiu.
Atenție! Tipul operației este format din două caractere scrise fără spațiu între ele.

Restricții și precizări

  • 6 ≤ N ≤ 30000
  • Un subșir strict crescător al unui șir \(a_1, a_2, ..., a_N\) este un șir \(a_{i_1}, a_{i_2}, ..., a_{i_k}\), unde \(1 ≤ i_1 < i_2 < ... < i_K ≤ N\) și \(a_{i_1} < a_{i_2} < ... < a_{i_k}\).
  • Elementele matricii sunt numere întregi mai mari sau egale cu 0 și mai mici sau egale cu 65000.

Exemplu

matrice.in

6
1 2
3 1
4 4
6 3
5 5
2 6

matrice.out

S4 1 3 4 5
J3 4 5 6

Explicație

Dupa efectuarea operațiilor, matricea va fi

4 4
3 1
6 3
2 6
5 5
1 2

Lungimea celui mai lung subșir strict crescător de pe prima coloană este 2, iar de pe cea de-a doua este 3 (2 si 3 sunt mai mici sau egale decât \(\lceil \sqrt{N} \rceil = \lceil \sqrt{6} \rceil = 3\) ).

General info

ID: 107

Upload: liviu

Input: matrice.in/matrice.out

Memory limit: 64MB/16MB

Time limit: 0.05s

Source: ONI 2005 XI-XII: Ziua 1, Problema 2

Submissions

Special Submissions