Забастовки
Отмечаем рабочие дни забастовок, считая совпадения только один раз.
Как к ней подойти
Увидите, как множества помогают сравнивать группы без повторяющихся элементов.
Множество хранит каждый элемент один раз. Пересечение a & b оставляет общие элементы, разность a - b - только элементы a, а объединение a | b собирает обе группы. Если важен порядок вывода, отсортируйте результат отдельно.
Остатки 6 и 0 соответствуют субботе и воскресенью. Множество автоматически удаляет совпадения разных партий.
Проверьте перед запуском
- Отсчёт дней начинается с понедельника под номером 1.
- Совпадающие забастовки не суммируются.
- Нельзя учитывать дни раньше первого выступления партии.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Множество дней
Остатки 6 и 0 соответствуют субботе и воскресенью. Множество автоматически удаляет совпадения разных партий.
n, k = map(int, input().split())
days = set()
for _ in range(k):
a, b = map(int, input().split())
for day in range(a, n + 1, b):
if day % 7 not in (6, 0):
days.add(day)
print(len(days))
Время: O(k + Σ(1 + (n−aᵢ)//bᵢ)) для партий с aᵢ≤n; в среднем. Память: O(n) в худшем случае.
Другой способ: Проверка календаря
Для каждого рабочего дня ищем хотя бы одну партию, у которой он входит в арифметическую прогрессию.
n, k = map(int, input().split())
parties = [tuple(map(int, input().split())) for _ in range(k)]
count = 0
for day in range(1, n + 1):
if day % 7 not in (6, 0):
if any(day >= a and (day - a) % b == 0 for a, b in parties):
count += 1
print(count)
Время: O(nk). Память: O(k).