Flashcard FC242135
Como determinar o mínimo de recreios necessários para concluir um torneio eliminatório, sabendo que há um máximo de jogos por recreio e que cada participante só joga uma vez por re
Outros Exercícios de Lógica
CESGRANRIO · 2010
Como determinar o mínimo de recreios necessários para concluir um torneio eliminatório, sabendo que há um máximo de jogos por recreio e que cada participante só joga uma vez por recreio?
Mostrar resposta e comentário
Resposta
Agrupe, em cada recreio, o máximo de jogos envolvendo jogadores distintos, respeitando o limite de jogos; jogos que dependem de resultados de outros não podem ocorrer no mesmo recreio.Explicação:
Calcule primeiro o total de jogos \(G = N-1\). Em cada recreio pode-se realizar até \(m\) jogos, mas não se pode colocar no mesmo recreio partidas cuja realização obrigue algum jogador a atuar duas vezes naquele recreio (ou seja, jogos dependentes em cadeia não podem ser no mesmo recreio). Portanto, organize os jogos em ordem e agrupe sucessivos jogos que envolvam conjuntos disjuntos de participantes até atingir \(m\); jogos que dependem de vencedores só poderão ser agendados em recreios posteriores.
Exemplo:
Torneio com 8 participantes: \(G = 8-1 = 7\) jogos e limite de \(m=3\) jogos por recreio.
Agendamento possível que minimiza recreios:
Recreio 1: 3 jogos (máximo) — jogos 1 a 3
Recreio 2: 2 jogos — jogos 4 e 5 (não causam que alguém jogue duas vezes neste recreio)
Recreio 3: 1 jogo — jogo 6 (depende de resultados anteriores e não pode coincidir com jogo 4 neste mesmo recreio sem fazer alguém jogar duas vezes)
Recreio 4: 1 jogo — final (jogo 7)
Total de recreios = 4 — agrupando o máximo de jogos com jogadores distintos em cada recreio, respeitando a dependência entre jogos.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236951
Conteúdo do catálogo FC Concursos · Atualizado em