Problemas del Simulacro

A continuación se presentan los problemas con sus restricciones y soluciones.

A. Título del Problema A

Puntuación: 100 | Límite de tiempo: 1000ms | Puntos de prueba: 10

Idea de la Solución:

La dificultad principal radica en la interpretaicón del enunciado. En esencia, si entre las 14 cartas no hay ninguna de las siguientes: Ipin, Chupin, Isou, Chusou, Iwan, Chuwan, Ton, Nan, Sha, Pei, Haku, Hatsu, Chun, entonces la mano es una mano "Duan Yao Jiu". Si alguna de estas cartas está presente, la mano no es válida. La implementación es directa.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<string> cartasInvalidas = {"Ipin", "Chupin", "Isou", "Chusou", "Iwan", "Chuwan", "Ton", "Nan", "Sha", "Pei", "Haku", "Hatsu", "Chun"};
    string entrada;
    for (int iter = 0; iter < 14; iter++) {
        cin >> entrada;
        if (cartasInvalidas.find(entrada) != cartasInvalidas.end()) {
            cout << "Gong Fu Zai Gao,Ye Pa Duan Yao";
            return 0;
        }
    }
    cout << "Rong,Duan Yao Jiu,1000 Dian";
    return 0;
}
</string></set></iostream>

B. Título del Problema B

Puntuación: 100 | Límite de tiempo: 2000ms | Puntos de prueba: 10

Idea de la Solución:

Se exploran varios métodos para resolver el problema:

1. Enumerar los dos números seleccionados y calcular su máximo común divisor mediante búsqueda exhaustiva. Complejidad temporal O(amáx * n2), donde amáx es el valor máximo de los números.
2. Similar al anterior, pero usando el algoritmo de Euclides para el cálculo del máximo común divisor. Complejidad O(n2 * log n).
3. Sea m el valor máximo de los números. La respuesta debe ser un divisor común de dos números. Para cada número, se enumeran sus divisores y se cuentan sus ocurrencias. Si un divisor aparece al menos dos veces, puede ser una respuesta válida. Complejidad O(n * √m).
4. Solución óptima: Considerar cada divisor potencial x. Para que x sea respuesta, debe haber al menos dos múltiplos de x en la lista de números. Se cuenta para cada x los múltiplos presentes. Complejidad O(n * log n).

El siguiente código C++ implementa la solución óptima:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int cantidad, numero, maxNumero = 0;
    cin >> cantidad;
    vector<int> contador(5000001, 0);
    for (int i = 0; i < cantidad; i++) {
        cin >> numero;
        contador[numero]++;
        maxNumero = max(maxNumero, numero);
    }
    vector<int> conteoDivisores(5000001, 0);
    for (int divisor = 1; divisor <= maxNumero; divisor++) {
        for (int multiplo = divisor; multiplo <= maxNumero; multiplo += divisor) {
            conteoDivisores[divisor] += contador[multiplo];
        }
    }
    for (int candidato = maxNumero; candidato >= 1; candidato--) {
        if (conteoDivisores[candidato] >= 2) {
            cout << candidato << endl;
            return 0;
        }
    }
    return 0;
}
</int></int></algorithm></vector></iostream>

Para los problemas C y D, las soluciones no se detallan aquí, pero pueden consultarse en recursos externos específicos del concurso.