Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BANDA09 - Banda

 

Jimmy é um garoto muito esperto que adora música. No último mês ele ganhou um campeonato de um jogo cujo objetivo é tocar guitarra. Empolgado, Jimmy decidiu montar uma banda. Para Jimmy a banda perfeita tem quatro integrantes, ele e mais três: um baterista, um baixista e um cantor.

Agora Jimmy precisa encontrar os outros integrantes da banda. Para isto ele reuniu todos os álbums que encontrou na internet e, após escutá-los diversas vezes, compilou o que ele chama de lista de entrosamento entre músicos. Nessa lista ele atribui, para cada par de músicos que já tocaram juntos, uma nota inteira de 1 a 100, que é uma medida de quão bem os músicos tocam juntos (o nível de entrosamento entre eles). Se dois músicos nunca tocaram juntos o nível de entrosamento é zero. Jimmy nunca tocou com nenhum músico da lista.

Jimmy pretende formar a sua banda a partir da lista de entrosamento entre músicos, da seguinte maneira: ele quer escolher os outros três músicos de tal forma que a soma dos níveis de entrosamento dos integrantes da banda seja a maior possível (ou seja, a soma dos níveis de entrosamento dos três pares possíveis de serem formados entre os três novos integrantes seja a maior possível).

Mas a lista de entrosamento entre músicos ficou muito grande e Jimmy não está conseguindo escolher os integrantes. Por isso, Jimmy está pedindo sua ajuda.

Tarefa

Você deve ajudar Jimmy a montar a melhor banda possível fazendo um programa que receba uma lista contendo o nível de entrosamento para cada par de músicos que já tocaram junto, e determine os músicos que formariam a melhor banda.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha da entrada é formada por dois inteiros N e M, informando respectivamente o número de músicos (3 ≤ N ≤ 100) e o número de pares de músicos que já tocaram juntos (0 ≤ M ≤ 104). Os músicos são identificados por números inteiros de 1 a N. Cada uma das M linhas seguintes contém três inteiros X, Y e Z, em que X e Y representa um par de músicos (1 ≤ X ≤ N, 1 ≤ Y ≤ N e X ≠ Y ) e Z representa o seu nível de entrosamento (1 ≤ Z ≤ 100). Cada par de músicos que já tocou junto aparece uma única vez na entrada.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo três números inteiros separados por espaço em branco, identificando os três outros músicos que devem compor a banda (em qualquer ordem). Se existir mais de uma melhor banda, Jimmy contenta-se com qualquer uma.

Exemplos

Entrada
3 3
1 2 50
2 3 27
3 1 1

Saída
1 2 3

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

Adicionado por:Wanderley Guimarăes
Data:2012-06-03
Tempo limite:0.127s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2009 - fase 2 nível 1 e 2

hide comments
2017-10-07 16:10:30 Etapa


Last edit: 2017-10-07 16:11:15
2015-04-07 06:57:17 Pedro Caldeira
Boa Washington, salvou aqui. Tem uma cerveja na minha conta!
2014-12-25 22:16:20 José Raimundo [IFPB - GBA]
AVISO! A saída desse segundo caso TAMBÉM pode ser 1 2 3, além desta que está no exemplo mostrado!
2014-12-25 22:06:48 José Raimundo [IFPB - GBA]
If(Jimmy + um vocal + um baixista + um batera){
cout << Led Zeppelin;
} yeah!!

Obs. Se tiver algum problema esse tipo de comentário, eu tiro imediatamente! ;)
2014-04-28 04:58:46 Gabriel Duarte [UNIFESO]
Acho que tem um erro no segundo exemplo
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

O problema diz que a saída é 1 3 4, porém meu algoritmo gera 1 2 3 e ele passou aqui no SPOJ :/
2014-03-26 18:27:51 Leandro[FACENS]
dica...năo é em qualquer ordem...imprimam em ordem crescente dos músicos :S
2014-01-22 19:05:03 Washington
Cuidado ao inicializar as variáveis...

Exemplo de Entrada:
3 0

Saída para o Exemplo:
1 2 3

Fica aqui a dica
2012-12-24 01:01:58


Last edit: 2012-12-24 17:50:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.