Seu desafio:
Você está no 0º andar de um edifício infinitamente alto. Em qualquer andar, você pode caminhar até a janela e soltar um ovo. Seu objetivo é descobrir o piso mais alto que o ovo possa suportar sem quebrar. No entanto, você tem no máximo três ovos para descobrir isso, mas precisa minimizar o número de tentativas.
Em termos formais:
- Você recebe uma função
f(n)
que retornabool(n <= X)
para um desconhecidoX
, onde0 <= X
- Você deve retornar o valor de
X
(sem acessá-lo diretamente) f(n)
deve retornar apenasFalse
um máximo de3
vezes (em um único caso de teste). Se retornarFalse
mais do que isso, sua resposta será desqualificada.
Restrições
Sua pontuação é o número total de chamadas feitas f(n)
(nos casos de teste abaixo)
Se desejar, você pode deixar de passar uma função e simplesmente "simular" a situação acima. No entanto , seu algoritmo de solução não deve saber nada X
.
Seu algoritmo não deve codificar os casos de teste, ou no máximo X
. Se eu regenerar os números ou adicionar mais, seu programa deve ser capaz de lidar com eles (com uma pontuação semelhante).
Se o seu idioma não suportar números inteiros de precisão arbitrários, você poderá usar o long
tipo de dados. Se o seu idioma também não for compatível, você estará sem sorte.
O enésimo caso de teste é gerado usando o seguinte:
g(n) = max(g(n-1)*random(1,1.5), n+1), g(0) = 0
ou aproximadamente 1.25^n
Casos de teste:
0,1,2,3,4,6,7,8,10,14,15,18,20,27,29,40,57,61,91,104,133,194,233,308,425,530,735,1057,1308,1874,2576,3162,3769,3804,4872,6309,7731,11167,11476,15223,15603,16034,22761,29204,35268,42481,56238,68723,83062,95681,113965,152145,202644,287964,335302,376279,466202,475558,666030,743517,782403,903170,1078242,1435682,1856036,2373214,3283373,4545125,6215594,7309899,7848365,8096538,10409246,15103057,20271921,22186329,23602446,32341327,33354300,46852754,65157555,93637992,107681394,152487773,181996529,225801707,324194358,435824227,579337939,600264328,827690923,1129093889,1260597310,1473972478,1952345052,1977336057,2512749509,3278750235,3747691805,5146052509
Este é um desafio de código e a pessoa com a pontuação mais baixa ganha!
fonte
Respostas:
Javascript,
44285944285774825 chamadasTeste aqui
Pontuações para cada caso de teste individual:
Como funciona:
1 ovo:
Quando houver um ovo, a melhor estratégia é subir 1 andar por vez e retornar o andar diretamente abaixo do piso, onde ele quebra primeiro.
2 ovos:
Quando temos dois ovos, o número máximo de andares que precisamos verificar será o menor n para o qual T n é maior que o intervalo de andares que precisamos verificar. T n é o enésimo número do triângulo. O primeiro arremesso será realizado no nono andar. O segundo arremesso será feito nos
n - 1
andares acima do primeiro arremesso. O mésimo arremesso será realizado nosn - m + 1
andares acima dom - 1
arremesso. Após o ovo quebrar, serão necessáriosn - m
lances para determinar o piso pelo primeiro método.3 ovos:
Com o primeiro dos nossos ovos, devemos determinar um limite superior para o andar mais alto. Originalmente, eu fazia isso duplicando o número do andar de cada vez. Depois de analisar o algoritmo para 2 ovos, pensei que talvez fosse melhor se cada vez que jogássemos o ovo, os lances máximos para encontrar o piso correto com 2 ovos aumentassem em 1. Isso pode ser satisfeito usando os números tetraédricos. Após o primeiro esmagamento dos ovos, podemos usar os métodos acima para os demais ovos.
O número máximo de gotas necessárias para determinar o piso deve ser ideal. No entanto, um algoritmo melhor provavelmente poderia ser encontrado onde a média de gotas de ovo é melhor.
fonte
Java, 68985 chamadas
Resultado dos testes:
Programa de teste:
Enquanto otimizava, tentei fazer o número de tentativas com cada ovo aproximadamente igual.
fonte
Ruby,
6746666026 chamadasCódigo do teste:
Resultados:
Esse algoritmo funciona como meu antigo, mas tem algumas diferenças:
A primeira queda de ovo é no andar 8
O primeiro incremento é 8 * 8 = 64
Esses números são o resultado do ajuste fino aleatório à mão.
fonte