ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98690
Тема:    [ Прочие задачи на аккуратную реализацию ]
Сложность: 3
Классы: 8,9,10,11
Название задачи: Праздники.
В корзину
Прислать комментарий

Условие

Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые 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

Источники и прецеденты использования

олимпиада
Название Московская городская олимпиада по информатике
год
Название 2005 год
задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .