Задача 18.
В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [Т1(i), Т2(i)] - моментов начала и конца дежурства i-го сторожа из интервала [0,EndTime].
Для заданного расписания стражи требуется:
(а) проверить, в любой ли момент в галерее находится не менее двух сторожей.
Если условие (а) не выполнено, то:
(б) перечислить все интервалы времени с недостаточной охраной (менее 2 сторожей).
(в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписание (т.е. удовлетворяющее условию (а)).
(г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать времена дежурства каждого из сторожей с сохранением длительности дежурства.
(д) Если это возможно, то составить расписание с наименьшим числом сдвигов.
ВХОДНЫЕ ДАННЫЕ:
(Все моменты времени задаются в целых минутах.)
EndTime - момент окончания стражи, т.е. охраняется отрезок времени [0, EndTime].
N -число сторожей.
T1[i], T2[i], i=1,..N - моменты начала и окончания дежурства i-го сторожа.
Length - длительность дежурства каждого дополнительного сторожа.
ВЫХОДНЫЕ ДАННЫЕ:
(1) Ответ на пункт (а) в форме да/нет.
(2) При ответе "нет" на п. (а) - список пар (k,l) - начал и концов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1).
(3) Число дополнительных сторожей и моменты начала и окончания дежурства каждого дополнительного сторожа.
(4) Ответ на пункт (г) в форме да/нет. Если "да", то номера сторожей, смена которых сдвигается, и значения сдвигов.
(5) В ответ на пункт (д): наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов.
ПРИМЕЧАНИЕ
Программа должна допускать независимое тестирование пунктов (в), (г), (д).
|
