1

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 é?

1
  • 1
    Qual a duvida? Qual o erro? Clique em editar a pergunta e explique melhor.
    – user28595
    Commented 19/04/2017 às 23:29

1 Resposta 1

0

Eu li o enunciado problema, porém com a minha interpretação eu não consegui entender a sua lógica. Vou resumir o que entendi da questão e como fiz para resolver o problema.

Sabemos que

X + Y + somatório de V = total

O objetivo é dividir o total para os dois sabendo que um já possui X e o outro já possui Y. Para que o primeiro consiga metade, deve haver algum valor que valide a expressão: X + VALOR = total/2. Este valor deve ser formado a partir da combinação de valores de V.

Ex: imagine que V tenha 3 valores: V = V1, V2, V3, então eu devo criar suas combinações e verificar alguma valida a expressão.

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

Se alguma das combinações validar a expressão o retorno é positivo (S) e se nenhuma validar o retorno é negativo (N).

O grande desafio da questão é criar uma função que gere todas estas combinações. A função que desenvolvi para o problema foi a seguinte:

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);
    }
}

Sendo chamado assim:

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

O i do for é passado no parâmetro m da função. Quando passado 0 para essa parâmetro, serão feitas combinações com apenas um valor, quando passado 1 serão feitas as combinações somando dois valores, quando passo 2 serão feitas combinações somando três valores, etc...

O resultado é armazenado no vetor result (exceto na posição result[0] que é usada para fazer o controle do tamanho do vetor dentro da função).

O código completo ficou assim:

#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;
}

*Obs: O código não verifica as restrições do enunciado e o código só faz um teste e termina.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .