1. Идея

Нужно для каждой записи понять, срабатывает ли она в заданную дату.

Типы напоминаний проверяются так:

• ONCE — только если дата ровно совпадает;
• DAILY — если запрошенная дата не раньше даты начала;
• WEEKLY — если запрошенная дата не раньше даты начала и разница в днях кратна 7.

Главная техническая часть задачи — удобно сравнивать даты и находить разницу между ними в днях. Для этого каждую дату переведём в число: количество дней, прошедших с 1970-01-01 до этой даты.

Тогда:

• совпадение дат — это равенство чисел;
• дата не раньше другой — это обычное сравнение чисел;
• разница в днях — это вычитание чисел.

2. Наблюдения

Наблюдение 1. С датами удобнее работать как с числами

Строки вида YYYY-MM-DD неудобно сравнивать для еженедельных проверок, потому что нужна именно разница в днях.

Поэтому для каждой даты считаем её номер дня:

• складываем количество дней во всех полных годах до нужного года;
• добавляем количество дней во всех полных месяцах текущего года;
• добавляем day - 1.

Например, для 1970-01-01 номер будет 0.

Наблюдение 2. Нужно учитывать високосные годы

Год високосный, если:

• делится на 400, или
• делится на 4, но не делится на 100.

Из-за этого в феврале бывает 28 или 29 дней.

Наблюдение 3. Название может содержать пробелы

Значит, нельзя просто разбить строку по пробелам на все части и ожидать фиксированное число слов в названии.

Нужно выделить:

• тип напоминания;
• дату;
• всё остальное как title.

В C++ это удобно сделать через поиск первых двух пробелов. В Python — через split(' ', 2).

Наблюдение 4. Порядок вывода должен совпадать с входным

Значит, достаточно пройти по напоминаниям в исходном порядке и добавлять подходящие названия в ответ.

3. Алгоритм

Шаг 1. Реализуем функции для работы с календарём

Нужны три функции:

1. isLeap(year) / is_leap(year) — проверка, високосный ли год.
2. daysInMonth(year, month) / days_in_month(year, month) — количество дней в месяце.
3. dayNumber(date) / day_number(date) — перевод даты YYYY-MM-DD в номер дня.

Шаг 2. Считываем все напоминания

Сохраняем строки напоминаний как есть, потому что потом их нужно разобрать, не потеряв пробелы в названии.

Шаг 3. Считываем дату запроса и переводим её в номер дня

Пусть это будет queryDay.

Шаг 4. Обрабатываем каждое напоминание

Для каждой строки:

• выделяем type, date, title;
• считаем startDay = dayNumber(date);
• проверяем условие в зависимости от типа:

Если тип ONCE

Напоминание подходит, если queryDay == startDay.

Если тип DAILY

Напоминание подходит, если queryDay >= startDay.

Если тип WEEKLY

Напоминание подходит, если:

• queryDay >= startDay,
• (queryDay - startDay) % 7 == 0.

Если условие выполнено, добавляем title в ответ.

Шаг 5. Выводим результат

• сначала количество подходящих напоминаний;
• затем их названия по одному в строке.

4. Почему это работает

Докажем, что алгоритм правильно определяет все срабатывающие напоминания.

Корректность перевода даты в номер дня

Функция dayNumber считает:

• все дни в годах от 1970 до year - 1,
• все дни в месяцах от января до month - 1,
• дни внутри текущего месяца, кроме первого, то есть day - 1.

Это и есть точное количество дней от 1970-01-01 до данной даты.

Значит:

• если две даты одинаковые, их номера дней равны;
• если одна дата позже другой, её номер дня больше;
• разность номеров дней равна числу дней между датами.

Корректность проверки ONCE

По условию ONCE срабатывает только в одну конкретную дату.

Алгоритм проверяет queryDay == startDay, то есть совпадение дат. Это в точности соответствует условию.

Корректность проверки DAILY

По условию DAILY срабатывает каждый день, начиная с даты начала включительно.

Алгоритм проверяет queryDay >= startDay. Это означает, что запрошенная дата либо совпадает с датой начала, либо позже неё. Значит, проверка полностью верна.

Корректность проверки WEEKLY

По условию WEEKLY срабатывает:

• в дату начала;
• затем каждые 7 дней.

Алгоритм требует:

• queryDay >= startDay, то есть дата не раньше начала;
• (queryDay - startDay) % 7 == 0, то есть разница в днях равна 0, 7, 14, ...

Это ровно и означает, что напоминание срабатывает в дату начала и через каждую неделю после неё.

Корректность порядка вывода

Мы обрабатываем напоминания в том же порядке, в котором они даны во входных данных, и сразу добавляем подходящие в ответ. Поэтому итоговый список тоже будет в исходном порядке.

Следовательно, алгоритм полностью корректен.

5. Сложность

Пусть n — число напоминаний.

Для каждого напоминания мы:

• разбираем строку;
• один раз переводим его дату в номер дня;
• выполняем несколько простых проверок.

Перевод одной даты в номер дня перебирает годы от 1970 до нужного года и месяцы от 1 до нужного месяца. По ограничениям диапазон лет маленький, так что это очень быстро.

Итоговая сложность:

• по времени: O(n);
• по памяти: O(n) для хранения строк напоминаний и ответа.

6. Код на C++17

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isLeap(int y) {
    if (y % 400 == 0) return true;
    if (y % 100 == 0) return false;
    return y % 4 == 0;
}

int daysInMonth(int y, int m) {
    static int mdays[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (m == 2 && isLeap(y)) return 29;
    return mdays[m - 1];
}

long long dayNumber(const string& s) {
    int y = stoi(s.substr(0, 4));
    int m = stoi(s.substr(5, 2));
    int d = stoi(s.substr(8, 2));

    long long days = 0;

    for (int year = 1970; year < y; year++) {
        days += isLeap(year) ? 366 : 365;
    }
    for (int month = 1; month < m; month++) {
        days += daysInMonth(y, month);
    }
    days += d - 1;

    return days;
}

int main() {
    int n;
    cin >> n;
    string line;
    getline(cin, line);

    vector<string> answer;
    vector<string> reminders(n);

    for (int i = 0; i < n; i++) {
        getline(cin, reminders[i]);
    }

    string queryDate;
    getline(cin, queryDate);
    long long queryDay = dayNumber(queryDate);

    for (int i = 0; i < n; i++) {
        const string& s = reminders[i];

        size_t p1 = s.find(' ');
        size_t p2 = s.find(' ', p1 + 1);

        string type = s.substr(0, p1);
        string date = s.substr(p1 + 1, p2 - p1 - 1);
        string title = s.substr(p2 + 1);

        long long startDay = dayNumber(date);
        bool ok = false;

        if (type == "ONCE") {
            ok = (queryDay == startDay);
        } else if (type == "DAILY") {
            ok = (queryDay >= startDay);
        } else if (type == "WEEKLY") {
            ok = (queryDay >= startDay && (queryDay - startDay) % 7 == 0);
        }

        if (ok) {
            answer.push_back(title);
        }
    }

    cout << answer.size() << "\n";
    for (const string& title : answer) {
        cout << title << "\n";
    }

    return 0;
}

7. Код на Python 3

def is_leap(y):
    if y % 400 == 0:
        return True
    if y % 100 == 0:
        return False
    return y % 4 == 0

def days_in_month(y, m):
    mdays = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    if m == 2 and is_leap(y):
        return 29
    return mdays[m - 1]

def day_number(s):
    y = int(s[0:4])
    m = int(s[5:7])
    d = int(s[8:10])

    days = 0
    for year in range(1970, y):
        if is_leap(year):
            days += 366
        else:
            days += 365

    for month in range(1, m):
        days += days_in_month(y, month)

    days += d - 1
    return days

n = int(input())
reminders = []

for _ in range(n):
    reminders.append(input())

query_date = input()
query_day = day_number(query_date)

answer = []

for s in reminders:
    parts = s.split(' ', 2)
    reminder_type = parts[0]
    date = parts[1]
    title = parts[2]

    start_day = day_number(date)
    ok = False

    if reminder_type == 'ONCE':
        ok = (query_day == start_day)
    elif reminder_type == 'DAILY':
        ok = (query_day >= start_day)
    elif reminder_type == 'WEEKLY':
        ok = (query_day >= start_day and (query_day - start_day) % 7 == 0)

    if ok:
        answer.append(title)

print(len(answer))
for title in answer:
    print(title)