Не так много задач на динамическое программирование разобрано на канале, давайте исправляться. Условие:
Разнообразные входные данные, но ограничения не очень большие. Должна легко решать на языке Python.
Так как олимпиада должна помещаться в один месяц, а размер месяца всего лишь до 100000, то можно завести массив такого размера и пометить все дни, в которые проводить олимпиаду нельзя. Давайте так и сделаем.
Считывание первого блока входных данных очень простое:
После этого идёт список еженедельных выходных, заданных номерами дней недели. Заведём список с нулями на каждый день месяца и каждый выходной пометим числом -1 в этом списке (для этого достаточно пройтись по списку с шагом w):
В шестой строке есть формула нахождения первого дня месяца по дню недели. Когда в задачах встречается кольцо вычетов (вычисления с остатками от деления), удобно нумеровать с нуля. Так и я предполагаю здесь, что дни недели и дни месяца нумеруются с нуля (поэтому и список на n элементов, а не на n + 1).
С разовыми праздниками ещё проще:
Единственный подвох здесь в считывании данных и тестах. Обычно принято, что файл заканчивается пустой строкой. Здесь же получается, что если праздничных дней нет, то пятая строка входных данных уже пустая. А в условии задачи не сказано, что входные данные содержат шесть строк (шестая пустая). Поэтому, при dm равном нулю, попытка считать следующую строку может приводить (если шестой нет) к ошибке выполнения, этого можно избежать, добавив условие.
Итак, данные считали, выходные пометили. Теперь надо придумать динамику. Можно для каждого дня посчитать, сколько прошло дней с предыдущего выходного (включая этот день). Тогда, если прошло не меньше k дней, то этот день может быть днём окончания олимпиады.
Тогда состоянием динамики будет номер дня. Переходы возможны только из предыдущего дня, но тут два случая. Если день праздничный, то ноль праздничных прошло, иначе - на один больше, чем вчера.
Так и запишем:
Обратите внимание на обработку первого дня. С ним тоже возможны два случая, но оба подходят под одну формулу. Либо это выходной (там стоит -1) и тогда надо записать 0, либо это не выходной (там стоит 0) и тогда надо записать 1.
Теперь осталось посчитать, сколько чисел в списке не меньше, чем k. Можно воспользоваться стандартными функциями:
Фильтруем, строим список и смотрим его длину.
Получилось несложное решение, но с, как минимум, одним подводным камнем. А если учесть, что проверяющая система не показывает развёрнутое сообщение об ошибке при Runtime error, то это может стать для кого-нибудь камнем преткновения.
Предыдущий выпуск: Задача 541. Две строки
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
