 # Easy problem help?

https://www.codechef.com/CWR22021/problems/CHFNSW
the solution of above problem is (N*M)/2
but i am not getting why ? could you help guys?

see it is an elementary problem u might have solved this in class 9-10.
U have to construct a wall of dimensions NxM and u r provided with bricks of dimension
nxm.
Then no of bricks req=area of wall / area of each brick
= NxM/(nxm)

Here NxM/(2)

1 Like

This problem is similar to the following problem at codeforces:

Wow copying question from CF contest? Nice

Adding to what is said above, number\;of \;bricks =\frac{area\; of\; wall}{area\; of\; each\; brick} would hold if there was a way to fill the entire NxM grid with 2x1 blocks such that no cell is empty.

Can we construct such a solution? If at least one of N or M is even, (Without loss of generality, assume M is even). Then in each of the N rows, we can have M/2 blocks of size 2x1, thus filling the entire grid with total MN/2 blocks

If both N and M are odd, then above doesn’t work, but we can build a different construction of (MN-1)/2 blocks. Put (M-1)/2 blocks in each row of size 2x1. In last column, put (N-1)/2 blocks. As only one cell is left empty in this construction, this is the maximum number of sweets.

2 Likes

thanks got it