Задача
Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны — развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза «Пятница 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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> #include <algorithm> using namespace std; int c2[12] = {16, 18, 19, 25, 1, 2, 3, 4, 7, 8, 13, 14}; int c3[4] = {21, 24, 27, 10}; int main (){ int a, year1, year2, counter = 0; cin >> a; while (a--){ cin >> year1 >> year2; for (int i = year1; i <= year2; i++){ if (any_of(begin(c2), end(c2), [=](int n){return n == i%28;})) counter+=2; else if(any_of(begin(c3), end(c3), [=](int n){return n == i%28;})) counter+=3; else counter++; } } cout << counter; return 0; } |
Решение задачи
Сперва стоит сказать, что полный цикл чередования лет с пятницей 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
Для отправки комментария необходимо войти на сайт.