КМ259(б). Квартеты из клеток

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

Задача

Назовем квартетом четверку клеток на клетчатой бумаге, центры которых лежат в вершинах прямоугольника со сторонами, параллельными линиям сетки. Какое наибольшее число квартетов, не имеющих общих клеток, можно разместить в прямоугольнике [latex]m\times n[/latex] клеток?

Входные данные

[latex]m[/latex],[latex]n[/latex]

Вывод

[latex]x[/latex]-кол-во квартетов.

Тесты

m n x
8 6 12
16 7 24
17 8 29,75
15 11 37

Код

Решение

Если [latex]m[/latex] и [latex]n[/latex] четные, то в прямоугольнике [latex]m\times n[/latex] можно разместить [latex]m/n[latex] квартетов. Если [latex]m[/latex] четное, а [latex]n[/latex] нечетное (и наоборот), то квартетов — [latex]m(n-1)/4[/latex]. И наконец если [latex]m[/latex] и [latex]n[/latex] — нечетные, то формула будет выглядеть так: [latex]m(n-1)-2/4[/latex].