# CUTPAPER - Editorial

Author: Utkarsh Gupta
Preparer: Jeevan Jyot Singh
Tester: Tejas Pandey
Editorialist: Nishank Suresh

800

None

# PROBLEM:

How many K\times K squares can you cut out of an N\times N grid?

# EXPLANATION:

The answer is simply

\left\lfloor \frac{N}{K} \right\rfloor \times \left\lfloor \frac{N}{K} \right\rfloor

where \left\lfloor \cdot \right\rfloor denotes the floor function. This is N/K in C++/Java and N//K in Python.

Proof

Any given row or column can only hold \left\lfloor \frac{N}{K} \right\rfloor squares, since any more than that would require more than N squares in that row/column.

So, \left\lfloor \frac{N}{K} \right\rfloor \times \left\lfloor \frac{N}{K} \right\rfloor is clearly an upper bound for the answer.

This upper bound is easily seen to be achievable by greedily picking K\times K squares from the top left corner, so it is also the answer.

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
print((n//k) * (n//k))

1 Like