COFN19M1 - Editorial

editorial
1

PROBLEM LINK:

Practice

Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name

DIFFICULTY:

EASY

PROBLEM:

Given N empty bottles, you can exchange K empty bottles at a time for a single bottle filled with water. You can perform this exchange any number of times, and must continue till you do not have enough bottles for an exchange.
In addition, bottles filled with water can be drunk and reused as an empty bottle.

QUICK EXPLANATION:

We observe that out of the k empty bottles, [n/k] will be filled and n%k remain empty. After the [n/k] bottles are depleted, they become empty as well. Iterate this procedure till empty bottles are less than k.

EXPLANATION:

Let N=22 and K=3
To compute the number of empty bottles, we use the modulo operation. In addition, add in the bottles which were filled with water as they become empty upon usage.

#Python3
empty = n%k + n//k    #Integer division

This process must be repeated until no more exchanges are possible. This means that we do not have enough empty bottles to exchange for filled ones. The iteration ends when

empty < k

View the complete solution below.

SOLUTIONS:

Setter's Solution 
t = int(input())
for _ in range(t):
    n, k = map(int, input().split())

    filled = n//k
    empty = n//k + n%k

    while empty >= k:
    
        filled += empty//k
        empty = empty//k + empty%k
    
    print(filled)