uva 11159 - Factors and Multiples

Next Generation Contest 3

Factors and Multiples

You will be given two sets of integers. Let�s call them set A and set B. Set A contains n elements and set B contains melements. You have to remove k₁ elements from set A and k₂ elements from set B so that of the remaining values no integer in set B is a multiple of any integer in set A. k₁ should be in the range [0,n] and k₂ in the range [0,m].

You have to find the value of (k₁+k₂) such that (k₁+k₂) is as low as possible.

P is a multiple of Q if there is some integer K such that P = K * Q.

Suppose set A is {2,3,4,5} and set B is {6,7,8,9}. By removing 2 and 3 from A and 8 from B, we get the sets{4,5} and {6,7,9}. Here none of the integers 6, 7 or 9 is a multiple of 4 or 5.

So for this case the answer is 3 (2 from set A and 1 from set B).

Input

The first line of input is an integer T(T<50 span="span"> that determine the number of test cases. Each case consists of two lines. The first line starts with n followed by n integers. The second line starts with m followed by m integers. Both n and m will be in the range [1,100]. All the elements of the two sets will fit in 32 bit signed integer.

Output

For each case, output the case number followed by the answer.

Sample Input	Output for Sample Input
2 4 2 3 4 5 4 6 7 8 9 3 100 200 300 1 150	Case 1: 3 Case 2: 0

Problem Setter: Sohel Hafiz
Special Thanks: Jane Alam Jan

bipartite graph - minimum vertex cover = maximum cardinality in bipartite matching
note: integers contain zero.

#include<stdio.h>
#include<cstring>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
#define MAXN 200
#define MAXM 20000

int N,M,e;
int v[MAXM],next[MAXM],head[MAXN],num[MAXN];
int xM[MAXN],yM[MAXN],cases=1;
bool trav[MAXN];
void addedge(int a,int b){
    v[e]=b,next[e]=head[a],head[a]=e,e++;
    v[e]=a,next[e]=head[b],head[b]=e,e++;
}
bool search(int b){
    for(int a=head[b];a>=0;a=next[a]){
        if(!trav[v[a]]){
            trav[v[a]]=1;
            if(yM[v[a]]<0||search(yM[v[a]])){
                xM[b]=v[a],yM[v[a]]=b;
                return 1;
            }
        }
    }
    return 0;
}
void ans(){
    int res=0;
    memset(xM,-1,sizeof(xM));
    memset(yM,-1,sizeof(yM));
    rep(i,N){
        if(xM[i]<0){
            memset(trav,0,sizeof(trav));
            if(search(i)){
                if(DBG)printf("search: %d %d\n",num[i],num[xM[i]]);
                res++;
            }
        }
    }
    printf("Case %d: %d\n",cases++,res);
}
void build(){
    rep(j,M)rep(i,N)
        if(num[j+N]==0)addedge(j+N,i);
        else if(num[i]>0&&num[j+N]%num[i]==0)addedge(j+N,i);
}
int main(){
   int n;
   scanf("%d",&n);
   rep(i,n){
        e=0,memset(head,-1,sizeof(head));
        scanf("%d",&N);
        rep(i,N)scanf("%d",&num[i]);
        scanf("%d",&M);
        rep(i,M)scanf("%d",&num[i+N]);
        build();
        ans();
    }
   return 0;
}