| DJC | Programación Competitiva | Codeforces |

Contest 2147 - Codeforces - DJC

Link al contest Aquí

A. El camino creciente más corto

Link

límite de tiempo por prueba: 1 segundo
límite de memoria por prueba: 256 megabytes

Estás en (0,0) en una cuadrícula rectangular y quieres ir a (x,y).

Para hacerlo, se te permite realizar una secuencia de pasos.

Cada paso consiste en moverse una cantidad entera positiva de longitud en la dirección positiva del eje x o del eje y.

El primer paso debe ser a lo largo del eje x, el segundo a lo largo del eje y, el tercero a lo largo del eje x, y así sucesivamente. Formalmente, si numeramos los pasos desde uno en el orden en que se hacen, entonces los pasos impares deben ser a lo largo del eje x y los pares a lo largo del eje y.

Además, cada paso debe tener una longitud estrictamente mayor que la del paso anterior.

Imprime el número mínimo de pasos necesarios para llegar a (x,y), o −1 si es imposible.

Entrada Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba t (1 ≤ t ≤ 10⁴). La descripción de los casos de prueba sigue.

La primera y única línea de cada caso contiene dos enteros x e y (1 ≤ x,y ≤ 10⁹).

Salida Para cada caso de prueba, imprime el número mínimo de pasos para llegar a (x,y) o −1 si es imposible.

Ejemplo

Entrada

10  
1 2  
5 6  
4 2  
1 1  
2 1  
3 3  
5 1  
5 4  
752 18572  
95152 2322

Salida

2  
2  
3  
-1  
-1  
-1  
-1  
-1  
2  
3

Nota

En el segundo caso de prueba, puedes moverte a (5,0) avanzando 5 en el eje x y luego a (5,6) avanzando 6 en el eje y.

En el tercer caso de prueba, puedes moverte a (1,0), luego a (1,2), y finalmente a (4,2).

En el cuarto caso de prueba, llegar a (1,1) es imposible ya que después de moverte a (1,0) en el eje x, estás obligado a moverte al menos 2 en el eje y.

B. Construcción múltiple

Límite de tiempo por prueba: 1 segundo
Límite de memoria por prueba: 256 megabytes

Se te da un entero n.
Tu tarea es construir un arreglo de longitud 2⋅n tal que:

  1. Cada número entero de 1 a n aparezca exactamente dos veces en el arreglo.
  2. Para cada número x (1 ≤ x ≤ n), la distancia entre sus dos ocurrencias sea un múltiplo de x.

En otras palabras, si pₓ y qₓ son los índices de las dos ocurrencias de x, entonces |qₓ − pₓ| debe ser divisible por x.

Se puede demostrar que siempre existe una solución.

Entrada

Cada prueba contiene múltiples casos de prueba.
- La primera línea contiene el número de casos de prueba t (1 ≤ t ≤ 10⁴).
- Las siguientes t líneas contienen un único entero n (1 ≤ n ≤ 2⋅10⁵).

Se garantiza que la suma de n en todos los casos de prueba no excede 2⋅10⁵.

Salida

Para cada caso de prueba, imprime una línea que contenga 2⋅n enteros — el arreglo que satisface las condiciones dadas.

Si hay múltiples respuestas válidas, imprime cualquiera de ellas.

Ejemplo

Entrada


3
2
3
1

Salida


1 2 1 2
1 3 1 2 3 2
1 1

Nota

Enlace al visualizador

  • En el primer caso de prueba:
  • El número 1 aparece en las posiciones 1 y 3 → la distancia es 2, divisible por 1.

  • El número 2 aparece en las posiciones 2 y 4 → la distancia es 2, divisible por 2.

  • En el segundo caso de prueba:

  • El número 1 aparece en las posiciones 1 y 3 → la distancia es 2, divisible por 1.
  • El número 2 aparece en las posiciones 4 y 6 → la distancia es 2, divisible por 2.

  • El número 3 aparece en las posiciones 2 y 5 → la distancia es 3, divisible por 3.

  • En el tercer caso de prueba:

  • El número 1 aparece en las posiciones 1 y 2 → la distancia es 1, divisible por 1.

C. Conejos

Límite de tiempo por test: 2 segundos
Límite de memoria por test: 256 megabytes

Tienes n macetas de flores dispuestas en una línea numeradas del 1 al n de izquierda a derecha.
Algunas macetas contienen flores, mientras que otras están vacías.

Se te da una cadena binaria s que describe qué macetas tienen flores (si = 1) y cuáles están vacías (si = 0).

También tienes algunos conejos y quieres tomar una bonita foto de los conejos y las flores.
Quieres poner conejos en cada maceta vacía (si = 0), y para cada conejo puedes hacerlo mirar hacia la izquierda o hacia la derecha.

Desafortunadamente, los conejos son bastante traviesos e intentarán saltar, lo cual arruinará la foto.

Reglas

  • Cada conejo se preparará para saltar a la siguiente maceta en la dirección en la que mira.
  • No saltará si:
  • Ya hay un conejo en esa maceta.
  • Otro conejo se prepara para saltar a esa misma maceta desde el lado opuesto.
  • Los conejos no saltarán fuera de los bordes (un conejo en la maceta 1 mirando a la izquierda no saltará, lo mismo para un conejo en la maceta n mirando a la derecha).

Objetivo

Elegir las direcciones de los conejos de manera que nunca salten, permitiéndote tomar la foto.
Debes determinar si existe una disposición válida.

Entrada

Cada test contiene múltiples casos de prueba.

  • La primera línea contiene el número de casos de prueba t (1 ≤ t ≤ 10⁴).
  • La descripción de los casos de prueba sigue.

Para cada caso de prueba:
- La primera línea contiene un entero n (1 ≤ n ≤ 2·10⁵).
- La segunda línea contiene una cadena binaria s de tamaño n, que indica las macetas ocupadas y vacías.

Se garantiza que la suma de n en todos los casos no excede 2·10⁵.

Salida

Para cada caso de prueba, imprime "YES" si existe una configuración de conejos que satisfaga la condición, y "NO" en caso contrario.

Puedes imprimir la respuesta en cualquier combinación de mayúsculas o minúsculas.
Por ejemplo: "yEs", "yes", "Yes", "YES" serán reconocidas como respuestas positivas.

Ejemplo

Entrada 


12
4
0100
3
000
8
11011011
5
00100
1
1
5
01011
2
01
7
0101011
7
1101010
5
11001
4
1101
9
001101100

Salida 


SÍ
SÍ
NO
SÍ
SÍ
SÍ
SÍ
SÍ
SÍ
SÍ
NO
NO

Nota

Enlace al visualizador

Explicación (Caso 1):
- Una configuración válida:
- Conejo en la posición 1 → derecha
- Conejo en la posición 3 → izquierda
- Conejo en la posición 4 → izquierda

Ningún conejo se moverá porque:
- El conejo en la maceta 1 no saltará a la 2 (el de la 3 mira a la izquierda).
- El conejo en la maceta 3 no saltará a la 2 (el de la 1 mira a la derecha).
- El conejo en la maceta 4 no saltará a la 3 (ya hay un conejo).

Explicación (Caso 2):
- Una configuración válida:
- Conejo en la posición 1 → izquierda
- Conejo en la posición 2 → derecha
- Conejo en la posición 3 → izquierda

Ningún conejo se moverá porque:
- El conejo en la maceta 1 no saltará (borde).
- El conejo en la maceta 2 no saltará a la 3 (ya ocupada).
- El conejo en la maceta 3 no saltará a la 2 (ya ocupada).

Se puede probar que no existe una disposición válida en el Caso 3.

D Juego en el arreglo

E OR máximo con conteo de bits

F Consultas de intercambio

G Tetración modular

H Coloreo de flujo máximo con MCD

I1 Camino creciente más largo (Versión fácil)

I2 Camino creciente más largo (Versión difícil)

| DJC | Programación Competitiva | Codeforces |