Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

D. Бонусы и экономия (25 баллов) Ограничение времени 1 секунда Ограничение памяти 64Mb…

  1. 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 деталь.

  2. 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

    1. Initial Purchase and Promotion:

      • For every b blanks bought, you receive 1 additional blank for free.
      • If you buy x blanks, the total number of blanks you get initially is x + floor(x / b).
    2. Recycling Chips (Stuzhek):

      • Each blank processed produces one finished detail and one set of chips.
      • For every a sets of chips, you can create one additional blank.
      • This process can be repeated until you no longer have enough chips to create additional blanks.
    3. Objective:

      • Find the smallest x such that the total number of finished details is at least c.

    Approach

    We can use binary search to efficiently find the minimum x. Here's how:

    1. Define the Function f(x):
      This function calculates the total number of finished details produced when you purchase x blanks.

      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
      
    2. Binary Search Implementation:

      • Initialize low to 0 and high to c (since buying all c blanks directly is one possible solution).
      • Iteratively narrow down the search space by comparing f(mid, a, b) with c.
      • The smallest x for which f(x, a, b) >= c is our answer.
    3. 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.

    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 41
    

    Output:

    26
    

    Explanation:

    • Initial Purchase: Buy 26 blanks and receive floor(26 / 5) = 5 free blanks, totaling 31 blanks.
    • First Recycling: From 31 chips, create floor(31 / 4) = 7 additional blanks.
    • Second Recycling: Now with 10 chips (from 7 new blanks and 3 remaining), create floor(10 / 4) = 2 additional 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.