D. Бонусы и экономия (25 баллов)
Технология производства некоторой металлической детали предполагает вытачивание её из металлической заготовки. При этом образуются стружки, которые не стоит выкидывать. Ведь из a комплектов стружек (оставшихся после обработки a заготовок) можно бесплатно выплавить еще одну заготовку, которую снова можно использовать для выточки детали и создания ещё одного комплекта стружек.
Заготовки можно купить на оптовом складе, при этом в целях привлечения клиентов, проводится акция "купи b заготовок, тогда еще одну получишь бесплатно".
Требуется изготовить с деталей. Нужно определить минимальное число заготовок, которые нужно купить за деньги, чтобы с учетом бонусных заготовок и экономии на стружках, можно было изготовить требуемое число деталей.
Формат ввода
В одной строке через пробел заданы три целых числа a, b, и c. 2 ≤ a ≤ 1018, 1 ≤ b, c ≤ 1018.
Формат вывода
Вывести одно целое число — минимальное количество заготовок, которые нужно купить, чтобы с учетом всех бонусов и экономии выточить c конечных деталей.
Пример
Ввод Вывод
4 5 41 26
Примечания
В примере из условия нужно закупить 26 заготовок. Тогда за каждые 5 купленных заготовок будет предоставлена одна бесплатная, итого по акции добавиться еще 5 заготовок, то есть получится 31 заготовка. Далее из 31 заготовки выточится 31 деталь, останется 31 комплект стружек. Из каждых четырех комплектов выплавится дополнительная заготовка, получится 7 заготовок и 3 комплекта стружек. Из 7 заготовок выточится 7 деталей и останется 7 комплектов стружек плюс 3 комплекта стружек осталось с первого шага, итого 10 комплектов стружек. Из них выплавится еще 2 заготовки, дающие 2 детали и два комплекта стружек. Собрав эти два комплекта с двумя, оставшимися от 10, получим еще одну заготовку, из которой выточится еще одна деталь. Останется один комплект стружек, который уже никак не получится использовать. Итого будет произведено 31 + 7 + 2 + 1 = 41 деталь.
Как-то так. Погоняй на разных тестах:
a, b, c = map(int, input().split())
print((c - c // a + 1) * b // (b + 1)) Никаких циклов тут, само собой, не нужно.
Краткое пояснение.
Чтобы найти, сколько заготовок нужно получить для изготовления 'c' деталей, берём и элементарно вычитаем из кол-ва деталей количество заготовок, которые можно сэкономить благодаря стружкам:
d = c - [c / a] (квадратные скобки в математике - это целая часть вещественного числа)
Далее составляем уравнение ('e' - это количество заготовок к закупке:
e + [e / b] = d
[e + e / b] = d
[e * (1 + 1/b)] = d
Переносим множитель в правую часть, попутно меняя на округление в большую сторону:
e = ⌈d / (1 + 1/a)⌉ = ⌈d * a / (a + 1)⌉ =
= [(d * a + (a + 1) - 1) / (a + 1)] =
= [(d + 1) * a / (a + 1)] = [(c - [c / a] + 1) * a / (a + 1)] def min_blanks(a, b, c):
purchased = 0
total_blanks = 0
while total_blanks < c:
needed = c - total_blanks
buy = (needed + (b - 1)) // b * b
purchased += buy
total_blanks += buy + (buy // b)
total_blanks += total_blanks // a
return purchased
a, b, c = 4, 5, 41
print(min_blanks(a, b, c))