Room#175

Room (Editorial)

Плитки не можна ні різати, ні класти під кутом, тому вони утворюють правильну сітку.

Розглянемо розміри окремо. Уздовж сторони довжини поміститься рівно плиток: залишок менший за , тому туди вже не влізе жодна ціла плитка. Так само вздовж сторони поміститься плиток.

Оскільки укладання по горизонталі й вертикалі незалежні, загальна кількість дорівнює добутку:

\left\lfloor \frac{n}{k} \right\rfloor \cdot \left\lfloor \frac{m}{k} \right\rfloor.

Перевіримо на прикладі з малюнка: n = 5, m = 3, k = 2 дають \lfloor 5/2 \rfloor \cdot \lfloor 3/2 \rfloor = 2 \cdot 1 = 2.

Зверніть увагу на випадок k > n або k > m — тоді відповідний множник дорівнює нулю, і відповідь теж нуль. Цілочисельне ділення обробляє це саме, окремої перевірки не потрібно.