Условие:
G. Супермаркет
ограничение по времени на тест1 s.
ограничение по памяти на тест512 MB
В пекарне супермаркета ежедневно выпекают хлеб и кондитерские изделия, которые остаются свежими в течение ограниченного времени. Чтобы не допустить продажи несвежей продукции, пекарь проверяет товары каждые k
дней в 23:59.
Если с момента начала последней проверки (или с момента открытия пекарни) прошло не менее d
суток, то пекарь проводит ревизию: следующие t
суток (начиная с 00:00) он тщательно проверяет всю выпечку и заменяет несвежие продукты. После завершения ревизии пекарь возвращается к обычной работе, а следующая проверка запланирована через k
дней (снова в 23:59).
Необходимо определить, сколько раз пекарь проверит выпечку за первые n
дней работы пекарни. Пекарня открывается в 00:00 первого дня, а первая проверка происходит в 23:59 k
-го дня.
Входные данные
В первой строке задано целое число n
(1≤n≤1018
) — количество дней.
Во второй строке указано целое число d
(1≤d≤1018
) — минимальный интервал между проверками.
В третьей строке задано целое число k
(1≤k≤d
) — периодичность проверок.
В четвертой строке указано целое число t
(0≤t<d
) — длительность ревизии.
Выходные данные
Выведите одно число — ответ на задачу.
Примеры
Входные данныеСкопировать
10
5
2
3
Выходные данныеСкопировать
3
Входные данныеСкопировать
10
3
1
2
Выходные данныеСкопировать
5
Примечание
Первый пример:
Мастер приезжает в конце 2-х, 4-х и 6-х суток
На 6-е сутки начинается обслуживание длительностью b=3
дня (7-е, 8-е и 9-е сутки)
Следующий визит должен быть в конце 12-х суток (но это уже за пределами рассматриваемого периода n=10
)
Итого: 3 приезда (на 2-й, 4-й и 6-й дни)
Второй пример:
Мастер приезжает каждый день (a=1
)
На 4-е сутки начинается обслуживание длительностью b=2
дня (5-е и 6-е сутки)
Затем на 7-е сутки снова начинается обслуживание (7-е и 8-е сутки)
Мастер приезжает и остается в конце: 1-х, 2-х, 3-х, 6-х, 9-х суток
Итого: 5 приездов за первые 10 дней
на с++
Решение:
Для решения задачи, давайте разберем алгоритм по шагам.
Шаг 1: Понимание условий задачи
- Пекарь проверяет выпечку каждыеk дней в 23:59.- Проверка может быть проведена только если с момента последней проверки прошло не менее
d суток.- Если проверка проводится, то она длится
t суток, в течение которых пекарь не может проводить новые проверки.Шаг 2: Определение логики проверки
1. Пекарь начинает проверку в концеk-го дня.2. После каждой проверки, если прошло не менее
d суток, пекарь снова проверяет.3. Если проверка была проведена, то в течение следующих
t суток пекарь не может проводить новые проверки.Шаг 3: Алгоритм
1. Инициализируем переменные:-
current_day = 0 (текущий день)-
checks = 0 (количество проверок)2. Запускаем цикл, который будет выполняться, пока
current_day меньше n:- Увеличиваем
current_day на k.- Проверяем, если
current_day меньше или равен n и если прошло не менее d суток с последней проверки:- Увеличиваем
checks на 1.- Увеличиваем
current_day на t (пекарь проводит ревизию).3. Выводим количество проверок.
Шаг 4: Реализация на C++
Теперь давайте напишем код на C++:- Мы используем для работы с большими числами, так как , , , и могут быть до . - Цикл продолжается до тех пор, пока меньше . - Мы проверяем, если текущий день меньше или равен , и если прошло достаточно времени с последней проверки, чтобы провести новую. - После проверки мы увеличиваем на , чтобы учесть время, в течение которого пекарь проводит ревизию. Теперь вы можете протестировать код с приведенными примерами, чтобы убедиться, что он работает правильно.