Реши

Клёво задача на расписание. По изображению видно, что таблица состоит из 6 уроков (строки 1–6) и 6 временных окон/классов (столбцы: 9а, 9б, 10а, 10б, 11а, 11б). Темные клетки означают, что в соответствующий урок в этом классе идёт урок физкультуры. Задача такова: - определить минимальное число учителей ФК (при таком расписании); - найти вариант расписания, при котором можно обойтись двумя учителями; - распределить между тремя учителями Ивановым, Петровым, Савиным сами уроки так, чтобы в каждом окне (уроке) было одинаковое число уроков на учителя и т. д. Разбор и решения 1) Как определить минимальное число учителей - В принципе, учитель не может вести более одного урока одновременно. Значит, в каждый конкретный урок (один столбец таблицы) число параллельно проводимых уроков ФК определяет, сколько учителей нужно именно в этот момент. - Минимальное число учителей равно максимальной загрузке по столбцам: M = max число темных клеток в любом столбце. 2) Что по изображению - По картинке в некоторых столбцах видно, что в одном из них задействовано три класса одновременно (есть три темных клетки в одном столбце). Это означает, что минимально нужно как минимум 3 учителя ФК. - Следовательно, двух учителей здесь недостаточно: существует урок, в который одновременно заняты три класса, т.е. хотя бы три параллельных занятия ФК требуют трех разных учителей. Итого: - Минимальное количество учителей: 3. - Раскрыватель для варианта на двух учителей: невозможен, потому что в одном уроке задействовано три класса. 3) Как распределить между тремя учителями (Иванов, Петров, Савин) В идеале нам нужно распределить каждую темную клетку по одному из трёх учителей так, чтобы в каждом столбце все занятие шли под разными учителями (если в столбце три темные клетки — под Ивановым, Петровым и Савиным), а также общее число уроков на каждого учителя было одинаковым (условие третьего пункта задачи). Что можно сделать пошагово: - Шаг 1. Посчитать общее число темных клеток T (всех занятий ФК по всей таблице). - Шаг 2. Если T не делится на 3, равного распределения между тремя учителями не будет (один из условий нарушится). В этом случае нужно либо изменить трактовку задачи, либо согласовать, что количество уроков на учителя может не быть строго одинаковым. - Шаг 3. Если T делится на 3 (например, T = 9, 12 и т. д.), можно приступить к раскраске: - В каждом столбце с 3 темными клетками назначаем по одному учителю на каждую клетку: Иванов, Петров, Савин (в любом порядке). Это обеспечивает, что в этот момент никто не будет перегружен. - В столбцах с 2 темными клетками назначаем двух учителей так, чтобы суммарно по всем столбцам общее число уроков на каждого учителя получалось одинаковым. Часто помогает циклическо чередовать порядок распределения в столбцах с двумя клетками (например, в первом таком столбце — Ивана и Петрова, во втором — Петрова и Савина и т. д.). - В столбцах с одной темной клеткой — присваиваем этот урок одному из учителей, чья общая нагрузка сейчас меньше всего, чтобы добиться равенства по итогам. Важно: чтобы привести конкретное распределение для вашего изображения, надо точно знать, какие именно клетки темные в каком столбце. Сейчас на изображении достаточно размыто, чтобы безошибочно перечислить все пары (класс–урок) и их соответствие. Но можно сделать так: - посчитать T и проверить, делится ли на 3; - затем применить описанный выше принцип: для столбцов с 3 клетками — распределяем по Иванову, Петрову, Савину; для столбцов с 2 клетками — распределяем по двум учителям так, чтобы итоговый баланс был близок к равному; для столбцов с 1 клеткой — на слабую нагрузку; - в конце можно немного подправить порядок в столбцах с двумя клетками, чтобы точно привести к равному числу уроков на каждого учителя (если T делится на 3). Если T = 9, например, каждому учителю должно приходиться по 3 урока. Что нужно от вас для точного готового расписания - Желательно получить более чёткое изображение таблицы (или сам список, какие клетки темные: например, в каком столбце и в каких строках находится темная клетка). - Либо можно переписать в текстовом виде: для каждого столбца перечислите номера уроков (1–6), в которых в этом классе проходит урок ФК. Я могу сделать точное распределение по трём учителям прямо сейчас, как только увижу точную раскладку темных клеток. Если отправите более ясное изображение или текстовую раскладку, дам готовый вариант с указанием, кому именно какой урок учит Иванов/Петров/Савин так, чтобы: - в каждом уроке учителей не more чем; - общее число уроков на каждого учителя было одинаковым (если это возможно по вашей раскладке).