D. Бонусы и экономия (25 баллов) Ограничение времени 1 секунда Ограничение памяти 64Mb…
- User
D. Бонусы и экономия (25 баллов) Ограничение времени 1 секунда Ограничение памяти 64Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt
Технология производства некоторой металлической детали предполагает вытачивание её из металлической заготовки. При этом образуются стружки, которые не стоит выкидывать. Ведь из 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 деталь.
- Assistant
To solve this problem, we need to determine the minimum number of blanks to purchase so that, after considering the promotional offers and the recycling of chips (stuzhek), we can produce the required number of finished details.
Problem Breakdown
-
Initial Purchase and Promotion:
- For every
bblanks bought, you receive 1 additional blank for free. - If you buy
xblanks, the total number of blanks you get initially isx + floor(x / b).
- For every
-
Recycling Chips (Stuzhek):
- Each blank processed produces one finished detail and one set of chips.
- For every
asets of chips, you can create one additional blank. - This process can be repeated until you no longer have enough chips to create additional blanks.
-
Objective:
- Find the smallest
xsuch that the total number of finished details is at leastc.
- Find the smallest
Approach
We can use binary search to efficiently find the minimum
x. Here's how:-
Define the Function
f(x):
This function calculates the total number of finished details produced when you purchasexblanks.def f(x, a, b): total_blanks = x + x // b # Initial blanks including free ones finished = total_blanks # Initial finished details stuzhek = total_blanks # Initial chips while stuzhek >= a: new_blanks = stuzhek // a finished += new_blanks stuzhek = stuzhek % a + new_blanks return finished -
Binary Search Implementation:
- Initialize
lowto0andhightoc(since buying allcblanks directly is one possible solution). - Iteratively narrow down the search space by comparing
f(mid, a, b)withc. - The smallest
xfor whichf(x, a, b) >= cis our answer.
- Initialize
-
Edge Cases:
- Ensure that when
b = 1, the logic still holds since every blank bought gives an additional blank. - Handle very large inputs efficiently by using integer division and avoiding floating-point operations.
- Ensure that when
Implementation
Here's the Python implementation based on the above approach:
def min_blanks(a, b, c): def f(x): total_blanks = x + x // b finished = total_blanks stuzhek = total_blanks while stuzhek >= a: new_blanks = stuzhek // a finished += new_blanks stuzhek = stuzhek % a + new_blanks return finished low = 0 high = c answer = c # Initialize with the maximum possible value while low <= high: mid = (low + high) // 2 produced = f(mid) if produced >= c: answer = mid high = mid - 1 else: low = mid + 1 return answer # Example usage: if __name__ == "__main__": import sys a, b, c = map(int, sys.stdin.read().split()) print(min_blanks(a, b, c))Explanation of the Example
Input:
4 5 41Output:
26Explanation:
- Initial Purchase: Buy 26 blanks and receive
floor(26 / 5) = 5free blanks, totaling 31 blanks. - First Recycling: From 31 chips, create
floor(31 / 4) = 7additional blanks. - Second Recycling: Now with 10 chips (from 7 new blanks and 3 remaining), create
floor(10 / 4) = 2additional blanks. - Third Recycling: With 4 chips, create 1 more blank.
- Total Finished Details:
31 + 7 + 2 + 1 = 41, meeting the requirement.
This confirms that purchasing 26 blanks is sufficient to produce the required 41 finished details.
-