PGNATK - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Putting up a pigeon net needs N minutes, but you will be interrupted every K-th minute.
Find the total amount of time needed to put up the net, including delays.

EXPLANATION:

It suffices to simply try and simulate the process directly.

For each minute i = 1, 2, 3, \ldots in order,

  • If i is a multiple of K, do nothing.
  • Otherwise, increment the number of minutes worked by 1.

As soon as the number of minutes worked reaches N, print the current minute.

Since N \le 100 and 2 \le K \le 100, we will need at most 200 minutes to achieve our goal; since we’ll surely get at least one working minute among any two consecutive ones.
So, the simulation will find the answer quickly.

It’s also possible to solve the problem mathematically, if you wish to do so.
This can be done by breaking up the minutes into chunks of K and noting that we get K-1 working minutes from each chunk; except maybe the last chunk which needs less.

So the number of full chunks can be obtained by dividing N by K-1 (rounded down), and the remainder will be the extra days needed from the last chunk.

TIME COMPLEXITY:

\mathcal{O}(1) or \mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    
    done = 0
    for i in range(1, 300):
        if i%k == 0: continue
        done += 1
        if done == n:
            print(i)
            break