Problema 1: Conversión de formato de texto

Descripción: Dada una secuenica compuesta únicamente por caracteres latinos, se requiere modificar la capitalización de algunos caracteres para que toda la secuencia se convierta en mayúsculas o en minúsculas. Determine el número mínimo de modificaciones necesarias para lograr esto.

Formato de entrada: Una secuencia de caracteres, compuesta exclusivamente por caracteres latinos.

Formato de salida: Un entero que indica el número mínimo de modificaciones.

Rango de datos: Sea n el número de caracteres en la entrada, se garantiza que 1 ≤ n ≤ 100,000.

Ejemplo:

Entrada: TheQuickBrownFoxJumpsOverTheLazyDog

Salida: 9

Explicación: Se convierten todos los caracteres a minúsculas, requiriendo 9 cambios.

Solución: Se cuenta la cantidad de caracteres en mayúsculas y minúsculas. El mínimo de cambios es el menor entre ambas cantidades, ya que se elige convertir al formato con menos caracteres opuestos.

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

int main() {
    string texto;
    cin >> texto;
    int mayusculas = 0;
    for (char c : texto) {
        if (c >= 'A' && c <= 'Z') mayusculas++;
    }
    int minusculas = texto.length() - mayusculas;
    int cambios = min(mayusculas, minusculas);
    cout << cambios << endl;
    return 0;
}

Problema 2: Conteo de múltiplos

Descripción: Dados dos enteros a y b, y un entero positivo c, calcule cuántos enteros en el intervalo [a, b] (incluyendo a y b) son múltiplos de c.

Formato de entrada: Primera línea: dos enteros a y b; segunda línea: un entero positivo c.

Formato de salida: Un entero que representa la respuesta.

Rango de datos: −10^9 ≤ a ≤ b ≤ 10^9, 1 ≤ c ≤ 10^9.

Ejemplo:

Entrada: 4 6, 5

Salida: 1

Solución: En lugar de enumerar, se utiliza la fórmula matemática para contar múltiplos en un intervalo. Se manejan casos con valores positivos, negativos o mixtos mediante la división entera.

#include <iostream>
using namespace std;

int main() {
    int inicio, fin, divisor;
    cin >> inicio >> fin >> divisor;
    if (inicio > fin) swap(inicio, fin);
    int conteo = fin / divisor - (inicio - 1) / divisor;
    if (inicio <= 0 && fin >= 0) {
        conteo = (-inicio) / divisor + 1 + fin / divisor;
    } else if (inicio < 0 && fin < 0) {
        conteo = (-inicio) / divisor - (-fin - 1) / divisor;
    }
    cout << conteo << endl;
    return 0;
}

Problema 3: Unión de intervalos

Descripción: Dados n intervalos cerrados en una recta numérica, donde el i-ésimo intervalo tiene extremos [a_i, b_i], su unión se puede representar como varios intervalos cerrados disjuntos. Salida estos intervalos ordenados por su punto de inicio en orden ascendente.

Formato de entrada: Primera línea: un entero n; siguientes n líneas: dos enteros a_i y b_i por línea.

Formato de salida: Varias líneas, cada una con dos enteros que representan un intervalo cerrado en la unión, ordenados por inicio ascendente.

Rango de datos: Para 50% de los datos, 1 ≤ n ≤ 10^4, 0 ≤ a_i ≤ b_i ≤ 10^4; para 100%, 1 ≤ n ≤ 10^5, 0 ≤ a_i ≤ b_i ≤ 10^9.

Ejemplo:

Entrada: 3, (10,12), (1,3), (2,5)

Salida: (1,5), (10,12)

Solución: Se ordenan los intervalos por su inicio. Luego, se iteran para fusionarlos si se superponen, manteniendo un intervalo acumulado actual.

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

struct Intervalo {
    int izquierda, derecha;
};

bool comparar(Intervalo a, Intervalo b) {
    return a.izquierda < b.izquierda;
}

int main() {
    int n;
    cin >> n;
    vector<Intervalo> intervalos(n);
    for (int i = 0; i < n; i++) {
        cin >> intervalos[i].izquierda >> intervalos[i].derecha;
    }
    sort(intervalos.begin(), intervalos.end(), comparar);
    int actual_izq = intervalos[0].izquierda, actual_der = intervalos[0].derecha;
    for (int i = 1; i < n; i++) {
        if (intervalos[i].izquierda > actual_der) {
            cout << actual_izq << " " << actual_der << endl;
            actual_izq = intervalos[i].izquierda;
            actual_der = intervalos[i].derecha;
        } else {
            actual_der = max(actual_der, intervalos[i].derecha);
        }
    }
    cout << actual_izq << " " << actual_der << endl;
    return 0;
}

Problema 4: Partición equitativa de números

Descripción: Dados n enteros a_1, a_2, ..., a_n, determine si es posible dividirlos en dos partes (sin descartar ningún número) tales que la suma de cada parte sea igual.

Formato de entrada: Primera línea: un entero n; segunda línea: n enteros.

Formato de salida: Si es posible, salida "Matched"; de lo contrario, "No".

Rango de datos: Para 50% de los datos, 1 ≤ n ≤ 18; para 100%, 1 ≤ n ≤ 24, −10,000,000 ≤ a_i ≤ 10,000,000.

Ejemplo 1:

Entrada: 4, (1,2,3,4)

Salida: Matched

Ejemplo 2:

Entrada: 3, (2,2,2)

Salida: No

Solución: Se utiliza búsqueda exhaustiva (backtracking) para explorar todas las posibles asignaciones de números a dos grupos, verificando si alguna partición tiene sumas iguales. La complejidad es O(2^n), factible para n ≤ 24.

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

bool encontrado = false;
int total_numeros;

void buscar(int indice, int suma_grupo1, int suma_grupo2, vector<int>& numeros, vector<bool>& usado) {
    if (encontrado) return;
    if (indice == total_numeros) {
        if (suma_grupo1 == suma_grupo2) encontrado = true;
        return;
    }
    for (int i = 0; i < total_numeros; i++) {
        if (!usado[i]) {
            usado[i] = true;
            buscar(indice + 1, suma_grupo1 + numeros[i], suma_grupo2, numeros, usado);
            buscar(indice + 1, suma_grupo1, suma_grupo2 + numeros[i], numeros, usado);
            usado[i] = false;
            break; // Reducir búsqueda al fijar el orden
        }
    }
}

int main() {
    cin >> total_numeros;
    vector<int> numeros(total_numeros);
    for (int i = 0; i < total_numeros; i++) cin >> numeros[i];
    vector<bool> usado(total_numeros, false);
    buscar(0, 0, 0, numeros, usado);
    if (encontrado) cout << "Matched" << endl;
    else cout << "No" << endl;
    return 0;
}

Problema 5: Coloreado de anillo con tres colores

Descripción: Dado un anillo con n puntos, cada punto debe colorearse con uno de tres colores, de modo que puntos adyacentes en el anillo no tengan el mismo color. Calcule el número de esquemas de coloreado. El resultado puede ser grande; salida el módulo 1,000,000,007.

Formato de entrada: Un entero n.

Formato de salida: El número de esquemas módulo 1,000,000,007.

Rango de datos: Para 30% de los datos, 1 ≤ n ≤ 20; para 60%, 1 ≤ n ≤ 1,000,000; para 100%, 1 ≤ n ≤ 10^18.

Ejemplo 1:

Entrada: 1

Salida: 3

Ejemplo 2:

Entrada: 3

Salida: 6

Solución: Se modela con recursión o programación dinámica. Para n > 3, la recurrencia es f(n) = f(n-1) + 2 * f(n-2), con casos base f(1)=3, f(2)=6, f(3)=6. Para n grande, se usa exponenciación rápida basada en esta recurrencia.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long exponenciacion_rapida(long long base, long long exp) {
    if (exp == 1) return base % MOD;
    long long mitad = exponenciacion_rapida(base, exp / 2);
    long long resultado = (mitad * mitad) % MOD;
    if (exp % 2 == 1) resultado = (resultado * base) % MOD;
    return resultado;
}

int main() {
    long long n;
    cin >> n;
    if (n == 1) cout << 3 << endl;
    else if (n == 2) cout << 6 << endl;
    else if (n == 3) cout << 6 << endl;
    else {
        long long potencia = exponenciacion_rapida(2, n);
        long long resultado;
        if (n % 2 == 1) resultado = (potencia - 2 + MOD) % MOD;
        else resultado = (potencia + 2) % MOD;
        cout << resultado << endl;
    }
    return 0;
}