COCI '09 Contest 5 #6 Chuck

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

You are given a matrix of R rows and C columns. All elements of the matrix are by their absolute value smaller than or equal to 10^4. You may perform the following operations:

Operation Notation Example
Rotate i-th row of the matrix k elements right rotR i k rotR 3 1
\begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{pmatrix} \to \begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 7 & 8 \\ 10 & 11 & 12\end{pmatrix}
Rotate j-th column of the matrix k elements down rotS j k rotS 3 2
\begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{pmatrix} \to \begin{pmatrix}1 & 2 & 9 \\ 4 & 5 & 12 \\ 7 & 8 & 3 \\ 10 & 11 & 6\end{pmatrix}
Multiply all elements in the i-th row by -1,
if and only if none of them were multiplied before.
negR i negR 2
\begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{pmatrix} \to \begin{pmatrix}1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{pmatrix}
Multiply all elements in the j-th column by -1,
if and only if none of them were multiplied before.
negS j negS 1
\begin{pmatrix}1 & 2 & 3 \\ 0 & 0 & 0 \\ 7 & 8 & 9 \\ 10 & 11 & 12\end{pmatrix} \to \begin{pmatrix}-1 & 2 & 3 \\ 0 & 0 & 0 \\ -7 & 8 & 9 \\ -10 & 11 & 12\end{pmatrix}

Using a limited number of these operations, you need to maximize the sum of all the elements of the matrix.

Input Specification

The first line of input contains two integers R and C (1 \le R, C \le 100), number of rows and columns.

The next R lines contain C integers each. All integers are by their absolute value smaller than 10^4.

Output Specification

The first line of output should contain two integers, the maximal sum obtainable and the number of operations used. We shall call this number T.

The next T lines should contain any sequence of operations leading to the sum. Each operation should follow the notation defined in the table below. For details look at sample test cases.

If the obtained sum is not maximal, one of the elements was multiplied more than once or the sequence of operations printed does not lead to the sum, 0 points are awarded.

Otherwise, the number of points depends on the number of operations used

  • For T \le 5 \times R \times C, you are awarded 100\% of points allocated to that test case
  • For 5 \times R \times C < T \le 100\,000, you are awarded 50\% of points allocated to that test case
  • For T > 100\,000, you are awarded 0 points for that test case

Sample Input 1

3 4
1 -2 5 200
-8 0 -4 -10
11 4 0 100

Sample Output 1

345 2
rotS 2 1
negR 2

Sample Input 2

3 3
8 -2 7
1 0 -3
-4 -8 3

Sample Output 2

34 4
rotR 1 1
rotS 3 1
negR 2
negR 3

Comments

There are no comments at the moment.