PASSCHAIN - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

N football players practice passing.
The ball is initially with player 1, then is repeatedly passed from the current player X to player X+K as long as possible.
Who ends up with the ball?

EXPLANATION:

Run a simple while loop to compute the answer: start with X = 1, and as long as X+K \le N, increase X by K.
Print the final value of X.

It’s also possible to solve the problem mathematically without the loop, using the fact that the players who will receive the ball are 1, K+1, 2K+1, \ldots
So we want to find the largest integer of the form yK+1 that doesn’t exceed N.
This can be done using division: yK+1 \le N tells us that y \le \frac{N-1}{K} so the choice of y is just the largest integer not exceeding \frac{N-1}{K}.

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())
    x = 1
    while x+k <= n:
        x += k
    print(x)