El problema de Josephus
Flavius Josephus, un famoso historiador del primer siglo, no habría vivido para volverse famoso sin sus conocimientos matemáticos talentos matemáticos. Durante la guerra judía-romana, estuvo entre una banda de 41 rebeldes judíos atrapados en una cueva por los romanos. Prefiriendo el suicidio a la captura, los rebeldes decidieron formar un círculo y, procediendo a su alrededor, matar a una persona de cada 3 hasta que no quedara nadie. Pero Josephus, junto con un co-conspirador no acusado, no quería ninguna de estas tonterías suicidas; así que rápidamente calculó dónde deberían estar él y su amigo en el círculo vicioso.
En nuestra variación, comenzamos con personas numeradas del al alrededor de un círculo, con la -ésima persona al lado de la , y la -ésima al lado de la ra, y eliminamos a una persona de cada (se va recorriendo el círculo empezando por la ra persona, y se elimina una persona no, una sí, otra no, otra sí, y así sucesivamente, en cada paso se mueve hacia la siguiente persona que no ha sido eliminada) hasta que solo quede uno. Determine el número del ganador, .
Ejemplo si se empezara con , se eliminaría en el siguiente orden así que el ganadoe es el , por lo que .
Constantes:
, la cantidad de casos a procesar.
, la cantidad de personas en el círculo en cada caso.
Entrada
En la primera línea un entero , el número de casos a procesar.
En la i-ésima línea un entero , indicando que usted debe decir cual es el ganador del juego si se inicia con personas.
Salida
Para el i-ésimo caso imprima una línea, con un entero que representa el ganador del juego si se inicia con personas.
Puntuación
No habrá puntuación parcial en este problema.
Ejemplo de entrada
3
1
5
10
Ejemplo de salida
1
3
5
Comments
Cómo puedo obtener la entrada y devolver la salida en PROLOG?
Intente resolver este problema, saque las cuentas a papel y lapiz y el programa hace exactamente lo que pide el problema, lo compile en mi pc y funciona bien pero cuando envio la solucion del problema me salen muchas advertencias de compilacion y da MLE, alguien puede explicarme por que puede estar pasando eso por favor.
Tu solución parece correcta, en esencia, pero la cuestión del MLE (Memory Limit Exceeded) es porque has usado más memoria de la permitida en el problema. Si te fijas, tu programa consumió unos , y la memoria límite es de ; véase en las restricciones del ejercicio. Podrías optimizarlo en cuestión de memoria, intentando usar la menos posible, o hacerlo utilizando un enfoque más de matemáticas que de simulación. Suerte!
Buenísimo el ejercicio.