Ajudinha em problema

[marty]

Eu tenho 13 anos e sou iniciante em C. Conheci a linguagem quando, por prêmio de uma olimpíada de lógica(OBI, pra quem conhece), ganhei um curso de introdução à programação. Agora eu estou estudando para o nível de programação dessa olimpíada, mas me deparei com um problema que n consigo resolver de jeito nenhum, alguém pode me ajudar?

O problema é o "Banda" dessa prova: http://olimpiada.ic.unicamp.br/passadas/OB...9_prog_f2nj.pdf

PS: Não consegui copiar o problema por conta do formato pdf da prova.

Editado Abril 28, 2011 por marty

[marty]

será q essa solução funcionaria para todos os casos? q eu achei q usar matriz n tornaria o programa muito eficiente mas eu n consegui pensar em outro modo de resolvê-lo:

/*Banda*/

#include <stdio.h>
#include <stdlib.h>

int main () {
    
    int matriz[100][100],pares,quant,c1, c2, c3, mus1, mus2, final[3], somaini=0, somaf=0;
    
    scanf("%d", &quant);
    
    /*ZERAR O NIVEL DE ENTROSAMENTO ENTRE OS PARES DE MÚSICOS*/    
    for (c1=0;c1<quant;c1++){
        for(c2=0;c2<quant;c2++){
            matriz[c1][c2] = 0;
        }
    }
    
    scanf ("%d", &pares);
    
    for (c1=0;c1<pares;c1++) {
        scanf ("%d %d %d",&mus1, &mus2, &c3);
        /*c3 foi usado nesse caso para substituir uma variável que guardaria o entrosamento*/
        matriz[mus1 - 1][mus2 - 1] = c3;
        matriz[mus2 - 1][mus1 - 1] = c3;
    }
       
    /*Encontrar a maior soma (por cada possibilidade)*/
    
    for (c1=0;c1<quant;c1++) {
        for(c2=0;c2<quant;c2++) {            
            if (c2!=c1) {            
               for (c3=0;c3<quant;c3++){                   
                   if ((c3!=c1) && (c3!=c2)) {                      
                      somaini += matriz[c1][c2];
                      somaini += matriz[c1][c3];
                      somaini += matriz[c2][c3];                                          
                      if (somaini > somaf) {                                  
                                  somaf = somaini;
                                  final[0] = c1;
                                  final[1] = c2;
                                  final[2] = c3;                                                              
                      }
                      somaini = 0;
                   }
               }
            }
        }
    }
                                  
    printf ("\n%d %d %d\n", final[0] + 1, final[1] + 1, final[2] + 1);
    
    
    system("pause");
    
    return 0;
    
}

Editado Abril 28, 2011 por kuroi
Adicionar tag CODE

[Myho]

Testei seu código com os valores dados no pdf que descreve o problema e a solução para o segundo caso foi diferente.

Deveria sair assim:

Entrada

5 8

1 2 50

1 3 50

1 4 50

2 3 50

2 5 10

3 4 50

3 5 25

4 5 20

Saıda

1 3 4

Mas saiu assim:

Entrada

5 8

1 2 50

1 3 50

1 4 50

2 3 50

2 5 10

3 4 50

3 5 25

4 5 20

Saıda

1 2 3

Edit* Reparei agora que a soma de 1 e 3, 2 e 3 e 3 e 4 são iguais.. então resultariam em saidas iguais.. então não é erro, foi só uma escolha mesmo.

Editado Abril 29, 2011 por Myho

[marty]

ah, sim, no problema diz q pode ser qualque banda, contanto q seja com a maior soma, eu consegui o gabarito, a solução oficial é essa: (cheguei perto dela)

/*Banda*/

#include <stdio.h>
#include <stdlib.h>

int main () {
    
    int matriz[100][100],pares,quant,c1, c2, c3, mus1, mus2, final[3], somaini=0, somaf=-1;
    
    
    scanf("%d", &quant);
    
    /*ZERAR O NIVEL DE ENTROSAMENTO ENTRE OS PARES DE MÚSICOS*/    
    for (c1=0;c1<quant;c1++){
        for(c2=0;c2<quant;c2++){
            matriz[c1][c2] = 0;
        }
    }
    
    scanf ("%d", &pares);
    
    for (c1=0;c1<pares;c1++) {
        scanf ("%d %d %d",&mus1, &mus2, &c3);
        /*c3 foi usado nesse caso para substituir uma variável que guardaria o entrosamento*/
        matriz[mus1 - 1][mus2 - 1] = c3;
        matriz[mus2 - 1][mus1 - 1] = c3;
    }
       
    /*Encontrar a maior soma (por cada possibilidade)*/
    
    for (c1=0;c1<quant;c1++) {
        for(c2=0;c2<quant;c2++) {            
            if (c2!=c1) {            
               for (c3=0;c3<quant;c3++){                   
                   if ((c3!=c1) && (c3!=c2)) {                      
                      somaini += matriz[c1][c2];
                      somaini += matriz[c1][c3];
                      somaini += matriz[c2][c3];     
                                                         
                      if (somaini > somaf) {                                  
                                  somaf = somaini;
                                  final[0] = c1;
                                  final[1] = c2;
                                  final[2] = c3;                                                              
                      }
                      somaini = 0;
                   }
               }
            }
        }
    }
   
                                  
    printf ("\n%d %d %d\n", final[0] + 1, final[1] + 1, final[2] + 1);
    
    
    system("pause");
    
        
    return 0;
    
}