Что необходимо знать и понимать, чтобы решить задачу на составление простого расписания?

Question

[Дима]

Здравствуйте, уважаемые пользователи Тостера. Мне необходимо решить такую задачу, но так как опыта решения таких задач у меня нет, а задача решается не так очевидно (если опираться на пример, указанный в условии). Подскажите, что нужно прочитать / изучить / разобрать или к какому типу вообще относятся такие задачи, чтобы найти по ним материал и решить её. Попытки решить "по-простому" и поиски в сети не улучшили ситуацию, разве что указали на математическое/линейное программирование и теорию расписаний. Но в тех книгах, которые я нашел, задачи схожие, но в то же время далеки от этой, на мой взгляд.

В музее N залов. Посещение каждого зала экскурсией школьников занимает 1 час, при этом одновременно в зале может находится только одна группа. В один день на экскурсии записалось M групп школьников, и они хотят обойти все залы. Очевидно, что для посещения музея всеми группами потребуется K = max(M, N) часов, и экскурсоводы должны точно знать, в какой зал в какое время какую группу вести. Создайте расписание посещений залов группами школьников такое, чтобы за K часов все группы посетили все залы.

К сожалению, описание входных и выходных данных не помещается (Тостер обрезает описание). Оригинал задачи размещен здесь (PDF) (стр. 4, зад. 3)

Answer 1

[MiiNiPaa]

Это же элементарно. Сдвиги.

Если M > N, запихиваем в залы групы 1 - N по порядку. Затем группы 2 - N+1, и т.д. За группой M следует группа 1. Повторить M раз.

В случае M < N реение такое же, но придётся делать N проходов и добивать недостающие залы нулями.

Пример для N = 3 M = 5:

1 2 3
2 3 4
3 4 5
4 5 1
5 1 2

Пример для N = 5 M = 2:

1 2 0 0 0
2 0 0 0 1
0 0 0 1 2
0 0 1 2 0
0 1 2 0 0

Пример программы на С++

Comments

[Дима]

Большое спасибо за Ваш ответ!

[Дима]

Спасибо за алгоритм и программу, но результат несколько разнится. По второму столбику идет различие (при 2 5, как в примере).

[MiiNiPaa]

Дима: Вариантов решения много, это всего-лишь 2 из них. Попробуйте проверить: оба подходят (каждая группа посещает каждый зал ровно один раз).

[Дима]

Я понимаю, что подходят оба и про кол-во вариантов решения, но в задаче указаны именно определенные условия, которым вами предложенное решение тоже вроде соответствует, но пример дан не просто так.

[MiiNiPaa]

Дима: В задаче нет дополнительных условий которые бы отсекали какие-либо ответы. Просто приведен один из > 1m вариантов решения.

[Дима]

MiiNiPaa, я с вами полностью согласен, но если взять "по-простому" и подставить числа из примера, а результат реализованной программы будет другой нежели тот, который описан в задаче, а это уже признак, что автор имел в виду что-то другое. Мне кажется страннным давать пример, по которому "нельзя" проверить правильность выполнения задачи.

[MiiNiPaa]

Дима: К задачам со множеством решений нельзя создать эталонный ответ. В таких случаях часто добавляют дополнительные условия, которые отсекают остальные ответы (вывод должен быть сортированным, найти оптимальное решение, и т.д.), либо просят вывести инвариант (минимальное количество шагов, сумма позиций...). Вообще, пример ответа нужен для того, чтобы визуально показать формат вывода, и для самопроверки, чтобы решающий смог проверить, правильно он понял условие.