Algoritmo: você é o treinador de uma equipe de ciclismo com 25 membros e precisa determinar o ciclista mais rápido, o segundo e o terceiro mais rápidos para seleção para a equipe olímpica.

As outras variantes deste problema perguntam sobre a corrida de cavalos em vez de ciclistas.

Solução:

Seja o número de partidas jogadas até agora matchCount = 0;

Vamos nomear os jogadores como Ai, Bi, Ci, Di e Ei, onde 1 <= i <= 5

GRUPO 1 GRUPO 2 GRUPO 3 GRUPO 4 GRUPO 5
A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5
D1 D2 D3 D4 D5
E1 E2 E3 E4 E5

Agora, em 5 jogos diferentes, temos os 5 vencedores de cada um dos grupos. Sem perda de generalidade, podemos assumir que os vencedores são A1, A2, A3, A4 e A5 (Bi e Ci para 1 <= i <= 5 na 2ª e 3ª posições).

matchCount = 5

Agora vamos fazer uma corrida entre A1, A2, A3, A4 e A5.

matchCount = 5 + 1 = 6

Agora, sem qualquer perda de generalidade, podemos assumir que A1 é o vencedor e A2 e A3 estão na segunda e terceira posições, respectivamente. Portanto, se A1 for o vencedor, o mais próximo de A1 na corrida será B1, C1, A2 e A3. Outra corrida revelará os jogadores na 2ª e 3ª posições.

machCount = 6 + 1 = 7

Portanto, em 7 partidas podemos identificar os jogadores na 2ª e 3ª posição

Tagged