Soluciones OICV 2024

Table of Contents

Puedes encontrar el código de estas soluciones en mi repositorio de GitHub.

En este artículo ofreceremos soluciones orientativas y explicaciones sobre los cinco problemas de la III Olimpiada Informática de la Comunidad Valenciana, celebrada en Alicante y Valencia a finales del pasado mes de enero. Enhorabuena a todos los participantes, y si todavía no has participado, ¡te animo a que lo hagas!

Aquí tienes un enlace a los enunciados de los ejercicios de este año.

Concierto
#

En este problema se nos ofrece una lista de doce grupos y artistas. En cada caso de prueba tenemos un entero $n$ , que representa el número de grupos (a partir de ahora llamaremos grupos a todos los elementos de la lista) diferentes que deben tocar en un concierto, otro entero $s$ que indica el máximo número de grupos que podemos saltar en la lista para seleccionar el siguiente grupo, y uno de los nombres de la lista, indicando el grupo que tocará primero y, por tanto, desde el que comenzará la selección. Por último, la selección debe terminar en el mismo grupo en el que ha empezado, y al exceder el final de la lista, volvemos al principio como si se tratara de una prolongación de la misma.

En resumen, las condiciones para la selección son las siguientes:

Seleccionamos un total de $n + 1$ grupos (el último grupo en tocar debe ser el mismo que el primero, y por tanto, se debe realizar una iteración completa de la lista).
Para cada grupo saltamos como mínimo una posición (un grupo no puede tocar dos veces, excepto el que toca primero), y como máximo $s$ . Así, para $s = 2$ , no podemos saltar desde “Dorian” hasta “Love of Lesbian”, ya que estaría fuera de rango.
Los grupos se deben seleccionar en el mismo orden de la lista, y no se puede seleccionar hacia atrás: “The Killers” no puede tocar después de “Vetusta Morla” a no ser que el valor de $s$ permita seleccionarlo hacia delante.

Finalmente, como salida tenemos que mostrar el número de combinaciones posibles para seleccionar los grupos teniendo en cuenta las condiciones anteriores.

Solución
#

En primer lugar, nos damos cuenta de que los nombres de los grupos son completamente innecesarios para el cálculo de las combinaciones. De este modo, podemos reformular el problema como sigue:

Dados dos enteros $n$ y $s$ , hallar el número de combinaciones de $n$ números enteros $a_{1}, a_{2}, \dots, a_{n}$ tal que $1 \leq a_{i} \leq s$ y cuya suma sea $a_{1} + a_{2} + \dots + a_{n} = 12$ .

Este problema se puede resolver idealmente mediante una adaptación del Principio de Inclusión-Exclusión y la técnica de barras y estrellas. Por ejemplo, se puede obtener el número de combinaciones de $n$ números $x_{1}, x_{2}, \dots, x_{n}$ con $0 \leq x_{i} \leq s$ cuya suma sea $k$ mediante la expresión:

\sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) (\binom{k + n - 1 - (s + 1) i}{n - 1})

En nuestro caso, la expresión requiere una adaptación debido a que $1 \leq x_{i} \leq s$ . Sin embargo, las restricciones del problema son tan pequeñas que resulta más sencillo implementar una solución recursiva que genere todas las permutaciones posibles, y que de entre ellas seleccione aquellas cuya suma sea 12.

Código
#

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

int solve(int sum, int pos, int n, int s) {
    int res = 0;

    if (pos < n) {
        for (int i = 1; i <= s; i++) {
            // Para el elemento en la posición 'pos', probamos todos los valores
            // entre 1 y s, y llamamos a la función sobre la posición siguiente.
            if (sum + i <= 12) {
                res += solve(sum+i, pos+1, n, s);
            }
        }
    } else if (sum == 12) res = 1; // Caso base

    return res;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string grupo;
    int n, s;
    
    // Aunque no lo vayamos a usar, tenemos que leer el nombre del grupo
    // de la entrada.
    getline(cin, grupo); // El nombre del grupo pueden ser varias palabras!
    cin >> n >> s;

    if (n * s == 12) {
        // Por ejemplo, n = 3 y s = 4. En estos casos solo hay una
        // configuración posible.
        cout << "1\n";
    } else {
        cout << solve(0, 0, n, s) << '\n';
    }

    return 0;
}

Con corazón
#

Este problema consiste en realizar la media móvil de los elementos de un vector. Para el elemento en la posición $i$ , $x_{i}$ , el valor de su media móvil se define como:

M_{k} (i) = \frac{1}{k} \cdot \sum_{j = i - \frac{k - 1}{2}}^{i + \frac{k - 1}{2}} x_{j}

donde $k$ es una constante cuyo valor indica la anchura de la ventana de elementos alrededor de $x_{i}$ sobre la que calcular la media.

La dificultad principal del problema consiste en evitar exceder el rango del vector, y es por ello que en el enunciado se definen dos modos de operación, $O p$ , cuyo valor se define en la entrada de cada caso de prueba:

Si $O p = 0$ , todos aquellos elementos con los que se excedería el rango del vector al calcular la media móvil (debido a que se encuentran a menos de $\frac{k - 1}{2}$ elementos de distancia de uno de los extremos) mantienen su valor.
Si $O p = 1$ , para calcular la media de dichos elementos, el elemento que esté en el extremo del vector (el último o el primero, dependiendo del caso) se replicará tantas veces como sea necesario para rellenar las posiciones que faltan.

Cabe mencionar que $k$ siempre será impar, por lo que el resultado de $\frac{k - 1}{2}$ será un entero. También es necesario recordar que el resultado de cada media se debe redondear al entero más cercano, por lo que es importante realizar la división en coma flotante antes de realizar el redondeo.

En la salida se debe mostrar los elementos del vector suavizado, es decir, el vector original tras calcular la media móvil.

Solución
#

Iteramos elemento a elemento sobre el vector original calculando la media como se ha descrito en la fórmula anterior, y acorde a las condiciones del modo de operación seleccionado.

Código
#

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int op, n, k, offset;
    cin >> op >> n >> k;
    offset = (k-1)/2; // definimos por comodidad

    vector<int> v(n);
    vector<int> suavizado(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    for (int i = 0; i < n; i++) {
        if (op == 0 && (i < offset || i > n - 1 - offset)) {
            // Cuando op == 0, los elementos cuya media móvil excedería el
            // rango del vector mantienen su valor.
            suavizado[i] = v[i];
        } else {
            // En el resto de casos, realizamos la suma de los elementos de la
            // media teniendo cuidado de no salirnos del vector.
            for (int j = max(0, i-offset); j <= min(n-1, i+offset); j++) {
                suavizado[i] += v[j];
            }

            // Replicación de los elementos de los extremos
            if (i-offset < 0) suavizado[i] += (offset-i) * v[0];
            if (i+offset >= n) suavizado[i] += (i+offset-(n-1)) * v[n-1];

            // Es importante convertir uno de los términos de la división a
            // coma flotante para evitar truncamientos.
            suavizado[i] = round(suavizado[i] / (double)k);
        }

        cout << suavizado[i] << ' ';
    }

    cout << '\n';
    return 0;
}

Exposición de pinturas
#

Recibimos una serie de pares de puntos definidos por sus coordenadas cartesianas, que se traducen en forma de rectángulos sobre el plano. Teniendo en cuenta que estos rectángulos se pueden superponer, debemos calcular el perímetro de la figura compuesta por todos los rectángulos.

El planteamiento de este problema es muy similar al del cuarto problema de la IOI 1998, “Pictures”, pero con unas restricciones mucho más bajas en nuestro caso.

Solución
#

Tal y como se describe en este editorial del problema de la IOI comentado anteriormente, se puede utilizar un algoritmo sweep line con un segment tree para obtener la solución más eficiente, de complejidad $O (n \log n)$ .

No obstante, como nuevamente las restricciones del problema son tan bajas (como máximo puede haber diez rectángulos en cada caso), resulta más sencillo y rápido de implementar una solución cuadrática que realice la suma de los perímetros de todos los rectángulos y que después reste la suma de los perímetros de sus intersecciones:

{perim}_{total} = \sum_{i = 1}^{n} perim (R_{i}) - \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} perim (R_{i} \cap R_{j})

Nota: $n$ indica la cantidad total de rectángulos: $R_{1}, R_{2}, \dots, R_{n}$ .

Código
#

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define x first
#define y second
using namespace std;

typedef pair<int, int> pi;
typedef pair<pi, pi> ppi;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, perim = 0;
    ppi intersect;
    cin >> n;

    vector<ppi> squares(n);

    for (int i = 0; i < n; i++) {
        cin >> squares[i].first.x >> squares[i].first.y;
        cin >> squares[i].second.x >> squares[i].second.y;
    }

    // El perímetro total de la figura será la suma de los perímetros de todos
    // los rectángulos menos la suma de los perímetros de todas las
    // intersecciones entre rectángulos. Como 0 <= n <= 10, es perfectamente
    // viable una solución O(n2).

    for (int i = 0; i < n; i++) {
        // Sumamos al perímetro total el perímetro del rectángulo actual, R_i.
        perim += 2 * (
            (squares[i].second.x - squares[i].first.x) +
            (squares[i].second.y - squares[i].first.y));
        
        // Restamos el perímetro de la intesección de R_i con el resto de
        // rectángulos R_j.
        for (int j = n-1; j > i; --j) {
            intersect.first.x = max(squares[i].first.x, squares[j].first.x);
            intersect.first.y = max(squares[i].first.y, squares[j].first.y);
            intersect.second.x = min(squares[i].second.x, squares[j].second.x);
            intersect.second.y = min(squares[i].second.y, squares[j].second.y);

            if (intersect.first.x < intersect.second.x &&
                intersect.first.y < intersect.second.y) {
                // Los rectángulos se intersectan
                perim -= 2 * (
                    (intersect.second.x - intersect.first.x) +
                    (intersect.second.y - intersect.first.y));
            }
        }
    }

    cout << perim << '\n';
    return 0;
}

Laberinto aritmético
#

El cuarto problema consiste en atravesar un laberinto en la dirección indicada por las flechas y realizando una serie de operaciones aritméticas en el orden en el que van apareciendo. Se comienza en la posición de una flecha, que se indica en la entrada del caso de prueba, y se termina una vez se alcanza una casilla con el carácter @, o bien si no se puede llegar.

Se debe seguir la dirección de la última flecha encontrada hasta que pasemos por encima de una nueva.

Hay varios casos en los que el laberinto no tiene solución, y en que, por tanto, se debe mostrar el mensaje SIN SOLUCION:

Si al seguir la dirección de las flechas nos salimos del tablero.
Si no podemos llegar a la casilla final. Este caso se puede deducir si pasamos dos veces por la misma casilla y en la misma dirección (indicando que hay un ciclo).
Si la secuencia de operaciones es incorrecta. La secuencia de operaciones debe alternar dígitos (1-9) y operadores (+-*/=), comenzando siempre por un dígito y acabando por un igual (=). Por ejemplo, las secuencias 4+3-1/2*6= y 4-1+6= son válidas, mientras que *4+2/3=, 3+2=1 y 11*3= no lo son.

En el caso de que la secuencia sí sea correcta, se debe mostrar el resultado de la secuencia.

Solución
#

Básicamente, recorremos el tablero siguiendo las direcciones y calculando las operaciones hasta que, o bien entremos en conflicto con una de las condiciones anteriores, o bien lleguemos a la casilla final. En mi caso, he preferido primero recorrer el tablero almacenando la secuencia de operaciones en una cadena para evaluarla más tarde. Una vez comprobamos que sí se puede alcanzar la casilla final, iteramos sobre la secuencia para evaluar su validez y calcular el resultado.

Código
#

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define x first
#define y second
using namespace std;

typedef pair<int, int> pi;
typedef enum { NADA = 0, ARRIBA, ABAJO, IZQUIERDA, DERECHA } Direccion;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, res;
    pi pos;
    Direccion dirActual;
    string cad = "";

    cin >> n >> m >> pos.y >> pos.x;

    vector<string> v(n);

    // La matriz dirs almacena la dirección en la que hemos atravesado cada
    // casilla por última vez, para comprobar si existen ciclos.
    vector<vector<Direccion>> dirs(n, vector<Direccion>(m, NADA));

    for (int i = 0; i < n; i++) cin >> v[i];

    while (v[pos.y][pos.x] != '@') {
        if (dirs[pos.y][pos.x] == dirActual) {
            cout << "SIN SOLUCION\n"; // Existe un ciclo
            return 0;
        }

        dirs[pos.y][pos.x] = dirActual;

        switch (v[pos.y][pos.x]) {
            case 'v':
                dirActual = ABAJO;
                break;
            case '^':
                dirActual = ARRIBA;
                break;
            case '<':
                dirActual = IZQUIERDA;
                break;
            case '>':
                dirActual = DERECHA;
                break;
            case '0':
            case '@':
                break;
            default:
                cad += v[pos.y][pos.x];
        }

        switch (dirActual) {
            case ABAJO: pos.y++; break;
            case ARRIBA: pos.y--; break;
            case IZQUIERDA: pos.x--; break;
            case DERECHA: pos.x++; break;
            case NADA:
            default:
                cout << "SIN SOLUCION\n"; // Por si acaso
                return 0;
        }

        if (pos.y < 0 || pos.y >= n || pos.x < 0 || pos.x >= m) {
            cout << "SIN SOLUCION\n"; // Fuera de límites
            return 0;
        }
    }

    if (cad[0] < '1' || cad[0] > '9') {
        cout << "SIN SOLUCION\n"; // Secuencia no comienza por un dígito
        return 0;
    }

    res = cad[0] - '0';

    for (int i = 1; i < cad.length(); i++) {
        if ((i % 2 == 0 && (cad[i] == '+' || cad[i] == '-' || cad[i] == '*' || cad[i] == '/' || cad[i] == '=')) ||
            (i % 2 == 1 && cad[i] >= '1' && cad[i] <= '9')) {
            // No se cumple alternancia de dígitos y operadores
            cout << "SIN SOLUCION\n";
            return 0;
        }

        if (i % 2 == 0) {
            switch (cad[i-1]) {
                case '+':
                    res += cad[i] - '0';
                    break;
                case '-':
                    res -= cad[i] - '0';
                    break;
                case '*':
                    res *= cad[i] - '0';
                    break;
                case '/':
                    res /= cad[i] - '0';
                    break;
                case '=':
                    if (i < cad.length()-1) break;
                default:
                    cout << "SIN SOLUCION\n"; // Por si acaso
                    return 0;
            }
        }
    }

    if (cad[cad.length()-1] != '=') {
        cout << "SIN SOLUCION\n"; // Secuencia no termina por un igual
    } else {
        cout << res << '\n';
    }
    
    return 0;
}

Primos
#

Si $k = 0$ , simplemente tenemos que decir si un número $n$ es primo o no. Si $k > 0$ , debemos escribir los $k$ primos estrictamente mayores que $n$ .

Solución
#

Para resolver este ejercicio nos puede servir de ayuda escribir una función auxiliar isPrime, que devuelva true si el número pasado por parámetro es primo, y false en el caso contrario.

Para una menor complejidad temporal, podríamos generar todos los números primos en un intervalo arbitrario $[1, MAXN]$ , teniendo en cuenta que en el peor de los casos se nos puede pedir mostrar los 100 números primos posteriores a 10000 ( $k = 100, n = 10000$ ). Para generar los primos, podemos utilizar una criba como la de Eratóstenes ( $O (n \log \log n)$ ) o la de Atkin ( $O (n / \log \log n)$ ), para después comprobar si un número es primo o no con complejidades incluso cercanas a $O (1)$ .

No obstante, por mera sencillez ilustrativa utilizaremos una función isPrime como se ha indicado anteriormente.

Código
#

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n % 2 == 0) return n == 2;

    // Solo necesitamos comprobar los impares
    for (int i = 3; i*i <= n; i += 2) {
        if (n % i == 0) return false;
    }

    return true;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t, n, k, count;
    cin >> t;

    for (; t > 0; --t) {
        cin >> n >> k;

        if (k == 0)
            cout << ((isPrime(n) ? "SI\n" : "NO\n"));
        else {
            count = 0;
            if (n < 2) { // Con esto nos ahorramos comprobar los pares
                cout << "2 ";
                count++;
            }

            for (int i = (n+1) + ((n+2) % 2); count < k; i += 2) {
                if (isPrime(i)) {
                    cout << i << ' ';
                    count++;
                }
            }

            cout << '\n';
        }
    }

    return 0;
}

Author

Alberto Navalón

Computer Science student at the University of Alicante. Google Code-In Grand Prize Winner 2018, competitive programmer and language learner, now playing with NLP.

Concierto #

Solución #

Código #

Con corazón #

Solución #

Código #

Exposición de pinturas #

Solución #

Código #

Laberinto aritmético #

Solución #

Código #

Primos #

Solución #

Código #

Concierto
#

Solución
#

Código
#

Con corazón
#

Solución
#

Código
#

Exposición de pinturas
#

Solución
#

Código
#

Laberinto aritmético
#

Solución
#

Código
#

Primos
#

Solución
#

Código
#