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

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

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

Условие:

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

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

В первой строке вводятся два целых числа 1 ⩽ n, m ⩽ 100 — количество строк и столбцов таблицы.
Во второй строке вводятся n чисел r1, ..., rn: ri = 0 означает чётное число единиц в i-й строке, а ri = 1 — нечётное.
В третьей строке вводятся m чисел c1, ..., cm: ci = 0 означает чётное число единиц в j-м столбце, а ci = 1 — нечётное.

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

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

Решение:

Шаг 1. Считываем входные данные. Нам даны числа n и m – количество строк и столбцов, затем список из n чисел (для каждой строки: 0 – требуется чётное число единиц, 1 – нечётное) и m чисел (для каждого столбца).

Шаг 2. Проверяем, чтобы общее условие выполнилось. Заметим, что суммарное число единиц по строкам должно совпадать (по модулю 2) с суммарным числом единиц по столбцам. То есть сумма значений рядам (по модулю 2) должна равняться сумме значений столбцам (по модулю 2). Если условие не выполнено, решения не существует – выводим «NO».

Шаг 3. Если условие выполнен...

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

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

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

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

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

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

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

Топ 3 ошибок

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

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