/* * Solução do problema 'Copa do Mundo' (OBI 2010 - Nível 1, Fase 1) * * Maurício de Lemos Rodrigues Collares Neto () */ #include #include using namespace std; int main() { /* A observação importante para resolver este problema concisamente é que * podemos processar cada linha do diagrama dado separadamente. Os vence- * dores da linha de índice i estarão no array vencedores[i]. */ vector vencedores[5]; /* A linha 0 contém todos os times. */ for(char c = 'A'; c <= 'P'; c++) vencedores[0].push_back(c); /* E, para calcular a próxima linha, devemos pegar dois times consecutivos * da linha anterior, ler o resultado do jogo para saber quem ganhou, e co- * locar o vencedor na linha certa. */ for(int l = 1; l < 5; l++) { /* Estamos pulando de 2 em 2, pois o primeiro jogo é entre os times * 0 e 1 da linha anterior, o segundo é entre os times 2 e 3, e assim * por diante. Se pularmos de 2 em 2, os jogos serão sempre entre os * times j e j+1. */ for(int j = 0; j < vencedores[l-1].size(); j += 2) { int gols1, gols2; scanf("%d %d", &gols1, &gols2); if(gols1 > gols2) vencedores[l].push_back(vencedores[l-1][j]); else vencedores[l].push_back(vencedores[l-1][j+1]); } } /* A quinta linha (de índice 4) contém apenas um jogador: o vencedor. */ printf("%c\n", vencedores[4][0]); }