XXIX Spain Olympiad in Informatics, Online Qualifier
A. Length of the Path
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Your friend has been hiking in Cabezón de cuadrícula (a small village); there, all the paths go from north to south or from east to west.

Your friend says he has walked a lot until he returned to where he started, but he doesn't know exactly how much. After a moment, he remembers that he has a notebook where he has noted down the path he has taken.

The description has the following format:

  • Direction: N (North), S (South), E (East), or O (West)
  • Distance: A positive integer amount in meters.

In the notebook, there are $$$n$$$ descriptions.

Unfortunately, some of the distances in the notebook have been lost due to the notebook getting wet in the rain.

Your friend asks you to find out what the minimum possible distance he has traveled is and what the maximum possible distance he has traveled is.

Input

The first line contains an integer $$$T$$$, the number of cases.

Following are $$$T$$$ cases in the following format:

The first line contains an integer $$$n$$$.

The next $$$n$$$ lines contain the descriptions in order. Each description consists of two elements separated by a space:

  • An uppercase letter $$$d_i$$$ representing the direction (explained in the statement).
  • An integer $$$l_i$$$ representing the distance traveled in that direction; if the number is illegible, it will be $$$-1$$$.
Output

The output consists of two integers separated by a space.

If the notes in the notebook cannot correspond to any path, print "-1 -1" (without quotes).

Otherwise, print the minimum and maximum distances separated by a space.

If the duration of the walk is possibly unlimited, print a $$$-1$$$ for the maximum duration.

Scoring
  1. (14 points) $$$n \leq 2$$$.
  2. (10 points) There are no distances erased.
  3. (15 points) At most, there is $$$1$$$ distance erased.
  4. (15 points) At most, there are $$$2$$$ distances erased.
  5. (16 points) Only North and South directions appear.
  6. (30 points) No additional restrictions.
Example
Input
4
2
N 1
S -1
2
N -1
S -1
1
N -1
4
N 1000000000
S 1000000000
N 1000000000
S 1000000000
Output
2 2
2 -1
-1 -1
4000000000 4000000000
Note
  • $$$1 \leq T \leq 10^5$$$
  • $$$1 \leq n \leq 10^5$$$
  • $$$1 \leq l_i \leq 10^9$$$
  • The sum of $$$n$$$ over all cases is less than or equal to $$$10^5$$$.

B. Many Tasks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Berta has a list of $$$n$$$ tasks. The $$$i$$$-th task requires $$$t_i$$$ seconds to be completed. Additionally, each task has a deadline $$$p_i$$$: the $$$i$$$-th task must be completed before more than $$$p_i + t_i$$$ seconds have passed since the start (therefore, it must be started at second $$$p_i$$$ or earlier).

Berta wants to perform the tasks strictly in the order they are written in her list, being able to skip some of them.

Help Berta determine the maximum number of tasks from her list that she can complete.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

Each case begins with a line containing an integer $$$n$$$, the number of tasks. This is followed by $$$n$$$ lines, the $$$i$$$-th of which contains the two integers $$$t_i$$$ and $$$p_i$$$.

Output

For each case, print a line with the maximum number of tasks that can be completed.

Scoring
  1. (39 points) $$$t_i \leq n$$$, $$$p_i \leq n$$$ and the sum of $$$n^3$$$ over all cases is at most $$$10^6$$$.
  2. (15 points) All values of $$$p_i + t_i$$$ are equal: $$$p_1 + t_1 = p_2 + t_2 = \ldots = p_n + t_n$$$.
  3. (16 points) All values of $$$p_i$$$ are equal: $$$p_1 = p_2 = \ldots = p_n$$$.
  4. (30 points) No additional restrictions.
Example
Input
3
5
2 0
1 1
1 1
2 2
3 4
2
10000 100000000
1 9999
10
8 25
5 12
7 10
11 28
3 18
6 32
10 45
5 34
7 28
6 42
Output
4
1
7
Note
  • $$$1 \leq T \leq 10^3$$$.
  • $$$1 \leq n \leq 10^3$$$. The sum of $$$n^2$$$ over all cases is at most $$$10^6$$$.
  • $$$1 \leq t_i \leq 10^6$$$ for all $$$i = 1, \ldots, n$$$.
  • $$$0 \leq p_i \leq 10^9$$$ for all $$$i = 1, \ldots, n$$$.

C. Codificación
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Encodelia quiere enviar un mensaje a Decodelio. El mensaje consiste en una cadena binaria de bits. Por desgracia, la malvada Errorlina interferirá en la comunicación. Errorlina seleccionará aleatoriamente un intervalo de bits contiguos de la cadena enviada por Encodelia y lo invertirá, es decir, cambiará los unos a ceros y los ceros a unos.

Por ejemplo, si Encodelia envía el mensaje 01011001, Errorlina puede seleccionar el intervalo , de forma que Decodelio recibirá el mensaje 01100111.

Ayuda a Encodelia y a Decodelio a comunicarse pese a la interferencia de Errorlina. Tu programa se ejecutará tanto desde el punto de vista de Encodelia como de Decodelio: en el primer caso se te dará el mensaje que Encodelia quiere transmitir y debes imprimir una codificación del mensaje que enviar a Decodelio, y en el segundo recibirás la codificación tras la interferencia de Errorlina y debes recuperar el mensaje original.

Output

Una posible secuencia de ejecuciones sería la siguiente. En la primera ejecución, la entrada es:

ENC 011

Y la salida que imprime el programa es:

01011001

En la segunda ejecución, la entrada es:

DEC 01100111

Nótese que se ha invertido un intervalo, como se ha explicado antes en el enunciado. La salida debería ser:

011

Interaction

Este es un problema de ejecución múltiple. Por cada caso de prueba, tu programa se ejecutará dos veces seguidas de forma independiente.

En la primera ejecución, la entrada consistirá en una línea con la palabra ENC seguida de una cadena binaria, el mensaje que se quiere enviar. La palabra ENC y la cadena binaria están separadas por un espacio. Tu programa debe imprimir una línea con una cadena binaria, la codificación que se desea enviar.

En la segunda ejecución, la entrada consistirá en una línea con la palabra DEC seguida de una cadena binaria, el mensaje codificado recibido. La palabra DEC y la cadena binaria están separadas por un espacio. Tu programa debe imprimir una línea con una cadena binaria correspondiente al mensaje original.

Scoring
  1. (25 puntos) La longitud del mensaje a codificar será de como mucho 10 bits.
  2. (75 puntos) Sin restricciones adicionales.

Adicionalmente, la puntuación que obtienes depende de la longitud del mensaje codificado: para obtener una puntuación completa la longitud debe ser como máximo 2·104 bits y para obtener una puntuación positiva la longitud debe ser como máximo 105 bits. La puntuación de cada subtarea es multiplicada por un multiplicador , donde es la máxima longitud en bits de una de las codificaciones producidas en los casos de esa subtarea. El valor de viene dado por:

Note

La longitud del mensaje a codificar será de como mucho 104 bits.

La longitud de la codificación debe ser de como mucho 105 bits.

Tu programa será probado en un número limitado de casos de prueba. El intervalo de la codificación que se invertirá se seleccionará (pseudo)aleatoriamente de forma independiente en cada caso, con una distribución uniforme sobre todos los intervalos posibles (donde es la longitud de la codificación).

D. Coprime Sums
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a list $$$a = (a_1, \ldots, a_n)$$$ of $$$n$$$ non-negative integers, and you must answer $$$p$$$ queries of the form: given $$$k$$$, print the sum of values of $$$a$$$ at positions that are coprime to $$$k$$$. In other words, return the sum of values of $$$a_i$$$ for those $$$i$$$ such that $$$\text{gcd}(k, i) = 1$$$, where $$$\text{gcd}(k, i)$$$ is the greatest common divisor of $$$k$$$ and $$$i$$$.

Input

The first line of the input contains the number of cases $$$T$$$.

Each case starts with a line of input with two integers $$$n$$$ and $$$p$$$, the size of $$$a$$$ and the number of queries.

The following line of each case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

The next line of each case contains $$$p$$$ integers, the values of $$$k$$$ for each of the queries.

Output

For each case, you must print a line with $$$p$$$ integers, the answers to each of the queries.

Scoring
  1. (13 points) The sum of $$$n$$$ and the sum of $$$p$$$ across all cases are at most $$$10^3$$$.
  2. (24 points) It is guaranteed that $$$a_i$$$ will be non-zero only if $$$i$$$ is prime.
  3. (35 points) $$$k \le 1000$$$, $$$T \le 10$$$, $$$a_i = 1$$$ for all $$$i$$$.
  4. (28 points) No additional restrictions.
Example
Input
3
4 4
1 1 1 1
1 2 3 4
10 4
3 9 2 3 4 5 5 0 2 1
7 1 3 2
8 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1
Output
4 2 3 2 
29 34 25 16 
8000000000
Note
  • $$$1 \le T \le 10^5$$$.
  • $$$1 \le n, p \le 2 \cdot 10^5$$$. The sum of $$$n$$$ and the sum of $$$p$$$ across all cases are at most $$$2 \cdot 10^5$$$.
  • $$$0 \le a_i \le 10^9$$$.
  • $$$k \le n$$$.

E. Pizarra
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Te has perdido por el instituto, y después de dar muchas vueltas acabas en una clase vacía, que contiene solamente un cartel y una pizarra con los números enteros a1, ..., an escritos en ella. En el cartel hay una lista de precios:

  • Por l euros, puedes borrar un número x de la pizarra y escribir x - 1.
  • Por r euros, puedes borrar un número x de la pizarra y escribir x + 1.
  • Gratuitamente, puedes duplicar un número de la pizarra (es decir, escribir una copia sin borrar el original).
Tienes unos cuantos números favoritos b1, ..., bm, y no puedes aguantar la irresistible tentación de conseguir que todos tus números favoritos aparezcan en la pizarra. Calcula el mínimo dinero que necesitarías para cumplir tu objetivo.
Input

La primera línea contiene un entero T, el número de casos. Siguen T casos, cada uno con 3 líneas:

  • La primera línea contiene n, m, l y r.
  • La segunda línea contiene los n enteros a1, ..., an escritos en la pizarra.
  • La tercera línea contiene tus m números favoritos b1, ..., bm.
Output

Para cada caso imprime en una línea un solo entero, el mínimo dinero que necesitas para que todos tus números favoritos aparezcan en la pizarra.

Scoring
  1. (7 puntos) m = 1.
  2. (12 puntos) n = 1.
  3. (6 puntos) l = 0.
  4. (16 puntos) l = 1, r = 106.
  5. (24 puntos) La suma de n sobre todos los casos es como mucho 1000. La suma de m sobre todos los casos es como mucho 1000.
  6. (24 puntos) l = r = 1.
  7. (11 puntos) Sin restricciones adicionales.
Example
Input
1
4 3 1 2
1 7 1 10
2 5 8
Output
6
Note
  • 1 ≤ T ≤ 105
  • La suma de n sobre todos los casos es como mucho 2·105
  • La suma de m sobre todos los casos es como mucho 2·105
  • 0 ≤ l, r ≤ 106
  • 1 ≤ ai ≤ 106 para todo 1 ≤ i ≤ n
  • 1 ≤ bi ≤ 106 para todo 1 ≤ i ≤ m
  • El array b no contiene números repetidos.

F. Balloons
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tomorrow is Manuel's birthday, and you are preparing a surprise party for him. You are in charge of the decorations, but you are too lazy to go to the store. Fortunately, you already have a row of balloons left over from another birthday. To make it less obvious that they are the same, you plan to remove the balloons of a certain color and keep the rest. You have $$$n$$$ balloons arranged in a row, each of one of $$$2 \le k \le n$$$ colors. The color of the $$$i$$$-th balloon will be $$$1 \le a_i \le k$$$.

We will choose a color $$$c$$$ and pop all the balloons of that color. After popping them, there will be a new row of balloons that contains all the balloons that were not of color $$$c$$$, in the same order they were before the popping.

Manuel really likes consecutive segments of balloons of the same color. Therefore, you are interested in knowing for each color $$$c$$$ to pop what the maximum number of consecutive balloons of any color will remain after popping those of color $$$c$$$.

Input

The first line contains an integer $$$T$$$, the number of cases. There are $$$T$$$ cases, each with $$$2$$$ lines:

  • The first line contains $$$n$$$ and $$$k$$$, the number of balloons and the number of colors.
  • The second line contains the $$$n$$$ colors $$$a_1,\ldots,a_n$$$ of the balloons, in the order they are in the row.
Output

For each case, you must print $$$k$$$ numbers in one line: The $$$i$$$-th is the answer when you remove color $$$i$$$.

Scoring
  1. (6 points) $$$k=2$$$.
  2. (10 points) The sum of $$$n$$$ over all cases is at most $$$2000$$$.
  3. (17 points) The balloons of each color form at most $$$2$$$ segments.
  4. (36 points) There are no two consecutive balloons of the same color.
  5. (31 points) No additional restrictions.
Example
Input
1
7 3
1 1 2 1 2 3 1
Output
2 3 2
Note
  • $$$1 \le T \le 10^5$$$
  • $$$2 \le k \le n \le 2 \cdot 10^5$$$
  • The sum of $$$n$$$ over all cases is at most $$$2 \cdot 10^5$$$
  • There is at least one balloon of each color