El problema de Josephus.

View as PDF

Submit solution


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

Author:
Problem types
Allowed languages
C, C++, Java, Python

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 \(1\)ra, y eliminamos a una persona de cada \(2\) (se va recorriendo el círculo empezando por la \(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)\).

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

There are no comments at the moment.