Já vi um problema parecido da OBM que dava pra resolver usando o teorema de Turan. Pra esse imaginei assim, VC separa as baterias em dois grupos, B das boas e R das ruins e liga duas se foram testadas juntas. O numero máximo de arestas que dá pra colocar sem a lampada acender é |B|×|R| +|R|×(|R|-1)/2.
Em dom, 24 de fev de 2019 11:40, Jeferson Almir <jefersonram...@gmail.com> escreveu: > Peço ajuda aos amigos da lista, sei que existe um problemas da obm > "parecido", aguardo dicas ou soluções. Eu tentei formar um grafo de > tentativas e penso como otimizar ele. > > a.) Existem 2n + 1 (n> 2) baterias. Não sabemos quais baterias são boas e > quais são ruins, mas sabemos que o número de baterias boas é maior do que o > número de baterias ruins. Uma lâmpada usa duas baterias e só funciona se > ambas forem boas. Qual é o menor número de tentativas suficientes para > fazer a lâmpada funcionar? > > b.) O mesmo problema, mas o número total de baterias é 2n (n> 2) e os > números de baterias boas e ruins são iguais. > > > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
