CUTPAPER - Editorial

editorial
,
1

PROBLEM LINK:

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

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

DIFFICULTY:

800

PREREQUISITES:

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