Olá, estou tentando resolver esse problema das olimpíadas de informática: http://olimpiada.ic.unicamp.br/passadas/pdf/provas/ProvaOBI2002.pdf
e aqui está o código que estou desenvolvendo
#include <stdio.h>
int backtrack( int vet[] , int pos, int soma, int valor, int tam ) {
int num;
if(soma==valor) return 1;
/*if(tab[line][row]!=0)
return backtrack( vet, pos+1, soma, valor, tam );*/
for(num=pos; num<tam; num++) {
if( soma + vet[num] <= valor ) {
soma += vet[num];
if( backtrack( vet, pos+1, soma, valor, tam ) )
return 1;
}
}
return 0;
}
int main()
{
int resp; // 1: a divisao eh possivel; 0: a divisao nao eh possivel
int X, Y, N; // variaveis citadas no enunciado
int V[100]; // vetor que armazena os valores das pecas da arca
int i,k; // variaveis auxiliares
int valorX, valorY; // variavel para armazenar o valor final do x e do y
int total; // todos os valores dos objetos da arca somados
int dif; // valor da diferenca entre os valores finais de x e de y
for(k=1;;k++)
{
valorX =0;
valorY = 0;
resp = 0;
total = 0;
scanf("%d %d %d",&X,&Y,&N);
if((X==0 && Y==0 && N==0) || X>50 || X<0 || Y>50 || Y<0 || N>100 || N<0)
break;
for(i=0;i<N;i++){
scanf("%d",&V[i]);
if(V[i]>100)
V[i] = 100;
if(V[i]<1)
V[i] = 1;
total+=V[i];
}
if(X <= Y){
valorX = X+total;
if(valorX >= Y){
dif = valorX - Y;
if(dif == 0)
resp = 1;
if(dif%2 == 1)
resp = 0;
else{
for(i=0;i<N;i++){
if( backtrack( V, i, 0, dif/2, N ) ){
resp = 1;
break;
}
}
}
/*for(i=0;i<N;i++){
if(V[i] == dif/2)
resp = 1;
}*/
}
else
resp = 0;
}
else{
printf("pera ai\n");
}
if(resp == 1)
printf("Teste %d\nS\n\n",k);
else
printf("Teste %d\nN\n\n",k);
}
return 0;
}
Creio que não haja erro na lógica, mas tem algo no código que o impede de funcionar corretamente, alguém poderia me dizer o que é?