Book of programming problems

Complexity (1-100): 30

A wall consists of M rows with N equal bricks in each. Each succeeding row is shifted by 1/2 of a brick's length, as it is shown on fig. 1. Even rows from the top are shifted to the left, and odd rows are shifted to the right. A wall is stable, if each brick lays over at least one another brick in the next row (bricks in the bottom row lay on ground).

Obviously, one can remove a few bricks from a wall so that the wall would remain stable. Fig. 2 shows a possible configuration after removing bricks from the wall on fig. 1.

Write a program which, given wall dimensions M and N (0<M,N≤1000), finds a stable wall configuration, ensuing from the solid wall M×N by removing maximal number of bricks such that the top row can remain unchanged. The program should print the number of remaining bricks and the resulting wall configuration.

Note: the program is allowed to run no longer than 3 seconds.

Self-tests. These are some results:

M×N	Number of bricks
4×5	13
2×2	3
6×4	11
17×14	58
17×5	26