Sign Flip Table
InterviewTime limit2sMemory limit1024 MB
Find a sequence of row and column sign flips so every row and column sum of an integer table is non-negative, using at most 20000 moves.
- Level
Medium5 of 10
- Topics
- Matrix, Greedy, Simulation
- Solved
- No attempts yet
Problem
In a new one-player math game called Number Table, a table with rows and columns is filled with integers. In one move, the player picks one row or one column and flips the sign of every number in that row or column.
The goal is to bring the table to a state where the sum of the numbers in every row and every column is non-negative. The number of moves does not need to be minimal, but at most 20000 moves may be made.
Your task is to write a program that, given the initial table, finds a sequence of moves that reaches the goal, or determines that the goal cannot be reached.
Input
The first line contains two integers and (). Each of the next lines contains integers ().
Output
In the first line, print , the number of moves, or -1 if the goal cannot be reached. If the goal can be reached, print the moves in the following lines, one move per line. Each line contains the move type (R if a row is chosen, C if a column is chosen) and the number of that row or column. Rows and columns are numbered from 1, rows from top to bottom and columns from left to right.
The printed sequence must contain at most 20000 moves. It is guaranteed that if a sequence of moves reaching the goal exists, then a sequence satisfying this limit also exists.