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

Ниже подробное решение задачи с объяснениями и рабочий код на Python. Идея решения - Пусть мы решаем задачу так, чтобы после инверсий все элементы стали одинаковыми (0 или 1). Пусть r_i — флаг инверсии строки i, c_j — флаг инверсии столбца j. - После инверсий значение в клетке (i, j) станет a_ij xor r_i xor c_j. - Пусть итоговое значение равно t (0 или 1). Тогда для всех i, j выполняется: a_ij xor r_i xor c_j = t. Это эквивалентно a_ij xor t = r_i xor c_j. - Возьмем фиксированное t (попробуем t = 0 и t = 1). Пусть строка 0 не инвертируется (r_0 = 0). Тогда столбцы можно определить как c_j = a_0j xor t (для каждой j). Далее для каждой строки i нужно найти r_i так, чтобы для всех столбцов j выполнялось a_ij xor t = r_i xor c_j. - Если для некоторой i и любого j равенство нарушается, то для данного t решение невозможно. Пробуем другое t. Если для t = 0 или t = 1 решение находится — выводим YES и соответствующие маски для строк и столбцов. Если ни для одного t решения нет — NO. Пошаговый алгоритм 1) Прочитать матрицу A размером Q x N (символы '0'/'1'). 2) Для t в {0, 1}: - Вычислить c_j = (a_0j xor t) для всех j. - Для i = 0 задать r_0 = 0. - Для каждой i > 0 вычислить r_i = (a_i0 xor t) xor c_0. - Проверить, что для всех i, j выполняется (a_ij xor t) == (r_i xor c_j). Если да — нашли решение. 3) Если нашли решение для хотя бы одного t, вывести YES, затем строки из r_i и c_j (1 — инвертировать такую строку/столбец, 0 — оставить как есть). Если решений нет — NO. Сложность - Время: O(2 * Q * N) ∈ O(QN). - Память: O(Q + N) для хранения флагов. Рабочий код на Python import sys def solve(): data = sys.stdin.read().strip().split() if not data: return it = iter(data) Q = int(next(it)) N = int(next(it)) mat = [] for _ in range(Q): s = next(it) # При необходимости можно проверить длину, но предполагаем корректный вход mat.append(s) def attempt(t): # c_j = a_0j xor t c = [ ((1 if mat[0][j] == '1' else 0) ^ t) for j in range(N) ] r = [0] * Q # r_0 уже 0 for i in range(1, Q): # r_i = (a_i0 xor t) xor c_0 ri = ((1 if mat[i][0] == '1' else 0) ^ t) ^ c[0] r[i] = ri for j in range(N): bij = ((1 if mat[i][j] == '1' else 0) ^ t) if (ri ^ c[j]) != bij: return None return r, c ans = None for t in (0, 1): res = attempt(t) if res is not None: ans = res break if ans is None: print("NO") return r, c = ans print("YES") print(''.join('1' if x else '0' for x in r)) print(''.join('1' if x else '0' for x in c)) if __name__ == "__main__": solve() Как использовать - Вход: Первая строка: Q N (1 ≤ Q, N ≤ 100) Далее Q строк по N символов 0/1 — исходный кадр. - Выход: NO — если восстановить однородный кадр невозможно; иначе YES, затем две строки: - строка из Q символов 0/1 — инвертировать ли соответствующие строки (1 — инверсия); - строка из N символов 0/1 — инвертировать ли столбцы (1 — инверсия). Если корректных ответов несколько, можно вернуть любой.