Доміно#461

Доміно (Розбір)

Кожне доміно накриває рівно дві клітинки, а всього клітинок . Тому доміно не може бути більше ніж .

Ця межа завжди досяжна. Розглянемо поле як шахову дошку і будемо викладати доміно горизонтально, рядок за рядком: у рядку довжини поміщається доміно. Якщо парне, повністю накриваємо все поле. Якщо непарне, у кожному рядку залишається один вільний стовпець — і тоді ці залишки можна попарно накрити вертикальними доміно.

Простіше кажучи, незакритою може лишитись щонайбільше одна клітинка, і саме тоді, коли непарне. Отже, відповідь:

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

Добуток сягає 10^6, тому жодних проблем з типами даних немає.