Problem

Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants N tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square. The lengths of side of the tiles are 2S1, 2S2, ..., 2SN. He can only buy a lot of tiles sized M*M, and he decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy? Input

The first line of the input gives the number of test cases: T. T lines follow. Each line start with the number N and M, indicating the number of required tiles and the size of the big tiles Enzo can buy. N numbers follow: S1, S2, ... SN, showing the sizes of the required tiles. [cut] Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of the big tiles Enzo need to buy. [cut] Limits

1 ≤ 2Sk ≤ M ≤ 2^31-1.

Small dataset

1 ≤ T ≤ 100. 1 ≤ N ≤ 20. Large dataset

1 ≤ T ≤ 1000. 1 ≤ N ≤ 500. [cut]

Soluton: The core of this solution is : given a rectangle, add the max size tile that fits, and recurse on the remaining 2 rectangles formed. Do this till all tiles are exhausted. The rectangles are taken so as to maximize the length and breadth of each. sides[] stores the available sides. Its pretty easy actually :)

		int[] sides;
int count = 0;

public void rec(int a, int b) {
//Switch sides so that a is the greater one
if (a < b) {
int t = a;
a = b;
b = t;
}
if (a == 0 || b == 0)
return;
//Select the max size tile that fits
int max = (int) (Math.log(b) / Math.log(2));

while (max >= 0 && sides[max] == 0)
max--;//max size tile that is available
if (max == -1)
return;
sides[max]--;//remove it
count++;
int ss = 1 << max;
//recurse on the remaining rectangles
rec(b - ss, ss);
rec(a - ss, b);
}

public int Solve() {
int n = ni();//input
int m = ni();
sides = new int[32];
for (int i = 0; i < n; i++)
sides[ni()]++;
int ans = 0;
for (; count < n; ans++) {
rec(m, m);
}
count = 0;
return ans;

}

• 0

 » 9 years ago, # | ← Rev. 2 →   +2 Whether problems of this contest are available online ?
•  » » 9 years ago, # ^ |   0
•  » » » 9 years ago, # ^ |   0 Thanks.
 » 9 years ago, # |   0 My bad. Should have added the question too. Updated.
 » 8 years ago, # |   0 In the recurse on the remaining rectangles step, there should also be rec(a-ss,b-ss).
•  » » 8 years ago, # ^ |   0 wouldn't that be included in the recursive calls to (a-ss,b) and (a,b-ss)?