Another Brick in the Wall
Time limit2sMemory limit2048 MB
Find the fewest 1 x 3 bricks needed to build an l by h wall from 1 x 2 and 1 x 3 bricks so that no two seams line up vertically.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Bit manipulation
- Solved
- No attempts yet
Problem
Alice likes building toy walls. She has many bricks and a limited supply of bricks. Both types of bricks are 1 unit high and cannot be rotated.
Alice builds a wall one unit thick, with length and height , using these bricks. A wall is solid if no seam lies directly above another seam.
Find the minimum number of bricks needed to build a solid wall of length and height .
Input
The only line contains two integers and , the length and the height of the wall (; ).
Output
Print the minimum number of bricks needed to build a solid wall.
It is always possible to build a solid wall of length and height .


