The Lost Cow.
¡El Granjero Juan ha perdido su apreciada vaca Bessie, y él necesita encontrarla!
Afortunadamente, hay un solo camino que corre a lo largo de la granja, y el Granjero Juan sabe que Bessie debe estar en alguna ubicación en este camino. Si pensamos en el camino como una líneas numérica, entonces el Granjero Juan está actualmente en la posición y Bessie está actualmente en la posición
(desconocida para el Granjero Juan). Si el Granjero Juan únicamente supiera donde Bessie estaba ubicada, él podría caminar directamente hacia ella, recorriendo una distancia de
. Desafortunadamente, está oscuro afuera y el Granjero Juan no puede ver nada. La única manera que tiene para encontrar a Bessie es caminar de ida y vuelta hasta eventualmente llegar a su posición.
Tratando de encontrar la mejor estrategia para caminar de ida y vuelta en su búsqueda, el Granjero Juan consulta la literatura de investigación en ciencias de la computación y se divierte encontrando que este problema exactamente no únicamente ha sido estudiado por científicos en computación en el pasado, sino que realmente se llama "Problema de la Vaca Perdida" (¡esto es cierto de verdad!).
La solución recomendada para que el Granjero Juan encuentre a Bessie es moverse a posición , luego cambiar la dirección y moverse a la posición
, luego a la posición
y así sucesivamente, en un patrón "zig zag", en cada paso moviéndose el doble de desde su posición inicial. Como él ha leído durante su estudio de algoritmos para resolver el problema de la vaca perdida, esta aproximación le garantiza que él en el peor caso recorrerá 9 veces la distancia directa
entre él y Bessie antes de encontrarla (esto también es cierto, y el factor de 9 es el realmente el menor tal que en el peor caso cualquier estrategia puede lograr).
El Granjero Juan tiene curiosidad de verificar este resultado. Dados y
, por favor calcule la distancia total que él recorrerá de acuerdo a la estrategia zig-zag descrita anteriormente hasta encontrar a Bessie.
Entrada
La única línea de la entrada contiene dos enteros separados por espacio y
. Ambos están en el rango
.
Salida
Imprima una línea de salida, conteniendo la distancia que el Granjero Juan recorrerá para encontrar a Bessie.
Ejemplo de Entrada
3 6
Ejemplo de Salida
9
Comments