Задача

Как известно, в разные годы дежурят и развозят подарки разные Деды Морозы. Но все они суеверны — развозят подарки на протяжении всего года, кроме дней, когда на календаре Деда Мороза «Пятница 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

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

#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;
}

#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

Related Images:

Похожее

2 thoughts on “e-olymp 31. Суеверный Дед Мороз”

Мазурок Игорь Евгеньевич says: 23/12/2018 at 18:47

Необычное решение.
Уточните пожалуйста, о каком типе промежутков идёт речь: сегменте (отрезке), интервале или полуинтервале. В условии с этим как-то не однозначно.

Войдите, чтобы ответить
- Николь Метри says: 23/12/2018 at 19:20
  
  Уточнила. Речь идёт об отрезке/сегменте.