2012/1/12 Ralph Teixeira <ralp...@gmail.com>:
> Nao precisa testar 53 trincas nao! Rapidinho, arrumo um algoritmo com
> 38 testes...
>
> Sejam ABCDEFGH as 8 pilhas, seja X o conjunto das 4 que funcionam. Ha
> C(8,4)=70 possibilidades para X.
>
> Agora, voce testa ABC; se NAO funcionar, isto jah elimina 5
> possibilidades para X (a saber, ABCD, ABCE, ABCF, ABCG, ABCH).
> Teste CDE. Se nao funcionar, eliminamos ACDE, BCDE, CDEF, CDEG e CDEH.
> EFG elimina mais 5; GHA elimina mais 5.
> Tente agora ADF, CFH, EHB e GBD. Se nada disso funcionar, jah
> eliminamos no total 40 possibilidades -- ateh aqui, todas disjuntas!
> Explicitamente, sobram apenas as seguintes 30 possibilidades para X:
> ABDE ABDH ABEF ABEG ABFG ABFH ACDG ACDH ACEF ACEG ACEH ACFG ADEG ADEH AEFH
> BCDF BCDH BCEF BCEG BCFG BCGH BDEF BDFH BFGH CDFG CDGH CEGH DEFH DEGH DFGH
>
> Mesmo que voce agora escolha uma trinca de cada um desses 30
> conjuntos, seria um total de 8+30=38 testes. Mas ainda dah para
> diminuir bastante, jah que varias trincas aparecem em varias dessas
> quadras!
>
> Quem dah menos? :)
32
> Abraco,
> Ralph
Eu acho que é outra idéia (que eu acho também dá pra ser "escovada"),
então aí vai:
O princípio é "manter a simetria" (circular) das pilhas.
Teste ABC, BCD, CDE, ... GHA, HAB. (8 testes).
Se nada disso der certo, não tem 3 pilhas boas em série, que eu noto
"bbb". Portanto, bb => a próxima é r.
Teste em seguida ABD, BCE, ... GHB, HAC.
Se nada disso der certo, não tem também "bbrb", portanto "bb => rr".
Para a "simetria", teste ACD, BDE, ..., GAB, HBC.
Isso impede "brbb", portanto "brb => r"
Para fechar a simetria, teste ABE, BCF, ..., GHC, HAD.
Isso impede "bbrrb", logo "bb => rrr".
Agora, se houvesse um "bb" em algum momento, teríamos logo depois um
rrr. A situação é a seguinte:
bb rrr ???
Sabemos que temos que colocar 2 bons, nos ??? que sobram. Só que o
último também não pode ser um b (afinal de contas, não há 3 bons
consecutivos). Portanto, é um "bb rrr bb r", que também é impossível
visto que temos um bb r b cíclico.
Assim, não há "bb", e portanto podemos ficar com as 6 primeiras que
haverá 3 bons e 3 ruins. Há 20 = C(6,3) combinações possíveis para as
6 pilhas. Mas acontece que a gente já testou
ABC, BCD, CDE, DEF (4)
ABD, BCE, CDF (3)
ACD, BDE, CEF (3)
ABE, BCF (2)
12 possibilidades que não deram certo. Restam apenas 8, uma delas com
certeza vai dar.
O que dá 8+8+8+8 ("simétricos") + 8 (restos dos 6 que a gente não testou).
A minha solução é meio "força bruta" comparada à do Ralph (que deve
ser mais fácil de "optimizar", mas sei lá. De repente eu dei sorte com
o método.
Abraços,
--
Bernardo Freitas Paulo da Costa
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
