ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1092. Трансверсаль

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Рассмотрим квадратную таблицу размером (2N + 1) × (2N + 1), в каждой из ячеек которой стоит знак «+» или «-». Трансверсаль – это произвольное множество из 2N + 1 ячейки, такое, что каждая строка и каждый столбец таблицы содержат ровно одну ячейку, принадлежащую этому множеству.
Рассмотрим операцию, состоящую в изменении всех знаков на противоположные во всех ячейках некоторой трансверсали. Вам нужно определить, можно ли с помощью последовательности таких операций получить таблицу, содержащую не более 2N ячеек со знаком «+».

Исходные данные

В первой строке содержится целое положительное число N, не превышающее 20. Следующие 2N + 1 строки содержат таблицу. Они состоят из символов «+» и «-» без пробелов между ними.

Результат

Если искомой последовательности операций не существует, выведите фразу «No solution». В противном случае в первой строке выведите «There is solution:», а в следующих строках – последовательность операций, приводящую к требуемому результату. Каждая из этих строк должна описывать одну трансверсаль и содержать целые числа от 1 до 2N + 1. Число K в позиции S означает, что трансверсаль включает в себя ячейку на пересечении строки номер S и столбца номер K.
Если подходящих последовательностей операций много, вы можете вывести любую из них.

Пример

исходные данныерезультат
1
+++
++-
+-+
There is solution:
1 2 3
2 3 1
1 3 2
3 1 2
Автор задачи: Дмитрий Филимоненков
Источник задачи: USU Open Collegiate Programming Contest March'2001 Senior Session