bom dia!
Não sei onde vi que so precisam +4. Nada a ver.
Em ter, 26 de fev de 2019 14:09, Pedro José Boa tarde!
>
> Embora seja bastante óbvio. Só me apercebi agora.
> Para o caso b, quando nós chegamos ao pior caso com n testes, sem
> resultado. No algoritmo primordial. Pegava-se dois pares
Boa tarde!
Embora seja bastante óbvio. Só me apercebi agora.
Para o caso b, quando nós chegamos ao pior caso com n testes, sem
resultado. No algoritmo primordial. Pegava-se dois pares falhos e tínhamos
+ 4 chances. n+4.
Depois o Ralph, o melhorou e caímos em n +3.
O que havia reparado é que para
Provando que n+2 eh otimo no item (a):
Suponha que voce arrumou um jeito de testar n+1 pares e garantir que
funciona. Vou mostrar que tah errado.
Afinal, nos seus n+1 pares tem 2n+2 baterias, contando repeticoes.
Portanto, alguma das 2n+1 baterias aparece em (pelo menos) dois dos seus
pares.
Era n+2 para o item (a); o que eu falei ali foi um jeito de fazer em n+3
para o item (b), melhor que o n+4 que eu tinha falado antes.
Abraco, Ralph.
On Sun, Feb 24, 2019 at 5:14 PM Pedro José wrote:
> Boa tarde!
> Ralph,
> também não sei se é ótimo. Postei a resposta para provocar.
> Só que
Boa tarde!
Será que não sai pelo princípio de gavetas?
Aí garante-se que é mínimo?
Sds,
PJMS.
Em dom, 24 de fev de 2019 às 17:02, Pedro José
escreveu:
> Boa tarde!
> Ralph,
> também não sei se é ótimo. Postei a resposta para provocar.
> Só que você afirmou ter um método melhor, mas não foi.
Boa tarde!
Ralph,
também não sei se é ótimo. Postei a resposta para provocar.
Só que você afirmou ter um método melhor, mas não foi. Para a) com n+2
estava garantido acender. Com o que você propôs podemos atingir n+3. Então
não foi melhor.
Ou talvez não tenha compreendido.
Sds,
PJMS
Em dom, 24
Boa tarde!
a) Você pode ter n baterias com falha e n+1 sem estar em modo de falha.
Seu pior caso é sempre pegar uma ruim e uma boa, pois aí você nem acende a
lâmpada nem esgota rapidamente as em modo de falha.
Quando você fizer n tentativas, a que sobrou é boa.
E em cada lote tem uma boa e uma em
b) Tem um jeito melhor: comece testando ab,ac,bc. Se der errado, significa
que tem (pelo menos) 2 ruins aqui, entao sobram 2n-3 baterias onde tem mais
boas do que ruins... O que eh exatamente o item (a)! (Bom, trocando n por
n-2). Entao pelo metodo da (a), conseguimos um par de baterias boas em
Bom, tenho estrategias boas, mas tem que provar que sao otimas (ou arrumar
uma melhor):
a) Faca n tentativas com 2 baterias cada, sem intersecao. Se nenhuma dessas
tentativas der certo, voce eh muito azarado e cada par tinha exatamente uma
bateria ruim. Bom, entao a bateria que nao foi testada
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|
10 matches
Mail list logo
