URI PROBLEMA 1056 - Fatores e Múltiplos SOLUÇÃO EM C++

URI Online Judge | 1056

Fatores e Múltiplos

Por Sohel Hafiz  Bangladesh*

Timelimit: 1

Serão fornecidos a você, dois conjuntos de valores de entrada. Vamos chamá-los de conjuntos A e B. O conjunto A contém n elementos e o conjunto B contém m elementos. Você deverá remover k1 elementos do conjunto A e k2 elementos do conjunto B de forma que nenhum dos valores inteiros que restarem no conjunto B seja múltiplo de algum inteiro do conjunto A. k1 deverá estar no intervalo [0,n] e k2 no intervalo [0,m].

Você deverá encontrar o valor de (k1+k2) tal que (k1+k2) seja tão baixo quanto possível.

P é um múltiplo de Q se houver algum inteiro K tal que P = K * Q.

Suponha que o conjunto A seja {2,3,4,5} e o conjunto B seja {6,7,8,9}. Se forem removidos 2 e 3 do conjunto A e 8 do conjunto B, nós tempos os conjuntos {4,5} e {6,7,9}. Aqui nenhum dos inteiros 6, 7 ou 9 é um múltiplo de 4 ou 5.

Portanto, para este caso a resposta é 3, que é a quantia de elementos eliminados (2 elementos do conjunto A e 1 elemento do conjunto B).

Entrada

O primeiro valor da entrada é um inteiro T ( T < 50 ) que determina o número de casos de teste. Cada caso de teste consiste de duas linhas. A primeira linha inicia com n seguida pelos n inteiros. A segunda linha inicia com mseguido pelos m inteiros. Ambos, n e m estarão no intervalo [1,100]. Todos os elementos destes dois conjuntos devem caber em um inteiro com sinal de 32 bits.

Saída

Para cada caso, imprima o número do caso de teste, seguido pela resposta, conforme exemplo abaixo.

#include <cstdio>

#include <vector>

#define MAXN 210

using namespace std;

int vetor[MAXN],n,m;

vector<int> match, vis, grafo[MAXN];

int Aug(int l){

if (vis[l]) return 0;

vis[l] = 1;

for(int i=0;i<(int)grafo[l].size();i++){

int r = grafo[l][i];

if (match[r] == -1 || Aug(match[r])){

match[r] = l;

return 1;

}

}

return 0;

}

int main(){

int casos;

scanf("%d",&casos);

for(int caso = 1; caso <= casos;caso++){

for(int i=0;i<MAXN;i++) grafo[i].clear();

match.clear();

vis.clear();

scanf("%d",&n);

for(int i= 1; i <= n; i++) scanf("%d",&vetor[i]);

scanf("%d",&m);

for(int i=n+1;i<=n+m;i++) scanf("%d",&vetor[i]);

for(int i=1;i<=n;i++){

for(int j = n+1;j<=n+m;j++){

if (vetor[i] == vetor[j] || (vetor[i] != 0  && (vetor[j] % vetor[i]) == 0)) grafo[i].push_back(j);

}

}

int resposta = 0;

match.assign(n+m+10,-1);

for(int i=1;i<=n;i++){

vis.assign(n+10,0);

resposta += Aug(i);

}

printf("Case %d: %d\n",caso,resposta);

}

return 0;

}