El problema de Josephus


Submit solution


Points: 100
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

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 n personas numeradas del 1 al n alrededor de un círculo, con la i-ésima persona al lado de la i+1, y la n-ésima al lado de la 1ra, y eliminamos a una persona de cada 2 (se va recorriendo el círculo empezando por la 1ra 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, J(n).

Ejemplo si se empezara con n = 10, se eliminaría en el siguiente orden [2, 4, 6, 8, 10, 3, 7, 1, 9] así que el ganadoe es el 5, por lo que J(10) = 5.

Constantes:

T (1 \leq T \leq 10^4), la cantidad de casos a procesar.

n (1 \leq n \leq 10^9), la cantidad de personas en el círculo en cada caso.

Entrada

En la primera línea un entero T, el número de casos a procesar.

En la i-ésima línea un entero n_{i}, indicando que usted debe decir cual es el ganador del juego si se inicia con n_{i} personas.

Salida

Para el i-ésimo caso imprima una línea, con un entero que representa el ganador del juego si se inicia con n_{i} 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


  • 0
    Walber  commented on Nov. 5, 2024, 7:14 p.m.

    Cómo puedo obtener la entrada y devolver la salida en PROLOG?


  • 1
    Jaimemm  commented on April 4, 2024, 2:55 a.m.

    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.


    • 1
      linkyless  commented on April 4, 2024, 10:43 a.m.

      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 66MB, y la memoria límite es de 64MB; 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!


  • 6
    linkyless  commented on May 29, 2022, 9:14 p.m. edited

    Buenísimo el ejercicio.