Problem I
Rectangle Tiling
Consider a rectangle with integer side lengths. A square tiling of the rectangle is a covering of the entire region using non-overlapping squares whose sides are parallel with those of the rectangle. In a square tiling, no square may overhang (extend beyond the rectangle’s boundary).
You have a collection of squares with side lengths being powers of $2$. Find a square tiling of the rectangle using the fewest squares possible, or, indicate that it cannot be done.
Input
The first line of input contains three integers $W, H$ and $N$ ($1 \leq W,H \leq 2^{50}$ and $1 \leq N \leq 51$). Here, $W$ and $H$ indicate the dimensions of the rectangle. The next line contains $N$ integers $a_0, a_1, \ldots , a_{N-1}$ where $a_i$ ($0 \leq a_i \leq 2^{51}$) is the number of $2^i \times 2^i$ squares you own.
Output
If there is a square tiling of a $W \times H$ rectangle using the squares you own, output the minimum number of squares needed in such a square tiling. Otherwise, output $-1$ if there is no square tiling of the rectangle using the squares you own.
Sample Input 1 | Sample Output 1 |
---|---|
4 2 2 5 1 |
5 |
Sample Input 2 | Sample Output 2 |
---|---|
6 7 3 10 10 10 |
12 |
Sample Input 3 | Sample Output 3 |
---|---|
17 20 5 20 0 4 0 1 |
25 |
Sample Input 4 | Sample Output 4 |
---|---|
4 2 3 3 1 10 |
-1 |