Jueguito y algoritmos...

[zuji]

Lo pusieron hoy en el laburo, está entretenido.

Tenemos 2 huevos y un edificio de 100 pisos. Sabemos que existe al menos un
piso a partir del cual cuando tirás el huevo desde ahí se rompe.
El objetivo es encontrar el piso de menor valor númerico (el piso más
bajo) en el cuál el huevo se rompe en la menor cantidad de pasos. Es
decir, dar un algortimo que en el peor caso tarde lo menos posible. Si
el huevo lo tiro y no se rompe, lo puedo volver a usar.

Ejemplo: Tirar el huevo en el piso 1. Si se rompe era ese,
sino lo tiro en el segundo. Si se rompe era ese, sino lo tiro en el
tercero... y así sucesivamente. Este algortimo en el peor caso tarda 100
pasos (si el piso en el que se rompía era el 100).

Ejemplo: Tiro el primer huevo en el piso 78. Si se rompe, uso el
OTRO huevo y lo voy tirando desde el 1 hasta el 78 (y hago el algoritmo
de arriba). Si no se rompe, hago el algoritmo de arriba también desde el
78 hasta el piso 100. Este algoritmo tiene como peor caso 78 pasos.


Por las dudas, la gracia es encontrar el menor peor caso.

[dDaunloz]

el huevo es ficticio? xq se romperia desde la planta baja :P

tomandolo como ficticio.. o mejor dicho un objeto el que desconocemos su consistencia y fragilidad(?)

lo mejor para mi, seria si al medio siempre

piso 50,

si se rompe - al 25


si se rompe - al 12



si se rompe - al 6



si NO se rompe - al 18


si NO se rompe - al 37



si se rompe - al 31



si NO se rompe - al 43

si NO se rompe - al 75


si se rompe - al 62



si se rompe - al 56



si NO se rompe - al 68


si NO se rompe - al 87



si se rompe - al 81



si NO se rompe - al 93

[zuji]

Claro, son huevos especiales, algo así como los que había que tener con Jumoge xD

En cuánto a la respuesta, no me hagan contar, pongan la cantidad de pasos del peor caso :P

Por otro lado no me quedo claro algo

"""
piso 50,

si se rompe - al 25



si se rompe - al 12


"""

Si no entendí mal ahí tiraste en el 50 y se rompió, entonces tiras el 2do en el 25. Ahí te quedaste sin huevos por lo que no podés seguir tirando, y en realidad no encontraste el piso más bajo porque capaz se rompía en el 8.

[dDaunloz]

ahh tenes 2 huevos? no habia entendido esa parte

[dDaunloz]

teniendo 2...

entonces lo mejor seria arrancar en el 2do piso e ir subiendo de a 2 pisos hasta que se rompa

piso 2 - no se rompe
piso 4 - no se rompe
piso 6 - no se rompe
piso 8 - no se rompe
piso 10 - se rompe

tonces bajo al 9 y tiro el otro..

si se rompe el 9 es el menor.. si no se rompe, es el 10

en el peor caso lo tiras 51 veces

edit: toy maquinando otro mas eficiente

[Dañel]

ahh tenes 2 huevos? no habia entendido esa parte citado fuera de contexto es muy gracioso.

Una más eficiente,

Arranco del 10 y si se rompe desde el 1,
si no se rompe, lo tiro del 20 y si se rompe del 11,
Así de diez en diez hasta romper el primero y bajar a la decena anterior +1, en el peor de los casos (que se rompa en el 99) llevaría 19 intentos, pero seguramente se pueda hacer mejor, me cuesta encontrar el óptimo para el primer lanzamiento de forma teórica, experimental sería ir probando en vez de 10, 11, 12 y así.

Saludos,
Dañel.

[dDaunloz]

bueno.. encontre una formula magica

la idea seria seleccionar un rango para dividir los 100 pisos

pongamole 10, entonces tiro el 1er huevo cada 10 pisos hasta que en uno se rompe
y luego tomo el segundo y lo tiro desde el siguiente en el que se salvo anteriormente hasta llegar a este

ej, se el primero se rompe en el 50, tonces tiro el 2do desde el 41 (en el 40 ya no se rompio) hasta el 49, si se rompe en el 45, fueron (5 + 5) 10 intentos

en el peor caso serian, 19 intentos,

piso 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93, 94, 95, 96, 97, 98, 99
o
piso 10, 1, 2, 3, 4, 5, 6, 7, 8, 9


luego variando un poco el rango, me di cuenta que esto aplica para varios rangos cumpliendo con la siguiente formula

100 DIV rango + rango - 1

rango 8 = 12 + 8 - 1 = 19
rango 9 = 11 + 9 - 1 = 19
rango 10 = 10 + 10 - 1 = 19
rango 11 = 9 + 11 - 1 = 19
rango 12 = 8 + 12 - 1 = 19
rango 13 = 7 + 13 - 1 = 19
rango 15 = 6 + 15 - 1 = 19


EDIT: bueno.. me gano de mano dañel.. pero esto llevo rato escribir :P

[Everybody]

No debe ser la mejor pero lo intento :P

Tiro en piso 10. Mientras no se rompa sigo subiendo de a 10 pisos. Si se rompe en el 100, use 10 tiradas.

Si tiro y se rompe en el piso 40 por ejemplo como ya se que en el 30 no se rompió, voy probando uno a uno del 31 al 39 hasta que se rompa. El peor caso ahí seria que se rompa en el 99. Usaría 10 tiradas del piso 10 al 100 y 9 del 91 al 99.
Peor caso = 19

[Juancho]

exacto, con los pares es la manera mas eficiente que tenes

[Everybody]

Escribimos los 3 lo mismo.

[dDaunloz]

Escribimos los 3 lo mismo.

es que viste lo que dicen... las mentes brillantes piensan como yo

[zuji]

Yo también morí en 19, pero un compañero lo resolvió en 14 así que otra vuelta tiene que haber :P

[dDaunloz]

y tenes el algoritmo? capaz q esta buggy :P

[Everybody]

Según Google es 14 si.

[dDaunloz]

bueno, no lo quise googlear.. asi que por ing inversa (?)
saque que serian intervalos variables
al ir restandole 1 al intervalo, te aseguras que los intentos sean constantes para el peor caso en cada intervalo

inter: 14, 13, 12, 11, 10, 09, 08, 07, 06, 05, 04
pisos: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99

si en el 14 se revienta te quedan 13 pisos desde el 1 al 13 para probar con el 2do huevo

si en el 14 no se rompe, le restas uno al intervalo, asi mantenes la misma cantidad de intentos si fuera el 26

1 (del 14) + 1 (del 27) + 12 (del 15 al 26)