Josephus Queries.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

Problem type

Consideremos un juego en el que hay $n$ ~n~ niños (numerados $1,2,\dots,n$ ~1,2,\dots,n~) en un círculo. Durante el juego, cada segundo un niño se quita del círculo, hasta que no quede ninguno.

Su tarea consiste en procesar $q$ ~q~ consultas de la forma "cuando hay n niños, ¿quién es el k-ésimo niño que será eliminado?"

Entrada

La primera línea de entrada tiene un número entero $q$ ~q~: el número de consultas.

A continuación, hay $q$ ~q~ líneas que describen las consultas. Cada línea tiene dos enteros $n$ ~n~ y $k$ ~k~: el número del niño y la posición del niño.

Salida

Imprime $q$ ~q~ enteros: la respuesta para cada consulta.

Restricciones

$1 \leq q \leq 10^5$ ~1 \leq q \leq 10^5~.
$1 \leq k \le n \leq 10^9$ ~1 \leq k \le n \leq 10^9~.

Ejemplo de Entrada

Ejemplo de Salida

Comments

2

victoredel commented on July 16, 2025, 4:06 a.m. ← edited →

Resolveremos el problema de forma recursiva, reduciendo el problema al menos a la mitad en cada paso. Si $k<\frac{n}{2}$ ~k<\frac{n}{2}~ , podemos ver que la respuesta sería $2K$ ~2K~. De lo contrario, hemos eliminado todas las posiciones pares. Las posiciones impares se pueden renombrar desde $1,2,\ldots,\frac{n}{2}$ ~1,2,\ldots,\frac{n}{2}~Y podemos encontrar recursivamente la solución para ello. Y luego podemos volver a mapear a nuestro original $n$ ~n~ multiplicando por $2$ ~2~ y restando $1$ ~1~. La complejidad del tiempo es $O(logn)$ ~O(logn)~.