1
Hi, I’m trying to solve this computer Olympics problem: http://olimpiada.ic.unicamp.br/passadas/pdf/provas/ProvaOBI2002.pdf
and here’s the code I’m developing
#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;
}
I believe there is no error in logic, but there is something in the code that prevents it from working properly, could someone tell me what it is?
What is the doubt? What is the error? Click [Dit] on the question and explain it better.
– user28595