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
.
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}\) ).
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.
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.
6 ≤ N ≤ 30000
0
și mai mici sau egale cu 65000
.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
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\) ).
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