В новой математической игре для одного игрока «Таблица чисел» используется таблица размером n строк на m столбцов, заполненная целыми числами. За один ход игрок выбирает одну из строк или один из столбцов и меняет знак на противоположный у всех чисел этой строки или столбца.
Цель игры состоит в том, чтобы привести таблицу в такой вид, что сумма чисел в каждой строке и каждом столбце является неотрицательной. При этом минимизировать количество ходов не требуется, но можно сделать не более 20000 ходов.
Ваша задача состоит в том, чтобы написать программу, которая по описанию начального вида таблицы, найдет последовательность ходов, которая ведет к достижению цели игры, или определит, что цель игры недостижима.
Формат входных данных
Первая строка входного файла содержит два целых числа: n и m (2 ≤ n, m ≤ 100). Каждая из последующих n строк содержит по m целых чиселai,j (|ai,j| ≤ 100).
Формат выходных данных
В первой строке выходного файла выведите k — число ходов, которые необходимо выполнить, или «-1», если цели игры добиться невозможно. В первом случае в последующих k строках выведите описание этих ходов.
Описание каждого хода должно быть выведено в отдельной строке, которые должны содержать: тип хода («R» — на этом ходе выбирается строка или «C» — на этом ходе выбирается столбец) и номер соответствующей строки или столбца. Строки и столбцы нумеруются натуральными числами начиная с единицы, строки нумеруются сверху вниз, а столбцы — слева направо.
Выведенная вашей программой последовательность ходов должна содержать не более 20000 ходов. Гарантируется, что если существует последовательность ходов, ведущая к достижению цели игры, то существует и последовательность, удовлетворяющая указанному ограничению
Примеры
Входные данные | Выходные данные |
2 2 -1 -3 1 -2 | 1 C 2 |
3 2 -1 -1 -1 -1 -1 -1 | 3 R 1 R 2 R 3 |
1. Цель всегда достижима: если есть хотя бы одна строка (или столбец) с отрицательной суммой, мы можем увеличить общую сумму на целое число, домножив эту строку на -1. Общая сумма не может расти неограничено (ограничение сверху - cумма всех модулей). Поэтому в какой-то момент мы придем к ситуации, когда улучшать некуда, то есть сумма в каждой строке и каждом столбце уже неотрицательна.
2. Порядок действий неважен.
3. Каждую строку или столбец достаточно менять не больше одного раза (важна только четность).
Достаточно, чтобы решить?
Не знаю, так ли просто, мне вот неочевидно, что лобовое решение, которое я описала (ну, почти описала), уложится в лимит, но мне лень проверять.
Кстати, а чему там не уложиться-то? Ведь если хранить отдельно суммы по строкам и по столбцам, то можно среди них даже линейный поиск делать.
(Прям как в анекдоте. Сколько майоров нужно, чтобы решить задачку одному рядовому?)
O (n + m) * O(n) * ?
Сколько итераций? Я не знаю, как нормально оценить. Кажется, что не очень много (особенно, если минимум выбирать каждый раз), но грубая оценка у меня получается слишком большая. (m * n * 100 - cтолько раз может меняться сумма, если она меняется каждый раз на 2 от абсолютного минимума до абсолютного максимума).
То есть O (n^5) - многовато.
Можно надеяться, что уложится, но обосновывать лень :)
А, ну и взять слагаемые в скобки, конечно, да.
(Я так понимаю, что проходит и "умножить", и, может, даже не на O(n), а на O (n^2). Сдать уже что ли, посмотреть :))
Наверное что-нибудь типа, на каждом шаге взять столбец или строку с минимальной суммой и инвертировать его. Проверить на правильность.
Вы знаете такой тест?
(Вы можете проверить: вывести на все тесты -1, узнать, сколько тестов прошло).
А что в итоге понадобилось исправить?