e-olymp 31. Суеверный Дед Мороз

Задача

Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны — развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза «Пятница 13».

Сколько дней Дед Мороз не развозил подарки во время своего дежурства?

Входные данные

В первой строке задано количество смен $k$ дежурства Деда Мороза.

Далее в k строках указаны года $a$ и $b$ ($1920 ≤ a ≤ b ≤ 2050$ по григорианскому календарю), попадающие на очередную смену.

Выходные данные

Вывести количество дней, когда Дед Мороз не будет развозить подарки.

Тесты

Ввод Вывод
1 2
1999 2000
1991 1997
13
2 3
1939 1945
1937 1938
1953 1964
37
3 3
1993 1996
2007 2017
1979 1981
32
4 4
1997 1999
1967 1972
2032 2032
1930 1933
24
5 4
1959 1960
1965 1966
1991 2011
1947 1959
63

Код программы

Решение задачи

Сперва стоит сказать, что полный цикл чередования лет с пятницей 13 в одни и те же месяца — 28 лет. Всего в году их может быть от 1 до 3. Всего в этих 28 годах будут 4 года с тремя пятницами 13 и по 12 с одной и двумя.
Все решение задачи сводится сводится к тому, чтобы посчитать количество пятниц 13 в каждом году данного нам отрезка времени. Создадим два массива — c2 и c3 — каждый будет содержать остатки от деления лет, содержащих 2 и 3 пятницы 13 соответсвенно, на 28. Все прочие остатки от деления «достанутся» годам, в которых 1 пятница 13; отдельный массив для них, очевидно, смысла создавать нет.
Сначала, по условию, вводим число смен и после в цикле года очередной смены. Для каждого года из отдельной смены считаем количество пятниц 13 путём проверки в соответствующих массивах остатка от деления этого года на 28. Если его нет в двух массивах, то, очевидно, в этом году всего одна пятница 13 и мы прибавляем к счетчику пятниц counter 1. Если все-таки есть, то прибавляем 2 или 3 в зависимости от того, в каком массиве нашлось необходимое число. В конце выводим значение счётчика.
Отметим, что задача решается и без использования массивов, но в таком случае придётся проверить остаток от деления каждого года на 28 на равенство числам, которые в данном случае находятся в массивах.

Ссылки

код на ideone
условие задачи на e-olymp

Related Images: