matrice

Time limit: 0.05s
Memory limit: 64MB
Input: matrice.in
Output: matrice.out

Se dă o matrice cu NN linii și 22 coloane de numere întregi. Liniile sunt numerotate cu numere de la 11 la NN, iar coloanele cu 11 și 22.

Există 44 operații care pot fi executate asupra matricii: S3,J3,S4,J4S_3, J_3, S_4, J_4 .

La o operație JkJ_k se aleg kk linii (distincte) ale matricii și se permută circular în jos, iar la o operație SkS_k se aleg kk linii (distincte) și se permută circular în sus (k=3,4k=3,4).

x1x2y1y2z1z2z1z2x1x2y1y2\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} \\ Operație J3\text{Operație } J_3 x1x2y1y2z1z2y1y2z1z2x1x2\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} \\ Operație S3\text{Operație } S_3

Operațiile S4S_4 si J4J_4 sunt similare, numai că în loc de 33 linii se aleg 44.

Cerința

Scrieți un program care prin efectuarea a cel mult 2N2N operații de tip S3,J3,S4,J4S_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 N\lceil \sqrt{N} \rceil (adică cel mai mic întreg mai mare sau egal decât N\sqrt{N} ).

Date de intrare

Fișierul de intrare matrice.in conține pe prima linie numărul natural NN. Pe fiecare din următoarele NN linii sunt câte 22 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 33 numere (pentru J3 și S3) sau 44 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

  • 6N30 0006 \leq N \leq 30 \ 000;
  • Un subșir strict crescător al unui șir a1,a2,...,aNa_1, a_2, ..., a_N este un șir ai1,ai2,...,aika_{i_1}, a_{i_2}, ..., a_{i_k}, unde 1i1<i2<...<iKN1 ≤ i_1 < i_2 < ... < i_K ≤ N și ai1<ai2<...<aika_{i_1} < a_{i_2} < ... < a_{i_k};
  • Elementele matricii sunt numere întregi mai mari sau egale cu 00 și mai mici sau egale cu 65 00065 \ 000.

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

După 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 22, iar de pe cea de-a doua este 33 (22 si 33 sunt mai mici sau egale decât N=6=3\lceil \sqrt{N} \rceil = \lceil \sqrt{6} \rceil = 3 ).

Problem info

ID: 107

Editor: liviu

Author:

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

Tags:

ONI 2005 XI-XII

Log in or sign up to be able to send submissions!