Questão Egg Drop do Google code Jam

[ivo_costa]

Olá, me inscrevi no google code jam e estou fazendo os exemplos, cheguei no exemplo 3 e empaquei. Eis o o enunciado da questão:

Imagine that you are in a building with F floors (starting at floor 1, the lowest floor), and you have a large number of identical eggs, each in its own identical protective container. For each floor in the building, you want to know whether or not an egg dropped from that floor will break. If an egg breaks when dropped from floor i, then all eggs are guaranteed to break when dropped from any floor j ≥ i. Likewise, if an egg doesn’t break when dropped from floor i, then all eggs are guaranteed to never break when dropped from any floor j ≤ i.

We can define Solvable(F, D, B) to be true if and only if there exists an algorithm to determine whether or not an egg will break when dropped from any floor of a building with F floors, with the following restrictions: you may drop a maximum of D eggs (one at a time, from any floors of your choosing), and you may break a maximum of B eggs. You can assume you have at least D eggs in your possession.

Input

The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as:

F D B

Solvable(F, D, B) is guaranteed to be true for all input cases.

Output

For each test case, output one line containing "Case #x: " followed by three space-separated integers: Fmax, Dmin, and Bmin. The definitions are as follows:

* Fmax is defined as the largest value of F' such that Solvable(F', D, B) is true, or -1 if this value would be greater than or equal to 232 (4294967296).
  (In other words, Fmax = -1 if and only if Solvable(232, D, B) is true.)
* Dmin is defined as the smallest value of D' such that Solvable(F, D', B) is true.
* Bmin is defined as the smallest value of B' such that Solvable(F, D, B') is true.

Sample

Input
2 (esse 2 é pra dizer que abaixo vem 2 testes)
3 3 3
7 5 3

Output
Case #1: 7 2 1
Case #2: 25 3 2

O que eu entendi da questão:
Vc tem uma construção com F andares e tem disponível consigo D ovos, podendo quebrar no máximo B ovos. Se vc jogar um ovo de um andar e ele quebrar é garantido que tbm quebrará nos andares superiores a esse, se vc jogar um ovo de um andar e ele não quebrar é garantida que tbm não quebrará nos andares inferiores a esse.

Então olhando os exemplos eu estou tentando entender como é possível, em uma construção de 3 andares eu ir com 2 ovos e quebrar apenas 1:

Input
2 (esse 2 é pra dizer que abaixo vem 2 testes)
3 3 3
7 5 3

Output
Case #1: 7 2 1 Em 3 andares eu só preciso de 2 ovos e vou quebrar no máximo 1. Eu consigo testar 7 andares com 3,3
Case #2: 25 3 2

Todas as possibilidades:
x = quebrou
o = Ñ quebrou

Começando pelo primeiro andar
1x
1o - 2x
1o - 2o - 3x
1o - 2o - 3o
pior resultado: joguei 3 ovos, 1 quebrou

Segundo andar
2o - 3x
2x - 1o
2x - 1x
pior resultado: joguei 2 ovos, 2 quebrou

Terceiro andar
3o
3x - 2o
3x - 2x - 1o
3x - 2x - 1x
pior resultado: joguei 3 ovos, 3 quebrou

Ou seja não existe possibilidade de conseguir testar tudo com apenas 2 ovos e quebrar no máximo 1. A menos que:

Seja garantido que nunca quebre no primeiro andar pois é o térreo.
Eu possa buscar de volta os ovos que não quebraram para jogar denovo, (mas isso tá fora, pq com apenas um ovo eu testava todos os andares, sempre começando no primeiro andar até o ovo quebrar)

Alguém consegue me explicar???

[victorwss]

Simples, você pode jogar D ovos mas quebrar no máximo B. Você não pode recuperar os ovos lançados mesmo que não tenham quebrado, senão não faria sentido D e B serem variáveis diferentes.

Não dá para tentar fazer algo tipo uma busca binária?

Se log2 F <= B com certeza isso funciona.

Jogue o ovo do andar F/2. Se F for ímpar arrendonda para baixo (diminui a chance de quebrar o ovo).
Se o ovo quebrar, vá para o andar F/4, senão para o andar 3F/4, e assim sucessivamente.

[ivo_costa]

Olá, eu tbm pensei nessa sua tese de usar o “Dividir para conquistar”, mas com 3 andares 2 ovos e quebrar no máximo 1 não funciona.
Vc tem idéia de como eu conseguiria fazer isso?

[victorwss]

[quote=ivo costa]Olá, eu tbm pensei nessa sua tese de usar o “Dividir para conquistar”, mas com 3 andares 2 ovos e quebrar no máximo 1 não funciona.
Vc tem idéia de como eu conseguiria fazer isso?[/quote]

Não existe forma de fazer isso com 3 andares 2 ovos e quebrar no máximo 1.

Hipótese A: Os ovos quebram de qualquer andar.
[color=green]A1. Jogue o ovo do primeiro andar. Ele vai quebrar. Você descobriu a resposta! Sobrou 1 ovo.[/color]
[color=red]A2. Jogue o ovo do segundo andar. Ele vai quebrar. Jogue o ovo do primeiro andar. Ele também quebra. PERDEU PLAYBOY![/color]
A3. Jogue o ovo do terceiro andar. Ele vai quebrar.
[color=red]A31. Jogue o ovo do primeiro andar. Ele vai quebrar. PERDEU![/color]
[color=red]A32. Jogue o ovo do segundo andar. Ele vai quebrar. PERDEU![/color]

Ou seja, na hipótese A, a única resposta possível é jogar do andar 1 (A1).

Hipótese B: Os ovos quebram nos andares 2 e 3.
B1. Jogue o ovo do primeiro andar. Ele não quebra.
[color=green]B12. Jogue o ovo do segundo andar, ele quebra. Você descobriu a resposta![/color]
[color=red]B13. Jogue o ovo do terceiro andar, ele quebra. Acabaram os ovos e você não achou a resposta! Você não sabe se ele quebra no andar 2.[/color]
[color=green]B2. Jogue o ovo do segundo andar. Ele vai quebrar. Jogue o ovo do primeiro andar, ele não quebra. Você descobriu a resposta![/color]
B3. Jogue o ovo do terceiro andar. Ele vai quebrar.
[color=red]B31. Jogue o ovo do primeiro andar. Ele não quebra. Acabaram os ovos e você não achou a resposta! Você não sabe se ele quebra no andar 2.[/color]
[color=red]B32. Jogue o ovo do segundo andar. Ele vai quebrar. PERDEU.[/color]

Ou seja, na hipótese B, as respostas possíveis são B12 e B2.

Hipótese C: Os ovos só quebram no andar 3.
C1. Jogue o ovo do primeiro andar. Ele não quebra.
[color=red]C12. Jogue o ovo do segundo andar, ele não quebra. Acabaram os ovos e você não descobriu a resposta! Não sabe se ele quebra no andar 3.[/color]
[color=red]C13. Jogue o ovo do terceiro andar, ele quebra. Acabaram os ovos e você não achou a resposta! Você não sabe se ele quebra no andar 2.[/color]
[color=green]C2. Jogue o ovo do segundo andar. Ele não vai quebrar. Jogue o ovo do terceiro andar, ele quebra. Você descobriu a resposta![/color]
C3. Jogue o ovo do terceiro andar. Ele vai quebrar.
[color=red]C31. Jogue o ovo do primeiro andar. Ele não quebra. Acabaram os ovos e você não achou a resposta! Você não sabe se ele quebra no andar 2.[/color]
[color=green]C32. Jogue o ovo do segundo andar. Ele não vai quebrar. Você achou a resposta.[/color]

Ou seja, na hipótese C, as respostas possíveis são C2 e C32.

Hipótese D: Os ovos nunca quebram.
D1. Jogue o ovo do primeiro andar. Ele não quebra.
[color=red]D12. Jogue o ovo do segundo andar, ele não quebra. Acabaram os ovos e você não descobriu a resposta! Não sabe se ele quebra no andar 3.[/color]
[color=green]D13. Jogue o ovo do terceiro andar, ele não quebra. Você achou a resposta.[/color]
[color=green]D2. Jogue o ovo do segundo andar. Ele não vai quebrar. Jogue o ovo do terceiro andar, ele não quebra. Você descobriu a resposta![/color]
[color=green]D3. Jogue o ovo do terceiro andar. Ele não vai quebrar. Você achou a resposta e ainda sobrou um ovo![/color]

Ou seja, na hipótese D, as respostas possíveis são D13, D2 e D3.

As respostas são então:
A1
B12 e B2
C2 e C32
D13, D2 e D3

O problema é que você não sabe qual é a hipótese verdadeira! Se você começar do andar 1, você se ferrou se a resposta for C. Se você começar no andar 2, você se ferrou se a resposta for A. Se começar no andar 3, você se ferrou se a resposta dor A ou B. Portanto, não existe forma de fazer com 100% de certeza que vai funcionar tendo 3 andares, 2 ovos e no máximo 1 quebra.

[ivo_costa]

Foi bem isso que eu pensei.
NÃO TEM COMO 3 ANDARES 2 OVOS E 1 QUEBRA.

Eu vou esperar mais um pouco, pra ver se alguem dá um luz (pq pode ser que eu tenha entendido errado a questão), e vou mandar um e-mail para o realizadores do concurso. Imagina começa o jogo e o cara fica na merda por causa de um erro de digitação ou coisa parecida.

Valeu cara!

[ualex]

[quote=ivo costa]Olá, eu tbm pensei nessa sua tese de usar o “Dividir para conquistar”, mas com 3 andares 2 ovos e quebrar no máximo 1 não funciona.
Vc tem idéia de como eu conseguiria fazer isso?[/quote]

cara não se entendi… mais tipo…

vc tem 2 ovos… e 3 andares…

tipo joga o primeiro do primeiro andar… e pela regra se quebrar então o outro vai quebrar nos outros andares… agora senão quebrar… pronto. como vc tem dois ovos o unico que pode quebrar vai ser este ultimo ovo…

mas dae tanto faz… porque vc só vai quebrar um…

mais nem sei se compensa… ficar quebrando ovo…

[ivo_costa]

Se vc joga no primeiro andar e não quebrar, então tem que jogar no segundo andar e ver se quebra, se denovo não quebrar então vai ter que jogar outro do terceiro andar pra ver se quebra.

A moral da questão é vc dizer no final do teste se é possível com 2 ovos testar todos os 3 andares, e dizer com toda certeza , tais andares quebram e tais andares não quebram.

[ualex]

[quote=ivo costa]Se vc joga no primeiro andar e não quebrar, então tem que jogar no segundo andar e ver se quebra, se denovo não quebrar então vai ter que jogar outro do terceiro andar pra ver se quebra.

A moral da questão é vc dizer no final do teste se é possível com 2 ovos testar todos os 3 andares, e dizer com toda certeza , tais andares quebram e tais andares não quebram.[/quote]

agora eu to começando a entender a questão… mais na onde diz que no final… você só pode ter quebrado um ovo ?

[victorwss]

Ah, entendi
Input 3 3 3 - Output 7 2 1
Isso significa que:

A. Tendo 3 ovos e podendo quebrar até 3, é possível resolver sem erro com até 7 andares.
B. Em um prédio de 3 andares e com a restrição que apenas 3 ovos podem ser quebrados, serão necessários 2 ovos. (o que implica que ambos podem ser quebrados).
C. Tendo 3 andares e 3 ovos, é possível resolver-se quebrando no máximo 1 ovo.

[victorwss]

Input 7 5 3 - Output 25 3 2

A. Tendo 5 ovos e podendo quebrar até 3, é possível resolver-se para prédios de até 25 andares.
B. Em um prédio de 7 andares podendo quebrar até 3 ovos, são necessários 3 ovos.
C. Em um prédio de 7 andares tendo 5 ovos, é possível resolver-se quebrando no máximo 2.

Ou seja, na verdade são 3 problemas diferentes em um só!

[ivo_costa]

Uhummmmm.
Eu acho que tu tá certo.
Eu entendi errado a questão.
Vou tentar resolver o algoritmo e postar lá pra ver se funfa.

Flw meu!

ps.: Quem sabe tu não participa tbm, premiação em dinheiro e empregos no google para os melhores, \o/.

[Bruno_Laturner]

A quantidade de ovos define o teu espaço de procura numa busca binária.

Com um ovo, você testa um andar, dois ovos, dois andares, três ovos, quatro andares, quatro, oito. O número de andares é 2^(n ovos - 1).

Como você tem um espaço limitado, você precisa procurar de espaço em espaço no universo de procura.

Se um prédio tem 16 andares, e você tem 3 ovos, você testa nos primeiros 4 andares, depois do 5º ao 8º, depois do 9º ao 12º e finalmente nos 13º ao 16. 4 em 4 andares.

Se em um desses testes o ovo quebrar, por exemplo, no 12, isso quer dizer que o andar procurado está entre 9º e o 12º. Daí começa a busca binária. Primeiro no 10º, se quebrar desça pro 9º, se não, suba para o 11º. Se não quebrou, você sobe e testa novamente. Se quebrar, é o 11º, senão, é o 12º.

[luistiagos]

neste exercicio eu não entendi estes 3 parametros passados e as saidas… afinal oq deve ser passado de parametro e o que realmente deve ser a saida?

[luistiagos]

???

[Bruno_Laturner]

Leia o texto.

F D B

F = número de andares
D = número de ovos
B = numéro máximo de ovos que podem quebra

A Saída é

Case #x: Fmax Dmin Bmin

Fmax = Maior andar encontrado
Dmin = Número de ovos usados
Bmin = Número de ovos quebrados

[ivo_costa]

Assim:

Ele te passa 3 3 3 (3=andares,3=ovos,3=maximo de ovos quebrados)

Voce tem que responder 3 coisas em 1:

3 3 1 (com 3 andares e 3 ovos eu consigo dizer quais andares quebram e quais andares não quebram quebrando apenas 1 ovo)

3 2 3 (com 3 andares e podendo quebrar tres ovos eu só preciso de dois ovos para determinar quais andares quebram e quais não quebram)

7 3 3 (com 3 ovos e podendo quebrar os 3 eu consigo testar até 7 andares)

resposta final (output)
7 2 1

Cabe a ti desenhar num papel todas as possibilidades com 3 ovos para ver que da pra fazer 3 3 1, 3 2 2 e 7 3 2.

ps.: Se as questões do jogo forem tudo desse naipe eu não vou passar da primeira fase.
A primeira e a segunda eu até consiguia fazer em um dia, mas essa é tri foda.
To dando um tempo pra ela, depois vou ver se consigo fazer.

[mfvwvfm]

Alguém conseguiu entender pq, para o caso solvable(7,5,3), o valor máximo de F é 25 ? Eu consigo resolver até 31 andares com 5 ovos!

[ivo_costa]

Eh possivel resolver 31 andares com 5 ovos e podendo quebrar os CINCO ovos.

Mas com 5 ovos e podendo quebrar apenas TRES ovos, o máximo é realmente 25 andares.

[luistiagos]

não entendi esse esquema de 3 respostas em uma…

[victorwss]

…

Você fornece três entradas e tem três saídas.
O problema 1 recebe a entrada 2 e a entrada 3 e fornece a saída 1.
O problema 2 recebe a entrada 1 e a entrada 3 e fornece a saída 2.
O problema 3 recebe a entrada 1 e a entrada 2 e fornece a saída 3.