2014
03-23

There are two kinds of tasks, namely A and B. There are N workers and the i-th worker would like to finish one task A in ai minutes, one task B in bi minutes. Now you have X task A and Y task B, you want to assign each worker some tasks and finish all the tasks as soon as possible. You should note that the workers are working simultaneously.

In the first line there is an integer T(T<=50), indicates the number of test cases.

In each case, the first line contains three integers N(1<=N<=50), X,Y(1<=X,Y<=200). Then there are N lines, each line contain two integers ai, bi (1<=ai, bi <=1000).

In the first line there is an integer T(T<=50), indicates the number of test cases.

In each case, the first line contains three integers N(1<=N<=50), X,Y(1<=X,Y<=200). Then there are N lines, each line contain two integers ai, bi (1<=ai, bi <=1000).

3
2 2 2
1 10
10 1
2 2 2
1 1
10 10

3 3 3
2 7
5 5
7 2

Case 1: 2
Case 2: 4
Case 3: 6

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 205;
int dp[N],a[N],b[N];
bool doit(int t,const int x,const int y,const int n)
{
memset(dp,-1,sizeof(dp));
dp[0] = 0;
for(int ni = 1; ni <= n; ++ni)
{
if(dp[x] >= y) return true;
int len = min(x, t/a[ni]);
for(int i = x; i >= 0; --i)
{
for(int j = 0; j <= min(len, i); ++j)
{
if(dp[i-j] < 0) continue;
dp[i] = max(dp[i],dp[i-j] + (t - j*a[ni])/b[ni]);
}
}
}
return dp[x] >= y;
}
int main()
{
int cas;
int n,x,y;
scanf("%d",&cas);
for(int cc = 1;cc <= cas;++cc){
scanf("%d %d %d",&n,&x,&y);
for(int i = 1; i <= n; ++i){
scanf("%d %d",&a[i],&b[i]);
}
int ll = 1, rr = x*a[1] + y*b[1],mid = (ll + rr)/2;
int ans;
while(ll <= rr){
if(doit(mid,x,y,n)){
ans = mid;
rr = mid - 1;
}
else
ll = mid + 1;
mid = (ll + rr)/2;
}
printf("Case %d: %d\n",cc,ans);
}
return 0;
}