1. Главная
  2. Библиотека
  3. Теория вероятностей
  4. В архиве школы нашли расплывшуюся распечатку: на ней бы...
Разбор задачи

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

  • Предмет: Теория вероятностей
  • Автор: Кэмп
  • #Теория вероятностей и математическая статистика
  • #Дискретная математика
В архиве школы нашли расплывшуюся распечатку: на ней была прямоугольная таблица из нулей и единиц, но сами клетки от влаги почти стерлись. Уцелели только контрольные пометки — для каждой строки и каждого столбца известно, чётно или нечётно количество

Условие:

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

Уцелели только контрольные пометки — для каждой строки и каждого столбца известно, чётно или нечётно количество единиц в них.

Восстановите любую подходящую таблицу или убедитесь, что такой таблицы не существовало.

Формат входных данных
В первой строке вводятся два целых числа
— количество строк и столбцов таблицы.

Во второй строке вводятся
чисел
:
означает чётное число единиц в
-й строке, а
— нечётное.

В третьей строке вводятся
чисел
:
означает чётное число единиц в
-м столбце, а
— нечётное.

Формат результата
Если подходящей таблицы не существует, выведите «NO».

Иначе выведите «YES», а затем любую подходящую таблицу:
строк по
чисел
или
, разделённых пробелами, так чтобы в каждой строке и каждом столбце чётность числа единиц совпадала с заданной.

Решение:

Шаг 1. Необходимое условие существования решения
Заметим, что если посчитать общее количество единиц по всем строкам, то его остаток по модулю 2 равен сумме остатков по всем строкам. Аналогично, если суммировать единицы по столбцам, остаток по модулю 2 равен сумме остатков по столбцам. Но ведь общее число единиц одинаково, независимо от способа подсчёта. Следовательно, должно выполняться условие:
(сумма значений для строк) mod 2 = (сумма значений для столбцов) mod
2.
Если это условие не выполняется, никакой таблицы нет – надо вывести «NO».

Шаг 2. П...

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

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое необходимое условие должно быть выполнено для существования таблицы с заданными чётностями сумм единиц по строкам и столбцам?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Выбери предмет