{"id":143,"date":"2016-10-10T13:01:48","date_gmt":"2016-10-10T16:01:48","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/competir\/?p=143"},"modified":"2017-05-17T13:29:39","modified_gmt":"2017-05-17T16:29:39","slug":"banda-obi2009","status":"publish","type":"post","link":"https:\/\/www.galirows.com.br\/meublog\/competir\/banda-obi2009\/","title":{"rendered":"Banda [OBI 2009]"},"content":{"rendered":"

(OBI2009, Fase 2, N\u00edvel 1) <\/strong><\/p>\n

Jimmy \u00e9 um garoto muito esperto que adora m\u00fasica. No \u00faltimo m\u00eas ele ganhou um campeonato de um jogo cujo objetivo \u00e9 tocar guitarra. Empolgado, Jimmy decidiu montar uma banda. Para Jimmy a banda perfeita tem quatro integrantes, ele e mais tr\u00eas: um baterista, um baixista e um cantor.<\/p>\n

Agora Jimmy precisa encontrar os outros integrantes da banda. Para isto ele reuniu todos os \u00e1lbuns que encontrou na internet e, ap\u00f3s escut\u00e1-los diversas vezes, compilou o que ele chama de lista de entrosamento entre m\u00fasicos<\/i>. Nessa lista ele atribui, para cada par de m\u00fasicos que j\u00e1 tocaram juntos, uma nota inteira de 1 a 100, que \u00e9 uma medida de qu\u00e3o bem os m\u00fasicos tocam juntos (o n\u00edvel de entrosamento<\/i> entre eles). Se dois m\u00fasicos nunca tocaram juntos o n\u00edvel de entrosamento \u00e9 zero. Jimmy nunca tocou com nenhum m\u00fasico da lista.<\/p>\n

Jimmy pretende formar a sua banda a partir da lista de entrosamento entre m\u00fasicos, da seguinte maneira: ele quer escolher os outros tr\u00eas m\u00fasicos de tal forma que a soma dos n\u00edveis de entrosamento dos integrantes da banda seja a maior poss\u00edvel (ou seja, a soma dos n\u00edveis de entrosamento dos tr\u00eas pares poss\u00edveis de serem formados entre os tr\u00eas novos integrantes seja a maior poss\u00edvel).<\/p>\n

Mas a lista de entrosamento entre m\u00fasicos ficou muito grande e Jimmy n\u00e3o est\u00e1 conseguindo escolher os integrantes. Por isso, Jimmy est\u00e1 pedindo sua ajuda.<\/p>\n

<\/p>\n

Tarefa<\/h3>\n

Voc\u00ea deve ajudar Jimmy a montar a melhor banda poss\u00edvel fazendo um programa que receba uma lista contendo o n\u00edvel de entrosamento para cada par de m\u00fasicos que j\u00e1 tocaram junto, e determine os m\u00fasicos que formariam a melhor banda.<\/p>\n

Entrada<\/h3>\n

A entrada cont\u00e9m um \u00fanico conjunto de testes, que deve ser lido do dispositivo de entrada padr\u00e3o<\/i> (normalmente o teclado).<\/p>\n

A primeira linha da entrada \u00e9 formada por dois inteiros N<\/i> e M<\/i> , informando respectivamente o n\u00famero de m\u00fasicos (3 \u2264 N<\/i> \u2264 100) e o n\u00famero de pares de m\u00fasicos que j\u00e1 tocaram juntos (0 \u2264 M<\/i> \u2264 104<\/sup>). Os m\u00fasicos s\u00e3o identificados por n\u00fameros inteiros de 1 a N<\/i> . Cada uma das M<\/i> linhas seguintes cont\u00e9m tr\u00eas inteiros X<\/i>, Y<\/i> e Z<\/i>, em que X<\/i> e Y<\/i> representa um par de m\u00fasicos (1 \u2264 X<\/i> \u2264 N<\/i> , 1 \u2264 Y<\/i> \u2264 N<\/i> e X<\/i> \u2260 Y<\/i> ) e Z<\/i> representa o seu n\u00edvel de entrosamento (1 \u2264 Z<\/i> \u2264 100). Cada par de m\u00fasicos que j\u00e1 tocou junto aparece uma \u00fanica vez na entrada.<\/p>\n

Sa\u00edda<\/h3>\n

Seu programa deve imprimir, na sa\u00edda padr\u00e3o<\/i>, uma \u00fanica linha, contendo tr\u00eas n\u00fameros inteiros separados por espa\u00e7o em branco, identificando os tr\u00eas outros m\u00fasicos que devem compor a banda (em qualquer ordem). Se existir mais de uma melhor banda, Jimmy contenta-se com qualquer uma.<\/p>\n

Exemplos<\/h3>\n\n\n\n\n\n
Entrada<\/strong><\/td>\nSa\u00edda<\/strong><\/td>\n<\/tr>\n
3 3
\n1 2 50
\n2 3 27
\n3 1 1<\/td>\n		1 2 3<\/td>\n<\/tr>\n
5 8
\n1 2 50
\n1 3 50
\n1 4 50
\n2 3 50
\n2 5 10
\n3 4 50
\n3 5 25
\n4 5 20<\/td>\n		1 3 4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

A quest\u00e3o pode ser acessada atrav\u00e9s do link:\u00a0http:\/\/olimpiada.ic.unicamp.br\/pratique\/programacao\/nivel1\/2009f2p1_banda<\/a><\/p>\n

Nesse link tamb\u00e9m existe a op\u00e7\u00e3o de testar o algoritmo desenvolvido e ver automaticamente se o algoritmo est\u00e1 correto (bot\u00e3o \u201cSubmete solu\u00e7\u00e3o\u201d). Entre as linguagens de programa\u00e7\u00e3o dispon\u00edvel est\u00e1 Python, que \u00e9 linguagem utilizada na codifica\u00e7\u00e3o presente no v\u00eddeo.<\/p>\n

Dica<\/strong><\/p>\n

“O n\u00famero de v\u00e9rtices no grafo \u00e9 pequeno (apenas 100). Logo, \u00e9 poss\u00edvel verificar todas as combina\u00e7\u00f5es de 3 v\u00e9rtices. A solu\u00e7\u00e3o \u00e9 enumerar todas as combina\u00e7\u00f5es de 3 v\u00e9rtices, somar os pesos das arestas entre eles e escolher a combina\u00e7\u00e3o que maximize esta soma. A complexidade deste algoritmo \u00e9 O(n3)O(n3). Note que, pelas restri\u00e7\u00f5es da entrada, sempre h\u00e1 uma resposta (o n\u00famero de v\u00e9rtices \u00e9 pelo menos 3)”.<\/p>\n

Dica retirada de http:\/\/wiki.maratona.dcc.ufmg.br\/index.php\/BANDA09<\/a><\/p>\n

Solu\u00e7\u00e3o em C\/C++
\n<\/strong><\/p>\n

#include <stdio.h>\r\n\r\n#define MAXN 101\r\n\r\nint main() {\r\n  int musicos[MAXN][MAXN], n, m, x, y, z;\r\n  int aux = -1, sol[3];\r\n  int i, j, k;\r\n  \r\n  scanf(\"%d %d\", &n, &m);\r\n\r\n  for (i = 0; i < m; i++) {\r\n  \tscanf(\"%d %d %d\", &x, &y, &z); \r\n    x--; \r\n    y--;\r\n    musicos[x][y] = z;\r\n    musicos[y][x] = z;\r\n  }\r\n\r\n  for (i = 0; i < n; i++) {\r\n    for (j = i+1; j < n; j++) {\r\n      for (k = j+1; k < n; k++) {\r\n\t\tif (musicos[i][j] + musicos[i][k] + musicos[j][k] > aux) {\r\n\t  \t\taux = musicos[i][j] + musicos[i][k] + musicos[j][k];\r\n\t  \t\tsol[0] = i; \r\n\t  \t\tsol[1] = j; \r\n\t  \t\tsol[2] = k;\r\n\t\t}\r\n      }\r\n    }\r\n  }\r\n\r\n  printf(\"%d %d %d\\n\", sol[0]+1, sol[1]+1, sol[2]+1);\r\n\r\n  return 0;\r\n}<\/pre>\n
Experimente esse c\u00f3digo em:<\/strong> http:\/\/ideone.com\/kkO3uj<\/a><\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
(OBI2009, Fase 2, N\u00edvel 1) Jimmy \u00e9 um garoto muito esperto que adora m\u00fasica. No \u00faltimo m\u00eas ele ganhou um campeonato de um jogo cujo objetivo \u00e9 tocar guitarra. Empolgado, Jimmy decidiu montar uma banda. Para Jimmy a banda perfeita tem quatro integrantes, ele e mais tr\u00eas: um baterista, um baixista e um cantor. Agora […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,6],"tags":[12,10,9],"class_list":["post-143","post","type-post","status-publish","format-standard","hentry","category-cc","category-obi","tag-for","tag-if","tag-matriz"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t