Como el título puede sugerir, este problema está semi-inspirado por el educado Bot borracho miope de @NP
Nuestro pobre robot se coloca en una cuadrícula cartesiana en el origen, y después de cada minuto, se mueve 1 unidad en una de las cuatro direcciones (arriba, abajo, izquierda, derecha).
Después de n minutos, se activan todas las minas latentes en la cuadrícula, matando a cualquier robot pobre que pueda encontrarse sobre ellas. Las minas se encuentran en todas las coordenadas enteras que satisfacen la ecuación | y | = | x |.
Desafío
Se le proporcionará n , el número de minutos antes de la explosión de las minas, como entrada y como salida, debe encontrar la probabilidad de que el bot esté muerto .
Entrada : un número natural que representa n .
Salida : Supongamos que la probabilidad de que el bot esté muerto sea p / q, donde pyq son números enteros relativamente primos (q no puede ser 0, pero p sí). Salida p.
Reglas
- Su algoritmo no debe ejecutarse en tiempo exponencial o superior. Idealmente debería ejecutarse en tiempo polinómico o menos.
- Su algoritmo debe poder manejar entradas de
n
<20 (puede ajustarse si es demasiado difícil) en un tiempo razonable. - Este es un desafío de código de golf .
- Iterar sobre todas las posibilidades para un n dado definitivamente no será aceptado como respuesta.
Casos de prueba
1
->0
2
->3
4
->39
6
->135
8
->7735
10
->28287
Ejemplo de cálculo para n = 6
Tenemos 4 movimientos posibles: U, D, R y L. El número total de caminos que se pueden tomar es 4 ^ 6 o 4096. Hay 4 casos posibles que aterrizan a lo largo de la línea y = x: x, y = ± 1; x, y = ± 2; x, y = ± 3; o x = y = 0. Contaremos el número de formas de terminar en (1,1), (2,2) y (3,3), multiplicarlos por 4 para tener en cuenta los otros cuadrantes y sumar esto a la cantidad de formas de terminar en (0,0).
Caso 1: el bot termina en (3, 3). Para que el bot termine aquí, debe haber tenido 3 movimientos correctos y 3 movimientos hacia arriba. En otras palabras, el número total de formas de llegar aquí es la forma de reorganizar las letras en la secuencia RRRUUU, que es 6, elija 3 = 20.
Caso 2: El bot termina en (2,2). Para que el bot termine aquí, podría haber tenido 2 movimientos hacia arriba, 3 movimientos hacia la derecha y 1 movimiento hacia la izquierda; o 2 movimientos a la derecha, 3 movimientos hacia arriba y 1 movimiento hacia abajo. Por lo tanto, el número total de formas de llegar aquí es la suma de las formas de reorganizar las letras en las secuencias RRRLUU y UUUDRR, las cuales son (6 elegir 1) * (5 elegir 2) = 60, para un total de 120 posibilidades .
Caso 3: El bot termina en (1,1). Para que el bot termine aquí, podría haber tenido: 1 movimiento hacia la derecha, 3 movimientos hacia arriba y 2 movimientos hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia RUUUDD es (6 elegir 1) * (5 elegir 2) = 60.
1 movimiento hacia arriba, 3 movimientos hacia la derecha y 2 movimientos hacia la izquierda. En este caso, el número de formas de reorganizar las letras en la secuencia URRRLL es (6 elegir 1) * (5 elegir 2) = 60.
2 movimientos hacia la derecha, 1 movimiento hacia la izquierda, 2 movimientos hacia arriba y 1 movimiento hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia UUDRRL es (6 elegir 1) * (5 elegir 1) * (4 elegir 2) = 180.
Por lo tanto, el número total de formas de terminar en (1,1) es 300.
Caso 4: El bot termina en (0,0). Para que el bot termine aquí, podría haber tenido:
3 movimientos a la derecha y 3 movimientos a la izquierda. En este caso, el número de formas de reorganizar las letras en la secuencia RRRLLL es (6 elegir 3) = 20.
3 movimientos hacia arriba y 3 movimientos hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia UUUDDD es (6 elegir 3) = 20.
1 movimiento hacia la derecha, 1 movimiento hacia la izquierda, 2 movimientos hacia arriba y 2 movimientos hacia abajo. En este caso, el número de formas de reorganizar las letras en la secuencia RLUUDD es (6 elige 1) * (5 elige 1) * (4 elige 2) = 180.
1 movimiento hacia arriba, 1 movimiento hacia abajo, 2 movimientos hacia la derecha y 2 movimientos hacia la izquierda. En este caso, el número de formas de reorganizar las letras en la secuencia RRLLUD es (6 elegir 1) * (5 elegir 1) * (4 elegir 2) = 180.
Por lo tanto, el número total de formas de terminar en (0,0) es 400.
Al sumar estos casos, obtenemos que el número total de formas de terminar en | y | = | x | es 4 (20 + 120 + 300) + 400 = 2160. Por lo tanto, nuestra probabilidad es 2160/4096. Cuando esta fracción se reduce completamente, es 135/256, por lo que nuestra respuesta es 135 .
fuente
Respuestas:
Python 2 , 65 bytes
Pruébalo en línea!
La probabilidad de que el bot esté muerto se puede expresar como:
y se entiende que el binomio es igual a cuando no está completo.0 n/2
Podemos razonar así. ¿Cuál es la probabilidad de que el bot aterrice en la línea ? Esto sucede si el número total de movimientos hacia arriba y hacia la izquierda es igual al número total de movimientos hacia abajo y hacia la derecha. Esta es la misma probabilidad de que, digamos, arrojes una moneda veces y obtengas tantas colas como caras. Debe elegir volteos para que sean cabezas de volteos, lo que se puede hacer en formas, de posibles secuencias en general, dando probabilidady=x n n/2 n (nn/2) 2n
La probabilidad de aterrizar la línea también es . Entonces, la probabilidad de aterrizar en cualquier línea es la suma de estos o , excepto que estamos contando dos la probabilidad de aterrizar de en ambas líneas, y debemos restarlo para compensar.y=−x s 2s x=y=0
Resulta que la probabilidad de aterrizar en es solo , el producto de la probabilidad de aterrizar en cada línea. Podemos argumentar que los eventos son independientes de la siguiente manera: si elegimos una secuencia aleatoria de números iguales de "Arriba o Izquierda" y "Abajo o Derecha" para aterrizar en y del mismo modo con "Arriba o Derecha" y "Abajo o Izquierda" "para , podemos combinarlos de forma única en una secuencia de arriba, abajo, izquierda, derecha tomando la intersección de los pares de direcciones en cada posición.x=y=0 s2 x=y x=−y
Entonces, la probabilidad de aterrizar en o es .x=y x=−y 2s−s2
El código calcula el binomio usando esta expresión como con base . Para extraer el numerador de la fracción de probabilidad, observamos que el denominador es una potencia de 2, por lo que usamos la expresión para dividir la potencia máxima de 2 , expresada como el clásico truco de bits .(nn/2)
(b+1)**n/b**(n/2)%b
b=2**n
r/(r&-r)
r
r&-r
La solución se juega al golf escribiendo como para que solo se haga referencia una vez, y trabajando sin las fracciones para permanecer dentro de los enteros. El cálculo es tiempo polinomial en incluso con la forma funky de calcular binomios.2s−s2 1−(1−s)2 s 1/2n n
Después de escribir la prueba de la probabilidad de que el bot muera, encontré una forma posiblemente más limpia de probarlo y presentarlo.
Hagamos un seguimiento de los valores de y después de cada movimiento del bot. Cada una de las cuatro direcciones hacia arriba, abajo, izquierda, y derecha, ya sea incrementos o decrementos cada uno de y , con las cuatro direcciones que corresponden a las cuatro combinaciones.a=x+y b=x−y a b
Entonces, un movimiento aleatorio es equivalente a agregar aleatoriamente a e independientemente a . Esto es equivalente a hacer paseos aleatorios separados en y .±1 a ±1 b a b
Ahora, el robot termina en la línea o exactamente cuando o . Entonces, la probabilidad de terminar con es e igualmente para . Como las caminatas son independientes, la probabilidad de que y sea , por lo que la probabilidad de que al menos uno sea cero es el complemento .x=y x=−y a=0 b=0 a=0 s=12n(nn/2) b=0 a≠0 b≠0 (1−s)2 1−(1−s)2
fuente