|
Название задачи: Праздники. |
 |
Условие
Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (субботы и воскресенья), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни.
В зависимости от того, на какой день недели приходится 1 января, количество нерабочих дней, которые идут подряд, может меняться.
Требуется определить, какое наибольшее количество нерабочих дней может идти подряд.
Формат входных данных
Во входном файле a.in записано единственное число K (1 £ K £ 50).
Формат выходных данных
В выходной файл a.out требуется записать единственное число - наибольшее количество нерабочих дней, идущих подряд.
Примеры
|
a.in |
a.out |
|
2 |
4 |
|
10 |
16 |
Также доступны документы в формате DOC
Решение
Тесты и проверяющая программаРешим сначала более простую задачу: будем считать, что праздниками являются только первые K дней года. Попробуем вывести явную формулу, выражающую количество выходных дней WK через K. Для маленьких K можно вычислить значения WK вручную:
|
K |
1 |
2 |
3 |
4 |
5 |
|
WK |
3 |
4 |
5 |
6 |
9 |
Теперь заметим, что если любое из значений K увеличить на 5, то количество выходных дней увеличится на 7. Поэтому WK +5 = WK + 7. Теперь нетрудно написать и явную формулу:
WK = 2 + (K mod 5) + 7*(K div 5),
где mod - взятие остатка, а div - получение целой части от деления (как в языке Паскаль).
Теперь перейдем к решению оригинальной задачи: вспомним про 23 февраля и 8 марта.
Итак, нам требуется найти такой год, на который придется наибольшее количество подряд идущих выходных дней. Год бывает високосным (29 дней в феврале) и не високосным (28 дней в феврале), причем как тот, так и другой может начинаться с любого из семи дней недели. Таким образом, нам придется перебрать 14 вариантов, и выбрать из них наилучший.
Покажем, как подсчитать общее количество выходных дней для одного из этих вариантов. Будем идти по календарю и считать праздники, выпавшие на выходные (назовем используемую для этого переменную p). Как только мы встречаем праздник, выпавший на субботу или воскресенье, мы увеличиваем p на 1 (здесь под праздничными подразумеваются первые K дней года, а также 23 февраля и 8 марта, заметим, что при заданных в задаче ограничениях K первых праздничных дней года всегда заканчиваются до 23 февраля). Обратно, как только мы встречаем рабочий день, мы уменьшаем p на 1. Когда p станет равна нулю, и мы встретим рабочий день, процесс нужно остановить - это будет первый рабочий день в рассматриваемом году: все дни до него - выходные. После этого нужно дополнительно проверить, не являлись ли выходными 30 и 31 декабря предыдущего года, и при необходимости увеличить общее количество выходных в рассматриваемом варианте.
Покажем, как работает этот алгоритм, на конкретном примере. Пусть k = 10, и первое января - понедельник. Составим такую таблицу:
|
номер дня |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
день недели |
пн |
вт |
ср |
чт |
пт |
сб |
вс |
пн |
вт |
ср |
чт |
пт |
сб |
вс |
пн |
|
p |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
2 |
2 |
2 |
1 |
0 |
0 |
0 |
Мы остановились на первом рабочем дне 15 января, встреченном после того, как значение p стало равно 0. Таким образом, мы получили 14 выходных. Добавим к ним еще два - 30 и 31 декабря предыдущего года (суббота и воскресенье) и получим ответ для данного случая: 16. Перебрав еще 6 случаев (еще 7, относящихся к високосному году, здесь можно не анализировать, так как наше рассмотрение всегда заканчивается январем) и, выбрав наибольший ответ, мы увидим, что приведенное решение и является лучшим для K = 10. Заметим, что оно же могло быть получено и для года, который начинается с субботы:
|
номер дня |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
|
день недели |
сб |
вс |
пн |
вт |
ср |
чт |
пт |
сб |
вс |
пн |
вт |
ср |
чт |
пт |
сб |
вс |
пн |
|
p |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
4 |
4 |
3 |
2 |
1 |
0 |
0 |
0 |
Таким образом дни предыдущего года здесь учитывать не нужно.
Итак, если бы в году было только K праздников, то решение можно было бы получить и по формуле. В полной же постановке задачи проверяется умение аккуратно работать с календарем (правильно определять дату и день недели каждого из рассматриваемых дней), что не для всех оказалось очевидным. Так, основной вопрос, который задавали участники во время тура: "Сколько дней в январе, феврале и марте соответственно?" (хотя последняя информация для решения задачи излишняя). На полный балл задачу решили 57 участников.
Также доступны документы в формате DOC
