Code error - Brazilian Computer Olympiad, C

Question

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?

Answer 1

I read the problem statement, but with my interpretation I could not understand its logic. I will summarize what I understood of the issue and how I did to solve the problem.

We know that

X + Y + sum of V = total

The goal is to divide the total for the two knowing that one already has X and the other already has Y. For the first to get half, there must be some value that validates the expression: X + VALOR = total/2. This value shall be formed from the combination of V values.

Ex: imagine that V has 3 values: V = V1, V2, V3, then I must create your combinations and check some validates the expression.

VALOR == V1
VALOR == V2
VALOR == V3
VALOR == V1 + V2
VALOR == V1 + V3
VALOR == V2 + V3
VALOR == V1 + V2 +V3

If any of the combinations validate the expression the return is positive (S) and if none validate the return is negative (N).

The big challenge of the question is to create a function that manages all these combinations. The function I developed for the problem was as follows:

void combinacoes( int vet[], int tam, int acum, int ini, int m, int result[]) {
    int i;
    if (m==0){
        for(i=ini; i< tam-m; i++){
            result[result[0]] = acum+vet[i];
            result[0]++;
        }
    }
    else{
        for(i=ini; i< tam-m; i++)
            combinacoes(vet, tam, acum+vet[i], 1+i, m-1, result);
    }
}

Being called so:

for(i=0;i<N;i++)
    combinacoes(V, N, 0, 0, i, result);

The i of for is passed in the parameter m of function. When passed 0 for this parameter, combinations will be made with only one value, when passed 1 the combinations will be made by adding two values, when step 2 combinations will be made by adding three values, etc...

The result is stored in the vector result (except in the position result[0] which is used to control the size of the vector within the function).

The whole code went like this:

#include <stdio.h>

void combinacoes( int vet[], int tam, int acum, int ini, int m, int result[]){
    int i;
    if (m==0)
    {
        for(i=ini; i< tam-m; i++){
            result[result[0]] = acum+vet[i];
            result[0]++;
        }
    }
    else{
        for(i=ini; i< tam-m; i++)
            combinacoes(vet, tam, acum+vet[i], 1+i, m-1, result);
    }
}

int somatorio(int vet[], int tam){
    int i, soma=0;
    for(i=0; i<tam; i++)
        soma += vet[i];
    return soma;
}

int verifica(int vet[], int tam, int valor){
    int i, coma=0;
    for(i=1; i<tam; i++)
        if(vet[i]==valor)
            return 1;
    return 0;
}


int main(){

    int X, Y, N; // variaveis citadas no enunciado
    int i; // variaveis auxiliares

    scanf("%d %d %d",&X,&Y,&N);

    int V[N]; // vetor que armazena os valores das pecas da arca

    for(i=0; i<N; i++)
        scanf("%d",&V[i]);

    int tam = (int)pow((float)2,(float)N);
    int result[tam];
    result[0]=1;

    //Cria um vetor em resut com todas as variações possiveis de valores
    for(i=0; i<N; i++)
        combinacoes(V, N, 0, 0, i, result);

    //Verifica se é possivel dividir e mostra o resultado
    int total = X+Y+somatorio(V, N);
    printf("Teste 1\n", total);
    if(verifica(result, tam, total/2-X))
        printf("S\n");
    else
        printf("N\n");
    printf("\n");

    return 0;
}

*Note: The code does not check the restrictions of the statement and the code only makes a test and ends.