Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы настраиваете предобработку данных для компьютерного зрения. Камера выдаёт бинарный кадр — прямоугольную таблицу размера Q × N, где в каждой ячейке записано число 0 или 1. Во время калибровки используется заведомо однородный тестовый кадр: либо объектив закрыт (ожидаются только нули), либо камера смотрит на равномерный белый экран (ожидаются только единицы). Из-за ошибки полярности у части линий сенсора некоторые строки или столбцы записались «наоборот». Предобработчик позволяет выполнять два вида действий: • выбрать некоторые строки и в каждой выбранной строке заменить все нули на единицы, а все единицы на нули; • выбрать некоторые столбцы и в каждом выбранном столбце заменить все нули на единицы, а все единицы на нули. Можно ли с помощью таких действий восстановить однородный кадр, то есть сделать так, чтобы все клетки таблицы стали одинаковыми (либо все 0, либо все 1)? Заметим, что мы не знаем, какой именно тест был в момент съёмки (чёрный или белый), поэтому допускаются оба варианта. Формат выходных данных Первая строка содержит два целых числа Q, N, (1 <= Q, N <= 100). Далее Q строк по N символов 0/1 - исходный кадр (без пробелов внутри строки). Формат выходных данных Выведите NО, если восстановить однородный кадр невозможно. Иначе выведите ҮЕЅ, затем строку из Q символов 0/1, показывающую, какие строки нужно инвертировать (символ 1 означает инверсию строки), и на следующей строке - N символов 0/1, показывающих, какие столбцы нужно инвертировать (символ 1 означает инверсию столбца). Если корректных ответов несколько, выведите любой. Ввод 3 4 0110 0010 1111 Вывод NO Ввод 2 2 10 01 Вывод YES 10 01 Ввод 1 1 0 Вывод YES 0 0

Коротко о задаче - Можно инвертировать произвольную подмножество строк и произвольную подмножество столбцов. - Нужно получить однородный кадр (все нули или все единицы). - Пусть исходная матрица A размеру Q x N. Пусть r_i = 1, если инвертируем строку i, иначе 0; c_j аналогично для столбца j. - После инверсий клетка (i, j) станет A[i][j] XOR r_i XOR c_j. - Требуется либо A[i][j] XOR r_i XOR c_j = 0 для всех i,j, либо = 1 для всех i,j. Идея решения - Попробуем оба варианта: сделать кадр нулём (k = 0) или единицей (k = 1). - Для фиксированного k запишем B[i][j] = A[i][j] XOR k. Нам нужно разложить B как r_i XOR c_j. Для этого достаточно подобрать r и c так, чтобы B[i][j] = r_i XOR c_j для всех i,j. - Одно конструктивное решение: зафиксируем r_0 = 0. Тогда: - c_j = B[0][j] (значения первой строки задают столбцовые инверсии). - r_i = B[i][0] XOR c_0 (значение первого столбца вместе с c_0 задаёт остальные строки). - Проверяем, что для всех i,j выполняется B[i][j] = r_i XOR c_j. - Если для k = 0 или k = 1 найдётся такая пара (r, c), значит можно получить однородный кадр; выведем YES и сами маски r и c. Иначе – NO. Пошаговый алгоритм 1) Прочитать Q, N и матрицу A (символы '0'/'1'). 2) Для k в {0, 1}: - Вычислить B[i][j] = A[i][j] XOR k. - Задать r_0 = 0. - Задать c_j = B[0][j] для всех j. - Задать r_i = B[i][0] XOR c_0 для всех i. - Проверить: для всех i, j выполняется B[i][j] == (r_i XOR c_j). - Если выполняется, вывести: YES строку из Q бит (r_i, где 1 означает инверсию строки) строку из N бит (c_j, где 1 означает инверсию столбца) и завершить программу. 3) Если ни для k=0, ни для k=1 подход не нашёлся, вывести NO. Пояснение корректности - Если существует набор r и c такой, что A[i][j] XOR r_i XOR c_j ровно равен константе k, то для этого k матрица B = A XOR k удовлетворяет B[i][j] = r_i XOR c_j. Первая строка даёт c_j, а первый столбец вместе с c_0 задаёт остальные r_i. Проверка на всех клетках гарантирует корректность. - Это решение зафиксировано в O(QN) для каждого k, итого O(QN), что комфортно для Q,N ≤ 100. Пример разборов - Пример 1: Ввод: 3 4 0110 0010 1111 Попробуем k=0, получаем B=A. Конструктивно строим r и c и проверяем. Проверка не проходит, значит соответствие не найдено для k=0. Попробуем k=1, B = A XOR 1. Повторяем построение и проверку. Проверка снова не проходит. Значит: NO. - Пример 2: Ввод: 2 2 10 01 k=0 даёт совместимость: можно выбрать r=[0,1], c=[1,0] (или эквивалентные). Вывод может быть: YES 10 01 Здесь строки инвертируются: только 2-я, столбцы: только 1-й. - Пример 3: Ввод: 1 1 0 k=0 даёт r=[0], c=[0]. Вывод: YES 0 0 Формат вывода - Если восстановить однородный кадр невозможно: вывести NO. - Иначе: YES затем строка из Q символов 0/1 — маска инверсий строк (1 означает инвертировать соответствующую строку) затем строка из N символов 0/1 — маска инверсий столбцов (1 означает инвертировать соответствующий столбец) Замечания по реализации - Обработку можно выполнять в памяти целиком, размеры ≤ 100x100. - Можно реализовать на любом языке; в псевдокоде выше приведён понятный алгоритм. - При наличии нескольких решений можно вывести любое. Если хотите, могу привести конкретную реализацию на выбранном языке (например, Python) или прогнать ещё один конкретный пример пошагово.