ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Internal Contest March'2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Transversal

Time limit: 1.0 second
Memory limit: 64 MB
Consider a square table of size (2N + 1) × (2N + 1) with a cells each containing the sign “+” or the sign “-”. We call an arbitrary set of 2N + 1 cells a transversal if each line and each column of the table contain exactly one cell belonging to the set.
By one operation you are allowed to change signs to opposite in all cells of one transversal. You are asked to determine if it is possible to obtain a table containing not more than 2N cells with the sign “+” by a sequence of such operations.


The first line contains a positive integer N not exceeding 20. The next 2N + 1 lines contain the table. They consist of the symbols “+” and “-” without spaces between them.


Output “No solution” if a necessary sequence of operations does not exist. Otherwise output in the first line “There is solution:” and in the next lines a sequence of operations that leads to the required result. Each of these lines should describe one transversal and should contain the integers from 1 to 2N + 1. Number K at position S means that the transversal includes the cell at the intersection of the line number S with the column number K.
If there exist many sequences of operations you may output any one.


There is solution:
1 2 3
2 3 1
1 3 2
3 1 2
Problem Author: Dmitry Filimonenkov
Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session
To submit the solution for this problem go to the Problem set: 1092. Transversal