[URI ONLINE JUDGE] – 1086 – The Club Ballroom

The Tingua Social Club is building its new ballroom. The club members wish to have the floor covered with wood planks, as they consider this to be the best for dancing. A lumberyard from the region donated a large quantity of good quality wooden planks to be used in the ballroom. The donated planks have all the same width, but have different lengths.

The ballroom is a rectangle of dimensions N x M meters. The planks must be placed juxtaposed, so that no plank superposes another, and the whole floor must be covered. They must be aligned, lengthwise, to one of the sides of the ballroom, and all planks must be parallel. The club members do not want too many joints in the floor, and therefore if a plank is not long enough to cover the distance between two opposite sides of the ballroom, it can be joined to at most one other plank to complete the distance. Furthermore, the chief-carpenter has a great respect for all woods, and would rather not saw any plank. Therefore, he wants to know whether it is possible to cover the floor with the set of planks donated, observing the restrictions described; in case it is possible, the chief-carpenter wish to know the smallest number of planks he can use.

The figure below depicts two possible ways to cover the floor of a ballroom with dimensions 4 x 5 meters for a set of ten donated planks, with 100 cm width, and lengths 1, 2, 2, 2, 2, 3, 3, 4, 4 and 5 meters.

Input

The input contains several test cases. The first line of a test case contains two integers N and Mindicating the dimensions, in meters, of the ballroom (1 ≤ N,M ≤ 104). The second line contains one integerL representing the planks width, in centimeters (1 ≤ L ≤ 100). The third line contains one integer K, indicating the number of planks donated (1 ≤ K ≤ 105). The fourth line contains K integers Xi, separated by spaces, representing the length, in meters, of one plank (1 ≤ Xi ≤ 104 for 1 ≤ i K). The end of input is indicated by a line containing only two zeros, separated by one space.

Output

For each of the test cases in the input your program must print one single line, containing one integer, the smallest number of planks needed to cover the whole floor, satisfying the restrictions established. If it is not possible to cover the whole floor satisfying the restrictions established, print one line with the word “impossivel” (which means impossible in Portuguese).

Sample Input Sample Output
4 5
100
10
1 2 2 2 2 3 3 4 4 5
5 4
100
7
4 5 4 4 4 4 3
4 5
99
4
4 4 4 4
3 2
100
7
2 4 1 4 2 4 4
0 0
7
5
impossivel
impossivel

 

my solution:

 

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>

using namespace std;

#define sc1(a) scanf("%d", &a)
#define sc2(a,b) scanf("%d %d", &a, &b)
#define INF 0x3f3f3f3f
#define mst(a, b) memset(a, b, sizeof a)
#define fr(i,a,b) for(int i=a; i < b; i++)

typedef set<int> si;

int l, k, w, n, m;
int arr[10005];
int arr_[10005];
si ns;
si::reverse_iterator it;

int check(int k, int sum, bool b) {

it = ns.rbegin();
int d, n, cnt = 0, i = ns.size()-1;

while(k && it != ns.rend()) {
n = *it;
d = sum-n;

if(b) {
if(arr[n] <= 0 || d < 0 || (d==n ? (arr[d]-1) <= 0 : arr[d] <= 0)) {
it++; continue;
}
}
if(!b) {
if(arr_[n] <= 0 || d < 0 || (d==n ? (arr_[d]-1) <= 0 : arr_[d] <= 0)) {
it++; continue;
}
}

if(b) {
arr[d]--, arr[n]--;
}else {
arr_[d]--, arr_[n]--;
}

cnt+= (d ? 2 : 1);
k--;
}

if(k) return INF;
return cnt;
}

int main (int argc, char const* argv[]) {

while(sc2(n,m) && (n || m)) {
mst(arr, 0); mst(arr_, 0);
arr[0] = arr_[0] = INF;
ns.clear();
sc2(l,k);

fr(i,0,k) {
sc1(w);
ns.insert(w);
arr[w]++, arr_[w]++;
}

int r = INF;

if((n*100)%l == 0){
r = min(r, check((n*100)/l, m, 1));
}

if((m*100)%l == 0){
r = min(r, check((m*100)/l, n, 0));
}

if(r >= INF || r < 0) puts("impossivel");
else printf("%d\n", r);
}

return 0;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s