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

Ниже даю подробное решение задачи с пошаговым объяснением и готовым алгоритмом. Если у вас сейчас есть конкретная матрица, дайте её — я пройдусь по алгоритму и дам точный результат (YES/NO и строки инверсии). Пока что — разбор метода и пример реализации. Что задача просит сделать - Есть бинарная матрица A размером Q x N. - Можно инвертировать любые выбранные строки (перевести 0 в 1 и наоборот) и любые выбранные столбцы. - Нужно получить однородную матрицу (все 0 или все 1). При этом считаем, что исход мог быть как черным, так и белым, поэтому допускаются оба варианта. - Если можно, вывести YES и две строки: для строк длиной Q (где 1 означает инвертировать соответствующую строку) и для столбцов длиной N (где 1 означает инвертировать соответствующий столбец). Если невозможно — NO. Математическая модель - Пусть r_i — признак инверсии i-й строки (0 или 1), для i = 1..Q. - Пусть c_j — признак инверсии j-го столбца (0 или 1), для j = 1..N. - После применения инверсий значение в клетке станет A[i][j] xor r_i xor c_j. - Требуем, чтобы итоговая матрица была однородной: все элементы равны некоторому k ∈ {0,1}. - Тогда для фиксированного k получаем матрицу B, определяемую как B[i][j] = A[i][j] xor k. Нужно, чтобы B[i][j] = r_i xor c_j для всех i,j. Как проверить существование решений - Пробуем оба варианта k = 0 и k = 1. - Пусть возьмём k и зададим r_1 = 0 (это без ограничений, выбор эквивалентен, так как можно дописать одно константное flipping-перемещение). - Тогда c_j = B[1][j] для всех j. - Теперь для каждой строки i найдём предполагаемое r_i: r_i = B[i][1] xor c_1. - Проверяем, что для всех j выполняется B[i][j] = r_i xor c_j. - Если для какой-то пары (i,j) это условие нарушается, текущий k невозможен. - Если для обоих k проверка успешна, задача решена. Можно вернуть r_i и c_j как ответ. - Если ни для k не удалось — вернуть NO. Псевдокод решения (Python-подобно) - Вход: матрица A размера Q x N, элементы 0/1. - Выход: "NO" или "YES" и две строки r (длина Q) и c (длина N), где '1' означает инверсию. Формализованный алгоритм 1) Считать Q, N и A[0..Q-1][0..N-1] где A[i][j] ∈ {0,1}. 2) Для k в {0, 1} сделать: a) B[i][j] = A[i][j] xor k b) c[j] = B[0][j] для всех j c) для i от 0 до Q-1: r[i] = B[i][0] xor c[0] для j от 0 до N-1: если B[i][j] != r[i] xor c[j], перейти к следующему k (неудачно) d) если цикл прошёл успешно, вернуть YES, r и c 3) Если ни один k не сработал, вернуть NO. Пример реализации (Python-подобный код) def solve_matrix(A): Q = len(A) N = len(A[0]) for k in (0, 1): # B = A xor k B = [[A[i][j] ^ k for j in range(N)] for i in range(Q)] c = B[0][:] # c_j = B[0][j] r = [0] * Q ok = True for i in range(Q): r[i] = B[i][0] ^ c[0] for j in range(N): if (r[i] ^ c[j]) != B[i][j]: ok = False break if not ok: break if ok: # Преобразовать r и c в строки '0'/'1' r_str = ''.join('1' if x else '0' for x in r) c_str = ''.join('1' if x else '0' for x in c) return ("YES", r_str, c_str) return ("NO", None, None) Как трактовать результат - Если мы получили YES, то: - В строке r_str символ i равен '1' если нужно инвертировать i-ю строку. - В строке c_str символ j равен '1' если нужно инвертировать j-й столбец. - В случае NO такая конфигурация инверсий не существует. Замечания и полезные моменты - Восстановление возможно не всегда: структура B должна быть суммой по модулю 2 двух векторов r и c. - Мы проверяем оба варианта k, потому что исходный кадр мог быть либо черным, либо белым, как сказано в задаче. - Сложность очень маленькая: O(2 * Q * N), где Q,N ≤ 100, что легко в рамках ограничений. Если хотите, пришлите конкретную матрицу Q x N (строки по порядку без пробелов, как в входе задачи), и я выполню шаги выше и дам точный результат (YES/NO и соответствующие строки инверсий).