DWITE Online Computer Programming Contest

October 2010

Problem 3

Power tiles

You are given a rectangular floor that is to be tiled with square tiles. The tiles come in a variety of sizes, but they all measure in some power of two: 1, 2, 4, 8, etc. A 5x6 space can be tiled with 30 of the smallest tile, but the minimum number of tiles required is only 9. Refer to the pattern below.

The input file **DATA3.txt** will contain 5 lines, a pair of integers 1 <= N, M <= 10000, separated by a space.

The output file **OUT3.txt** will contain 5 lines, the minimum number of tiles necessary to exactly cover the N by M space.

Sample Input:

10 5 1000 1001 21 13 9999 888 345 1277

Sample Output:

14 1358 42 4065 2046