Тесты и проверяющая программаРешим сначала более простую задачу: будем считать, что праздниками являются только первые K дней года. Попробуем вывести явную формулу, выражающую количество выходных дней WK через K. Для маленьких K можно вычислить значения WK вручную:
Теперь заметим, что если любое из значений
K увеличить на 5, то количество выходных дней увеличится на 7. Поэтому
WK +5 =
WK + 7. Теперь нетрудно написать и явную формулу:W
K = 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