El problema de Josephus

Points: 100

Time limit: 1.0s

Memory limit: 64M

Author:

humbertoyusta

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

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

Constantes:

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

$n (1 \leq n \leq 10^9)$ ~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$ ~T~, el número de casos a procesar.

En la i-ésima línea un entero $n_{i}$ ~n_{i}~, indicando que usted debe decir cual es el ganador del juego si se inicia con $n_{i}$ ~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}$ ~n_{i}~ personas.

Puntuación

No habrá puntuación parcial en este problema.

Ejemplo de entrada

Ejemplo de salida

1
3
5

Comments

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.

0

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

4

linkyless commented on May 29, 2022, 9:14 p.m. ← edited →

Buenísimo el ejercicio.