Intermediate levels like SIMPLE-EASY, EASY-MEDIUM, MEDIUM-HARD are also possible.
Yogesh has a whiteboard of dimension NxMNxM. Also, he has an unlimited number of blackboards of dimension 2x12x1. He is allowed to rotate the blackboard. He is asked to place as many as blackboards on toptop of the whiteboard to meet the following conditions:
- Each blackboard can completely cover the 2x1 part of the whiteboard.
- No two blackboards overlap.
- Each blackboard can only be placed completely inside the whiteboard.
Print the maximum number of blackboards that can be completely placed on top of the whiteboard.
Answer is floor(NM0.5). Since there is N*M cells on the whiteboard and each blackboard covers exactly two of them we cannot place more for sure. Now let’s show how to place exactly this number of blackboards. If N is even, then place M rows of N/2 blackboard and cover the whole whiteboard. Else N is odd, so cover N-1 row of the whiteboard as shown above and put floor(M/2) blackboard to the last row. In the worst case (N and M are odd) one cell remains uncovered.