BUSROW - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

A bus has N rows of M seats each. Seats are numbered 1, 2, \ldots in row-major order.
You have seat number X
You can board the bus from either the front or the back. Find the minimum number of rows you need to walk through to reach your seat.

EXPLANATION:

Our seat number is X.
Let R denote the row number containing seat X.

R can be found in a couple of different ways:

  1. Iterate through all choices for the row number, and check if X falls in the range of seats corresponding to the current row.
    To perform this check, use the fact that row i contains all seats with numbers from (i-1)M + 1 to iM.
  2. Alternately, using a bit of math, it can be seen that R = \left\lfloor \frac{X-1}{M} \right\rfloor + 1.

After finding R, we need to compute the minimum number of rows we need to walk past.

If we enter the bus from the front, we walk through rows 1, 2, \ldots, R which is a total of R rows.

If we enter the bus from the back, we walk through rows N, N-1, \ldots, R which is a total of (N+1-R) rows.

The answer is hence \min(R, N+1-R).

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, m, x = map(int, input().split())
    
    r = (x - 1) // m + 1
    print(min(r, n+1-r))