| DJC | Programación Competitiva | Codeforces |

Contest 2131 - Codeforces - DJC

Link al contest Aquí

A. Lever

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

En el Universo Divergente, La Palanca se itera a sí misma dadas dos matrices a y b de longitud n.
En cada iteración, La Palanca hará lo siguiente:

Elegir un índice aleatorio i tal que a[i] > b[i].
Luego, disminuir a[i] en 1.
Si no existe tal i, se ignora este paso.
Elegir un índice aleatorio i tal que a[i] < b[i].
Luego, aumentar a[i] en 1.
Si no existe tal i, se ignora este paso.

Después de cada iteración, La Palanca verificará si el paso 1 fue ignorado.
Si lo fue, terminará sus iteraciones.

Se te dan las dos matrices. Debes encontrar el número de iteraciones que realiza La Palanca.
Se puede demostrar que este número es fijo, independientemente de las elecciones aleatorias que La Palanca haga en cada paso.

Entrada

Cada prueba contiene múltiples casos de prueba.

La primera línea contiene un entero t — el número de casos de prueba — (1 ≤ t ≤ 10^4).
La descripción de los casos de prueba sigue.

En cada caso de prueba:

La primera línea contiene un entero n (1 ≤ n ≤ 10).
La segunda línea contiene n enteros a1, a2, …, an (1 ≤ ai ≤ 10).
La tercera línea contiene n enteros b1, b2, …, bn (1 ≤ bi ≤ 10).

Salida

Para cada caso de prueba, imprime un entero:
el número de iteraciones que realiza La Palanca.

Ejemplo

Entrada

4
2
7 3
5 6
3
3 1 4
3 1 4
1
10
1
6
1 1 4 5 1 4
1 9 1 9 8 1

Salida

Nota

En el primer caso de ejemplo:

Iteración 1: Disminuye a1 en 1 y aumenta a2 en 1.
a pasa de [7, 3] a [6, 4].
Iteración 2: Disminuye a1 en 1 y aumenta a2 en 1.
a pasa de [6, 4] a [5, 5].
Iteración 3: Aumenta a2 en 1.
a pasa de [5, 5] a [5, 6].

Como en la tercera iteración no se pudo disminuir ningún elemento (paso 1 ignorado), el proceso termina.
Por lo tanto, la respuesta es 3.

En el segundo caso de ejemplo, La Palanca no realiza ningún cambio en la primera iteración, por lo que el número de iteraciones es 1.

(Solucionado) Lever

Lo que pude notar es que se resuelve sumando las diferencias de a[i] - b[i] y agregarle 1:

#include<bits/stdc++.h>
using namespace std;

int solve(){
    int n;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    int ans=0;

    for(int i=0;i<n;i++)
        if(a[i]>b[i]) ans+= a[i]-b[i];
    return ans + 1;
}

int main(){
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
        cout<<solve()<<endl;
    return 0;
}

B. Alternating Series

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

Se te da un entero n. Llamaremos bueno a un arreglo a de longitud n si cumple:

Para todo 1 ≤ i < n, se cumple que a[i] ⋅ a[i+1] < 0
(es decir, el producto de elementos adyacentes es negativo).
Para todo subarreglo* con longitud al menos 2, la suma de todos sus elementos es positiva†.

Además, diremos que un arreglo bueno a de longitud n es mejor que otro arreglo bueno b de la misma longitud si:

La secuencia [|a₁|, |a₂|, …, |aₙ|] es lexicográficamente menor‡ que [|b₁|, |b₂|, …, |bₙ|].
Aquí |z| denota el valor absoluto del entero z.

Tu tarea es imprimir un arreglo bueno de longitud n tal que sea mejor que cualquier otro arreglo bueno de longitud n.

* Un arreglo c es un subarreglo de un arreglo d si puede obtenerse eliminando varios (posiblemente ninguno o todos) elementos del principio y varios (posiblemente ninguno o todos) elementos del final.

† Un entero x es positivo si x > 0.

‡ Una secuencia a es lexicográficamente menor que una secuencia b si y solo si se cumple una de las siguientes condiciones:

a es un prefijo de b, pero a ≠ b; o
En la primera posición donde a y b difieren, la secuencia a tiene un elemento menor que el elemento correspondiente en b.

Entrada

La primera línea contiene un entero t (1 ≤ t ≤ 500) — el número de casos de prueba.
Cada caso de prueba contiene una línea con un entero n (2 ≤ n ≤ 2·10⁵) — la longitud del arreglo.

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

Salida

Para cada caso de prueba, imprime n enteros a₁, a₂, …, aₙ (−10⁹ ≤ aᵢ ≤ 10⁹), los elementos del arreglo, en una nueva línea.

Ejemplo

Entrada

2
2
3

Salida

-1 2
-1 3 -1

Nota

En el primer caso de ejemplo:

a₁ ⋅ a₂ = −2 < 0 y a₁ + a₂ = 1 > 0, por lo que cumple las dos condiciones.
Además, se puede demostrar que el arreglo correspondiente b = [1, 2] es mejor que cualquier otro arreglo bueno de longitud 2.

C. Make it Equal

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

Se te dan dos multiconjuntos S y T de tamaño n y un entero positivo k.
Puedes realizar la siguiente operación cualquier número de veces (incluyendo cero) sobre S:

Selecciona un elemento x en S y elimina una ocurrencia de x en S.
Luego, inserta en S uno de los siguientes valores:
x + k
|x − k| (valor absoluto de x − k).

El objetivo es determinar si es posible transformar S en T.
Dos multiconjuntos S y T son iguales si cada elemento aparece el mismo número de veces en ambos.

Entrada

Cada prueba contiene múltiples casos de prueba.

La primera línea contiene un entero t (1 ≤ t ≤ 10⁴) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros n y k (1 ≤ n ≤ 2·10⁵, 1 ≤ k ≤ 10⁹):
el tamaño de S y la constante k, respectivamente.
La segunda línea contiene n enteros S₁, S₂, …, Sₙ (0 ≤ Sᵢ ≤ 10⁹) — los elementos de S.
La tercera línea contiene n enteros T₁, T₂, …, Tₙ (0 ≤ Tᵢ ≤ 10⁹) — los elementos de T.

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

Salida

Para cada caso de prueba, imprime "YES" si es posible hacer que S sea igual a T, y "NO" en caso contrario.

La respuesta puede imprimirse en cualquier combinación de mayúsculas y minúsculas. Por ejemplo: "yEs", "yes", "Yes" y "YES" se considerarán respuestas positivas.

Ejemplo

Entrada

Salida

YES
YES
YES
NO
NO

Nota

En el primer caso, podemos eliminar el 1 de S e insertar |1 − k| = |1 − 3| = 2, haciendo que S sea igual a T.
En el segundo caso, podemos eliminar el 4 de S e insertar 4 + k = 4 + 8 = 12, haciendo que S sea igual a T.
En el último caso, se puede demostrar que es imposible hacer que S sea igual a T.

D. Alboris Contractio

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

Kagari se está preparando para archivar un árbol, y sabe que el costo de hacerlo dependerá de su diámetro∗.
Para reducir el gasto, su objetivo es disminuir el diámetro tanto como sea posible primero.
Ella puede realizar la siguiente operación en el árbol:

Elige dos vértices s y t.
Sea la secuencia de vértices en el camino simple† de s a t: v₀, v₁, …, vₖ, donde v₀ = s y vₖ = t.
Elimina todas las aristas a lo largo del camino, es decir, (v₀, v₁), (v₁, v₂), …, (vₖ₋₁, vₖ).
Conecta los vértices v₁, v₂, …, vₖ directamente a v₀, es decir, añade las aristas (v₀, v₁), (v₀, v₂), …, (v₀, vₖ).

Se puede demostrar que el grafo sigue siendo un árbol después de la operación.

Ayúdala a determinar el número mínimo de operaciones necesarias para lograr el diámetro mínimo.

∗ El diámetro de un árbol es la mayor distancia posible entre cualquier par de vértices.
La distancia se mide como el número de aristas en el camino simple único que los conecta.

† Un camino simple es aquel que no visita ningún vértice más de una vez. En un árbol, siempre existe un único camino simple entre dos vértices.

Entrada

Cada prueba contiene múltiples casos de prueba.
La primera línea contiene un entero t (1 ≤ t ≤ 10⁴), el número de casos de prueba.

La descripción de cada caso de prueba es la siguiente:

La primera línea de cada caso de prueba contiene un entero n (2 ≤ n ≤ 2·10⁵), el número de vértices del árbol.
Las siguientes n − 1 líneas describen las aristas. Cada línea contiene dos enteros u y v (1 ≤ u, v ≤ n, u ≠ v), que indican que existe una arista entre u y v.

Se garantiza que los bordes forman un árbol.
También se garantiza que la suma total de n en todos los casos no excede 2·10⁵.

Salida

Para cada caso de prueba, imprime un entero: el mínimo número de operaciones para minimizar el diámetro.

Ejemplo

Entrada

Salida

Nota

En el primer caso, el diámetro inicial es 3.
Kagari puede elegir s = 3 y t = 4 y realizar:

Eliminar (3,1), (1,2) y (2,4).
Añadir (3,1), (3,2) y (3,4).

El diámetro se reduce a 2, que es el mínimo posible.

En el segundo caso, el diámetro es 1, que ya es el mínimo, por lo que no es necesario hacer operaciones.

E. Adjacent XOR

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

Se te da un arreglo a de longitud n.
Para cada índice i tal que 1 ≤ i < n, puedes realizar la siguiente operación como máximo una vez:

a[i] := a[i] ⊕ a[i+1]

donde ⊕ denota la operación XOR bit a bit.

Puedes elegir los índices y realizar las operaciones en cualquier orden secuencial.

Dado otro arreglo b de longitud n, determina si es posible transformar a en b.

Entrada

Cada prueba contiene múltiples casos de prueba.
La primera línea contiene un entero t (1 ≤ t ≤ 10⁴), el número de casos de prueba.

La descripción de cada caso de prueba es la siguiente:

La primera línea contiene un entero n (2 ≤ n ≤ 2·10⁵).
La segunda línea contiene n enteros a₁, a₂, …, aₙ (0 ≤ aᵢ < 2³⁰).
La tercera línea contiene n enteros b₁, b₂, …, bₙ (0 ≤ bᵢ < 2³⁰).

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

Salida

Para cada caso de prueba, imprime "YES" si es posible transformar a en b; de lo contrario, imprime "NO".
La respuesta puede imprimirse en cualquier combinación de mayúsculas y minúsculas.

Ejemplo

Entrada

7
5
1 2 3 4 5
3 2 7 1 5
3
0 0 1
1 0 1
3
0 0 1
0 0 0
4
0 0 1 2
1 3 3 2
6
1 1 4 5 1 4
0 5 4 5 5 4
3
0 1 2
2 3 2
2
10 10
11 10

Salida

YES
NO
NO
NO
YES
NO
NO

Nota

En el primer caso, puedes realizar las operaciones en el siguiente orden:

Elige i = 3 y asigna a₃ := a₃ ⊕ a₄ = 7, entonces a = [1, 2, 7, 4, 5].
Elige i = 4 y asigna a₄ := a₄ ⊕ a₅ = 1, entonces a = [1, 2, 7, 1, 5].
Elige i = 1 y asigna a₁ := a₁ ⊕ a₂ = 3, entonces a = [3, 2, 7, 1, 5].

F. Unjust Binary Life

Yuri tiene dos cadenas binarias a y b, ambas de longitud n.
Estas dos cadenas definen dinámicamente una cuadrícula de tamaño n × n.
Sea (i, j) la celda en la fila i y columna j.
El valor inicial de la celda (i, j) es a_i ⊕ b_j, donde ⊕ denota la operación XOR bit a bit.

El viaje de Yuri siempre comienza en la celda (1, 1).
Desde una celda (i, j), ella solo puede moverse hacia abajo (i+1, j) o hacia la derecha (i, j+1).
Su viaje es posible si existe un camino válido tal que todas las celdas en el recorrido (incluida (1, 1)) tengan valor 0.

Antes de partir, ella puede realizar la siguiente operación cualquier cantidad de veces:

Elegir un índice 1 ≤ i ≤ n y cambiar el valor de a_i o b_i (un 0 se convierte en 1 y un 1 se convierte en 0).
La cuadrícula cambiará en consecuencia.

Sea f(x, y) el mínimo número de operaciones necesarias para que Yuri pueda llegar a la celda (x, y).
Debes determinar la suma de f(x, y) para todos 1 ≤ x, y ≤ n.

Nota: Cada uno de estos n² casos es independiente, lo que significa que debes asumir que la cuadrícula está en su estado original en cada caso (es decir, no se realizan operaciones acumuladas).

Entrada

Cada prueba contiene múltiples casos de prueba.
La primera línea contiene un entero t — el número de casos de prueba (1 ≤ t ≤ 10⁴).

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 a (|a| = n, a_i ∈ {0, 1}). - La tercera línea contiene una cadena binaria b (|b| = n, b_i ∈ {0, 1}).

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

Salida

Para cada caso de prueba, imprime un entero: la suma de operaciones mínimas sobre todas las celdas posibles.

Ejemplo

Entrada

Salida

5
4
24

Explicación En el primer caso, la cuadrícula 2×2 es:

Inicialmente, Yuri no puede llegar a ninguna celda.

Si cambia a₁, la cuadrícula se convierte en:

y puede llegar a (1,1) y (1,2).

Si cambia b₁, la cuadrícula se convierte en:

y puede llegar a (1,1) y (2,1).

Para llegar a (2,2), es necesario realizar al menos dos operaciones.
Por ejemplo, puede cambiar a₁ y a₂ para obtener:

Por lo tanto, la respuesta es 1 + 1 + 1 + 2 = 5.

G. Wafu!

Para ayudar a mejorar sus habilidades matemáticas, a Kudryavka se le da un conjunto S que consiste en n enteros positivos distintos.

Inicialmente, su puntaje es 1. Ella puede realizar un número arbitrario de las siguientes operaciones sobre el conjunto, siempre que no esté vacío:

Sea m el valor mínimo de S.
Multiplica su puntaje por m.
Elimina m de S.
Para cada entero i tal que 1 ≤ i < m, añade i al conjunto S. Se puede demostrar que en este paso no se añaden duplicados.

Ella es adicta a realizar operaciones, pero después de k operaciones, se da cuenta de que olvidó su puntaje. Ayúdala a determinar su puntaje, módulo 10^9 + 7.

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^4).
La descripción de los casos de prueba sigue.

En cada caso de prueba: - La primera línea contiene dos enteros n y k (1 ≤ n ≤ 2·10^5, 1 ≤ k ≤ 10^9).
- La segunda línea contiene n enteros s1, s2, …, sn (1 ≤ si ≤ 10^9, si ≠ sj) — los elementos del conjunto inicial S.

Se garantiza que S no está vacío antes de cada una de las k operaciones.
Se garantiza que la suma de n en todos los casos de prueba no excede 2·10^5.

Salida

Para cada caso de prueba, imprime un entero indicando la respuesta módulo 10^9 + 7.

Ejemplo

Entrada

Salida

Nota

Simulemos el proceso en el primer caso:

{1, 3} → eliminar 1 → {3} → añadir 1, 2 → eliminar 3 → {1, 2} → eliminar 1 → {2}

Los valores eliminados son 1, 3 y 1, por lo que el puntaje es:

1 × 3 × 1 = 3

En el segundo caso, el puntaje es:

1 × 4 × 1 × 2 × 1 × 3 = 24

H. Sea, You & copriMe

Umi tiene un arreglo a de longitud n, cuyos elementos son enteros entre 1 y m. A ella le encantan los números coprimos y quiere encontrar cuatro índices distintos p, q, r, s (1 ≤ p, q, r, s ≤ n), tales que:

gcd(a_p, a_q) = 1
gcd(a_r, a_s) = 1

Si existen múltiples soluciones, puedes imprimir cualquiera de ellas.

gcd(x, y) denota el máximo común divisor (MCD) de los enteros x y y.

Entrada

Cada prueba contiene múltiples casos de prueba.
La primera línea contiene un entero t (1 ≤ t ≤ 10⁴) — el número de casos de prueba.

La descripción de cada caso es la siguiente:

La primera línea contiene dos enteros n y m (4 ≤ n ≤ 2·10⁵, 1 ≤ m ≤ 10⁶).
La segunda línea contiene n enteros a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ m).

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

Salida

Para cada caso de prueba:

Si no existe tal conjunto de cuatro índices distintos, imprime un solo entero 0.
En caso contrario, imprime cuatro enteros distintos p, q, r, s (1 ≤ p, q, r, s ≤ n) que cumplan las condiciones.

Si existen múltiples soluciones, puedes imprimir cualquiera.

Ejemplo

Entrada

5
4 15
4 7 9 15
4 10
1 2 4 8
5 15
6 10 11 12 15
5 15
6 10 11 14 15
6 10000
30 238 627 1001 1495 7429

Salida

Nota
En el primer caso, gcd(a₁, a₃) = gcd(4, 9) = 1 y gcd(a₂, a₄) = gcd(7, 15) = 1.
En el segundo caso, puede demostrarse que no existe tal cuádrupla.

| DJC | Programación Competitiva | Codeforces |

Keys	Action
`?`	Open this help
`n`	Next page
`p`	Previous page
`s`	Search