Блог пользователя FORWARD

Автор FORWARD, 14 лет назад, По-русски

В новой математической игре для одного игрока «Таблица чисел» используется таблица размером n строк на m столбцов, заполненная целыми числами. За один ход игрок выбирает одну из строк или один из столбцов и меняет знак на противоположный у всех чисел этой строки или столбца.

Цель игры состоит в том, чтобы привести таблицу в такой вид, что сумма чисел в каждой строке и каждом столбце является неотрицательной. При этом минимизировать количество ходов не требуется, но можно сделать не более 20000 ходов.

Ваша задача состоит в том, чтобы написать программу, которая по описанию начального вида таблицы, найдет последовательность ходов, которая ведет к достижению цели игры, или определит, что цель игры недостижима.

Формат входных данных

Первая строка входного файла содержит два целых числа: n и m (2  nm  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


http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=2528&chapterid=3021#1
Какой алгоритм использовать при решении?
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Задача интересная. Я пока что не могу придумать решение полностью, но, кажется, смотреть стоит в таком направлении: либо свести задачу к системе линейных уравнений и решить по методу Гаусса; либо свести задачу к системе линейных разностных ограничений и решить её с использованием алгоритма Беллмана - Форда.
14 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Ну, смотрите:
1. Цель всегда достижима: если есть хотя бы одна строка (или столбец) с отрицательной суммой, мы можем увеличить общую сумму на целое число, домножив эту строку на -1. Общая сумма не может расти неограничено (ограничение сверху - cумма всех модулей). Поэтому в какой-то момент мы придем к ситуации, когда улучшать некуда, то есть сумма в каждой строке и каждом столбце уже неотрицательна.
2. Порядок действий неважен.
3. Каждую строку или столбец достаточно менять не больше одного раза (важна только четность).

Достаточно, чтобы решить?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет.
    >Цель всегда достижима: если есть хотя бы одна строка (или столбец) с отрицательной суммой
    Если нет строки, где сумма отрицательна, значит цель уже достигнута. В каком случае цель будет недостижима?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я там поставила двоеточие, оно означает, что вторая часть предложения (и еще несколько следующих предложений) разъясняет первую.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Значит я ищу строку или столбец (который можно умножить на -1, чтобы общая сумма стала на некоторое число больше), затем если не нахожу и общая сумма отрицательна, то останавливаюсь, если же нет то задача решена. 
        Так?
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Общая сумма - сумма сумм по всем столбцам. Сумма неотрицательных чисел не может быть отрицательной. А так вроде правильно.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            >Общая сумма - сумма сумм по всем столбцам
            и по строкам?
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              или по строкам. Можно просуммировать по столбцам, а можно по строкам. Сумма будет одинаковой. Суммировать и то и то не стоит. Хотя все равно получим неотрицательное число.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как всё просто... А я написал какую-то жесть, а мне ещё и заплюсовали... Стыдно, стыдно...
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Все подумали, что то, что ты написал-это шутка:)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ага, а на контесте, если б я с отчаяния что-то такое отсабмитил, все бы не просто посмеялись над удачной шуткой, но и пристрелили бы с первого же челленджа :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я подумала, что вы издеваетесь :)

      Не знаю, так ли просто, мне вот неочевидно, что лобовое решение, которое я описала (ну, почти описала), уложится в лимит, но мне лень проверять.
      • 14 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
        Не, у меня принцип - даже издеваясь, не высказывать ложных утверждений. То есть, если бы я знал решение, я бы не написал, что не знаю.

        Кстати, а чему там не уложиться-то? Ведь если хранить отдельно суммы по строкам и по столбцам, то можно среди них даже линейный поиск делать.
        (Прям как в анекдоте. Сколько майоров нужно, чтобы решить задачку одному рядовому?)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну, надо прикидывать: (поиск отрицательной строки/столбца) * (пересчет всех изменившихся сумм) * (количество итераций).
          O (n + m) * O(n) * ?
          Сколько итераций? Я не знаю, как нормально оценить. Кажется, что не очень много (особенно, если минимум выбирать каждый раз), но грубая оценка у меня получается слишком большая. (m * n * 100 - cтолько раз может меняться сумма, если она меняется каждый раз на 2 от абсолютного минимума до абсолютного максимума).
          То есть O (n^5) - многовато.

          Можно надеяться, что уложится, но обосновывать лень :)
          • 14 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
            Так там ведь в формуле самый первый знак - он не умножить, он плюс :)
            А, ну и взять слагаемые в скобки, конечно, да.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Да, если еще подумать, то плюс. Это-то как раз и неочевидно.
              (Я так понимаю, что проходит и "умножить", и, может, даже не на O(n), а на O (n^2). Сдать уже что ли, посмотреть :))
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
(не туда)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мне кажется здесь не должно быть сложного решения.
Наверное что-нибудь типа, на каждом шаге взять столбец или строку с минимальной суммой и инвертировать его. Проверить на правильность.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Способом Jokser'a прошло все тесты, (кроме одного, но это мелочи, это моя ошибка -1 не выводит, легко исправить).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Нет.
Просто все тесты прошли, а на 4ом тесте "Неправильный формат вывода"
Я так понял, что у меня там пустую строку выводит. И скорее всего там ответ -1.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тогда уж скорее "0".
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      нет, "0" учитывается.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Но минус единицы-то не бывает :)
        (Вы можете проверить: вывести на все тесты -1, узнать, сколько тестов прошло).
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          Поверю вам) вы уже наверно проверили).
          Все исправил. Проходит все.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я, конечно, не проверяла, регистрироваться там еще. Я доказала :)
            А что в итоге понадобилось исправить?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Эти задачи с очного тура прошлого года?