Программирование. Задача о сторожах-2
Здравствуйте. В поисках решения своей задачи наткнулась на ваш форум – нашла решение другой задачи, похожей на часть моей -tehnari.ru/f41/t58807 , но целиком решить свою по-прежнему не могу, поэтому обращаюсь к вам за помощью.
Моя задача:
«В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [Т1(i), Т2(i)] - моментов начала и конца дежурства i-го сторожа из интервала [0,EndTime].
Для заданного расписания стражи требуется:
(а) проверить, в любой ли момент в галерее находится не менее двух сторожей.
Если условие (а) не выполнено, то:
(б) перечислить все интервалы времени с недостаточной охраной (менее 2 сторожей).
(в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписание (т.е. удовлетворяющее условию (а)).
(г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать времена дежурства каждого из сторожей с сохранением длительности дежурства.
(д) Если это возможно, то составить расписание с наименьшим числом сдвигов.
ВХОДНЫЕ ДАННЫЕ:
(Все моменты времени задаются в целых минутах.)
EndTime - момент окончания стражи, т.е. охраняется отрезок времени [0, EndTime].
N -число сторожей.
T1, T2, i=1,..N - моменты начала и окончания дежурства i-го сторожа.
Length - длительность дежурства каждого дополнительного сторожа.
ВЫХОДНЫЕ ДАННЫЕ:
(1) Ответ на пункт (а) в форме да/нет.
(2) При ответе “нет” на п. (а) - список пар (k,l) - начал и концов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1).
(3) Число дополнительных сторожей и моменты начала и окончания дежурства каждого дополнительного сторожа.
(4) Ответ на пункт (г) в форме да/нет. Если “да”, то номера сторожей, смена которых сдвигается, и значения сдвигов.
(5) В ответ на пункт (д): наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов.
ПРИМЕЧАНИЕ
Программа должна допускать независимое тестирование пунктов (в), (г), (д).”»
Собственно, как ответить на пункты (а) и (б) я понимаю – пройтись в цикле по каждой минуте, считая количество сторожей, как предлагается в указанной выше теме, или еще можно для всех моментов начала/окончания дежурства (сначала создать из них массив и отсортировать его по возрастанию) получить ряд чисел, указывающих на то, как меняется количество стражей, например, +1, -1 (может быть и несколько), тогда суммируя эти числа можно будет получить количества стражей в каждый момент сдачи/приема дежурства и по ним найти интервалы с недостаточной охраной.
Я буду очень благодарна, если кто-нибудь поможет мне с пунктами (в), (г) и (д).
Что делать с пунктом (в) тоже более-менее понятно из единственного существующего пояснения к этой задаче:
“…Увеличение количества сторожей осуществляется последовательно. Вначале добавляются сторожа в интервалы времени с недостаточной охраной и отстоящие друг от друга на время, большее времени дежурства сторожей. После этого вновь выполняется сортировка и осуществляется поиск интервалов времени с недостаточной охраной. Если они есть, то процесс продолжается, и так до тех пор, пока в любой момент времени в галерее не будут находиться не менее двух сторожей.”
Правильно ли я понимаю, что на каждом шаге мы выбираем все интервалы, на которых 0 или 1 сторож (те, где 0, и те, где 1, рассматриваем отдельно) и время между которыми меньше заданного времени дежурства каждого доп. сторожа (пока возможно, на последнем шаге выбираем все оставшиеся интервалы с недостаточной охраной вне зависимости от времени между ними), и заполняем их до отказа, т.е. для тех, на которых 0, добавляем сразу двух? И если да, то можно ли как-то теоретически обосновать, что при таком подходе количество доп. сторожей будет минимальным?
Как делать пункты (г) и (д) я совсем не понимаю…Единственная зацепка в том, что во всех источниках, где встречается эта задача, она находится в разделе «графы». В одной книге перед ней даны описания алгоритмов расстановки пометок при поиске максимального потока и алгоритма Дейкстры, но я не представляю, к чему они тут. Нужно ли в этих пунктах использовать эти или, может быть, какие-то другие алгоритмы на графах, и если да, то какие и как?
Здравствуйте. В поисках решения своей задачи наткнулась на ваш форум – нашла решение другой задачи, похожей на часть моей -tehnari.ru/f41/t58807 , но целиком решить свою по-прежнему не могу, поэтому обращаюсь к вам за помощью.
Моя задача:
«В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [Т1(i), Т2(i)] - моментов начала и конца дежурства i-го сторожа из интервала [0,EndTime].
Для заданного расписания стражи требуется:
(а) проверить, в любой ли момент в галерее находится не менее двух сторожей.
Если условие (а) не выполнено, то:
(б) перечислить все интервалы времени с недостаточной охраной (менее 2 сторожей).
(в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписание (т.е. удовлетворяющее условию (а)).
(г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать времена дежурства каждого из сторожей с сохранением длительности дежурства.
(д) Если это возможно, то составить расписание с наименьшим числом сдвигов.
ВХОДНЫЕ ДАННЫЕ:
(Все моменты времени задаются в целых минутах.)
EndTime - момент окончания стражи, т.е. охраняется отрезок времени [0, EndTime].
N -число сторожей.
T1, T2, i=1,..N - моменты начала и окончания дежурства i-го сторожа.
Length - длительность дежурства каждого дополнительного сторожа.
ВЫХОДНЫЕ ДАННЫЕ:
(1) Ответ на пункт (а) в форме да/нет.
(2) При ответе “нет” на п. (а) - список пар (k,l) - начал и концов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1).
(3) Число дополнительных сторожей и моменты начала и окончания дежурства каждого дополнительного сторожа.
(4) Ответ на пункт (г) в форме да/нет. Если “да”, то номера сторожей, смена которых сдвигается, и значения сдвигов.
(5) В ответ на пункт (д): наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов.
ПРИМЕЧАНИЕ
Программа должна допускать независимое тестирование пунктов (в), (г), (д).”»
Собственно, как ответить на пункты (а) и (б) я понимаю – пройтись в цикле по каждой минуте, считая количество сторожей, как предлагается в указанной выше теме, или еще можно для всех моментов начала/окончания дежурства (сначала создать из них массив и отсортировать его по возрастанию) получить ряд чисел, указывающих на то, как меняется количество стражей, например, +1, -1 (может быть и несколько), тогда суммируя эти числа можно будет получить количества стражей в каждый момент сдачи/приема дежурства и по ним найти интервалы с недостаточной охраной.
Я буду очень благодарна, если кто-нибудь поможет мне с пунктами (в), (г) и (д).
Что делать с пунктом (в) тоже более-менее понятно из единственного существующего пояснения к этой задаче:
“…Увеличение количества сторожей осуществляется последовательно. Вначале добавляются сторожа в интервалы времени с недостаточной охраной и отстоящие друг от друга на время, большее времени дежурства сторожей. После этого вновь выполняется сортировка и осуществляется поиск интервалов времени с недостаточной охраной. Если они есть, то процесс продолжается, и так до тех пор, пока в любой момент времени в галерее не будут находиться не менее двух сторожей.”
Правильно ли я понимаю, что на каждом шаге мы выбираем все интервалы, на которых 0 или 1 сторож (те, где 0, и те, где 1, рассматриваем отдельно) и время между которыми меньше заданного времени дежурства каждого доп. сторожа (пока возможно, на последнем шаге выбираем все оставшиеся интервалы с недостаточной охраной вне зависимости от времени между ними), и заполняем их до отказа, т.е. для тех, на которых 0, добавляем сразу двух? И если да, то можно ли как-то теоретически обосновать, что при таком подходе количество доп. сторожей будет минимальным?
Как делать пункты (г) и (д) я совсем не понимаю…Единственная зацепка в том, что во всех источниках, где встречается эта задача, она находится в разделе «графы». В одной книге перед ней даны описания алгоритмов расстановки пометок при поиске максимального потока и алгоритма Дейкстры, но я не представляю, к чему они тут. Нужно ли в этих пунктах использовать эти или, может быть, какие-то другие алгоритмы на графах, и если да, то какие и как?
