ZOJ Problem Set - 3363
The company Wall Construction Inc (WC Inc) is preparing its new software project. The goal of this project is to automatically plan garden walls. You, the company's leading developer, are asked to quickly write the prototype of the system.
The wall is constructed of several bricks. Bricks are organized in layers, the bottom layer contains m bricks lying next to each other. The total number of layers is n. The bricks in each next layer are shifed by one half of the brick horizontaly compared to the bricks of the previous layer.
The number of bricks in different levels may be different, however the wall must be stable. The wall is considered stable if all of its bricks are stable. The brick is stable if one of the following conditions is satisfied:
The pictures below show possible cases of stable bricks.
Note, that only bricks that affect the stability of the shaded brick are shown. Since all these bricks must also be stable, actually some other bricks must also exist for the whole wall to be stable.
Your first task is, given m and n find the number of stable walls.
The input file contains m and n (1 ≤ m, n ≤ 8).
There are multiple test cases. Process to the end of file.
Output the number of stable walls with m bricks in the first layer and n layers.
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #11