Problema A: Conteo de números sin una secuencia específica

Se requiere determinar cuántos números en el rango de 12345678 a 98765432 no contienen la subsecuencia "2023". "No contener" significa que incluso eliminando dígitos del número, no se puede formar "2023". Por ejemplo, 20322175 y 33220022 no contienen "2023", mientras que 20230415 y 20193213 sí lo contienen (en el último caso, tomando los dígitos en posiciones 1, 2, 6 y 8).

Solución mediante fuerza bruta:

def verificar_subcadena(numero, objetivo="2023"):
    indice = 0
    representacion = str(numero)
    for digito in representacion:
        if indice < len(objetivo) and digito == objetivo[indice]:
            indice += 1
        if indice == len(objetivo):
            return True  # Contiene la subsecuencia
    return False  # No contiene la subsecuencia

total_excluidos = 0
for valor in range(12345678, 98765433):
    if not verificar_subcadena(valor):
        total_excluidos += 1
print(total_excluidos)  # Resultado: 85959030

Se itera sobre cada número en el rango y se verifica si contiene "2023" como subsecuencia. El número total sin la subsecuencia se calcula contando los casos negativos.

Problema B: Intercambio de monedas

Dado un conjunto inicial de monedas con valores del 1 al 2023, se busca maximizar el número de monedas nuevas generdaas por suma de dos monedas existentes, donde el valor de la nueva moneda es la suma de dos monedas y debe ser único. Se encontró que la cantidad máxima se alcanza cuando el valor final de la moneda nueva sigue una fórmula cuadrática.

Optimización mediante análisis matemático:

monedas_iniciales = 2023
# Calcula el número máximo de combinaciones para generar monedas nuevas
maximo = 0
for fin in range(1012, 2023):
    nuevo_suma = fin * 2 + 1
    inicio = nuevo_suma - 2023
    cantidad = (fin - inicio + 1) * (inicio + fin) // 2
    if cantidad > maximo:
        maximo = cantidad
    else:
        break  # Punto óptimo encontrado
print(maximo)  # Resultado: 682425
total_monedas = monedas_iniciales + sum(range(1, 1012))
print(total_monedas)  # Para el caso simple: 513589

Se utiliza un enfoque iterativo para encontrar el valor de "fin" que maximiza la cantidad de monedas nuevas, basado en la fórmula de progresión aritmética.

Problema C: Secuencia suelta

Se define una secuencia suelta como una subsecuencia donde los índices de caracteres consecutivos en la subsecuencia orignial difieren en al menos 2. El objetivo es encontrar la secuencia suelta con el valor máximo, donde cada carácter tiene un valor igual a su posición en el alfabeto (a=1, b=2, etc.).

Solución con programación dinámica:

def valor_maximo_secuencia(cadena):
    n = len(cadena)
    dp = [0] * n  # dp[i] guarda el valor máximo terminando en posición i
    valores = {chr(ord('a') + i): i + 1 for i in range(26)}
    puntero = -1
    for i in range(n):
        if i == 0:
            dp[i] = valores[cadena[i]]
        elif i == 1:
            dp[i] = max(valores[cadena[i]], dp[i-1])
        else:
            while puntero < i - 2 or (puntero >= 0 and cadena[puntero+1:puntero+3] != cadena[i-1:i+1]):
                puntero += 1
            dp[i] = dp[puntero] + valores[cadena[i]]
            dp[i] = max(dp[i], dp[i-1])
    return dp[-1]

entrada = input()  # Ejemplo: "azaazaz"
print(valor_maximo_secuencia(entrada))  # Resultado: 78

Se emplea un arreglo dp para acumular valores máximos, manteniendo un puntero para asegurar la condición de distancia mínima entre índices.

Problema D: Cobertura de tuberías

Dado un conjunto de válvulas en una tubería de longitud L, cada válvula se activa en un tiempo S y cubre un intervalo que se expande con el tiempo. Se busca el tiempo mínimo en que toda la tubería está cubierta por al menos una válvula.

Solución con búsqueda binaria y arrays de diferencia:

def cobertura_total(tiempo, longitud, posiciones, activaciones):
    arreglo = [0] * (longitud + 2)
    for i in range(len(posiciones) - 1, -1, -1):
        arreglo[i] -= arreglo[i - 1]
    for idx in range(len(posiciones)):
        if tiempo >= activaciones[idx]:
            izquierda = posiciones[idx] - (tiempo - activaciones[idx])
            derecha = posiciones[idx] + (tiempo - activaciones[idx])
            izquierda = max(izquierda, 0)
            derecha = min(derecha, longitud)
            arreglo[izquierda] += 1
            arreglo[derecha + 1] -= 1
    for i in range(1, longitud + 2):
        arreglo[i] += arreglo[i - 1]
    return sum(arreglo[1:longitud + 1])

n, longitud_tuberia = map(int, input().split())
posiciones_valvulas = []
tiempos_activacion = []
for _ in range(n):
    pos, activ = map(int, input().split())
    posiciones_valvulas.append(pos)
    tiempos_activacion.append(activ)

bajo, alto = 1, 100000000
while bajo < alto:
    medio = (bajo + alto) // 2
    if cobertura_total(medio, longitud_tuberia, posiciones_valvulas, tiempos_activacion) < longitud_tuberia:
        bajo = medio + 1
    else:
        alto = medio
print(bajo)  # Resultado para el ejemplo: 5

Se utiliza búsqueda binaria para encontrar el tiempo mínimo, verificando la cobertura total mediante un enfoque de diferencias para manejar intervalos eficientemente.