Ограничение по времени: 0.5 секунды Слон Семён включил в онлайн‑кинотеатре новый фильм «Матрица». После каждых a минут показа фильма вставляется реклама длиной b минут. Но если в…
Ограничение по времени: 0.5 секунды Слон Семён включил в онлайн‑кинотеатре новый фильм «Матрица». После каждых a минут показа фильма вставляется реклама длиной b минут. Но если в момент планируемого начала рекламного блока фильм завершается, то рекламу не показывают. Фильм без рекламы длится n минут. Сколько времени займёт показ всего фильма вместе с рекламой? Формат входных данных Первая строка входных данных содержит одно целое число a (1⩽a⩽109) — длительность блока фильма между рекламами. Вторая строка содержит одно целое число b (1⩽b⩽109) — длительность одного рекламного блока. Третья строка содержит одно целое число n (1⩽n⩽109) — длительность оригинала фильма без рекламы. Формат выходных данных Выведите одно целое число — длительность фильма с рекламой. Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32 ‑битной целочисленной переменной, поэтому необходимо использовать 64 ‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Система оценки Решения, правильно работающие при a , b , n⩽105 , будут оцениваться в 50 баллов. Ввод Вывод 20 5 90 110 30 4 120 132
Краткое пояснение задачи
- Реклама ставится после каждых a минут фильма.
- Но если момент начала рекламы совпадает с концом фильма, рекламу не показывают.
- Значит количество рекламных пауз равно количеству целых кратных a, строго меньших чем n: a, 2a, 3a, ..., floor((n-1)/a)·a.
- Каждая реклама длится b минут, поэтому общее время равно: n + floor((n-1)/a) · b.
Формула
- количество реклам: ads = floor((n - 1) / a)
- итоговое время: result = n + ads * b
Пошаговый разбор
- Считаем ads = (n - 1) // a (целочисленное деление).
- Прибавляем рекламу к исходной длительности фильма: n + ads * b.
- Все вычисления выполняются в 64-битных целых, чтобы избежать переполнения (максимум может быть около 10^18).
Примеры (по заданным тестам)
- Пример 1: a=20, b=5, n=90
- ads = floor((90-1)/20) = floor(89/20) = 4
- итог = 90 + 4·5 = 110
- Пример 2: a=30, b=4, n=120
- ads = floor((120-1)/30) = floor(119/30) = 3
- итог = 120 + 3·4 = 132
Сложность
- Время: O(1)
- Память: O(1)
Пример кода (C++, можно адаптировать под другие языки)
// Используйте 64-битный тип #include <bits/stdc++.h> using namespace std;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
long long a, b, n;
if (!(cin >> a)) return 0;
if (!(cin >> b)) return 0;
if (!(cin >> n)) return 0;
long long ads = (n - 1) / a; // количество реклам
long long result = n + ads * b;
cout << result << "\n";
return 0;
}
Советы на экзамене
- Всегда проверяйте случай, когда a > n (рекламы нет): ads = 0.
- Учитывайте возможное переполнение при умножении; используйте 64-битные типы.
- Это задача на ключевую формулу: total = n + floor((n-1)/a) * b.
