750A - New Year and Hurry

Límite de tiempo por prueba: 1 segundo.
Límite de memoria por prueba: 256 megabytes.
Código Original.
Fecha: 13/09/2025.
Dificultad: 🍰 (800)
Tags: binary search, brute force, implementation, math

Limak va a participar en un concurso el último día de 2016. El concurso empezará a las 20:00 y durará cuatro horas, exactamente hasta la medianoche. Habrá problemas, ordenados por dificultad, es decir, el problema es el más fácil y el problema es el más difícil. Limak sabe que le tomará minutos resolver el problema -ésimo.

Los amigos de Limak organizan una fiesta de Año Nuevo y él quiere llegar a la fiesta a la medianoche o antes. Necesita minutos para llegar desde su casa, donde participará en el concurso primero.

La pregunta es: ¿Cuántos problemas puede resolver Limak si quiere llegar a la fiesta a tiempo?

Entrada

Los parámetros de entrada son dos enteros y ( , ): el número de problemas en el concurso y la cantidad de minutos que Limak necesita para llegar a la fiesta desde su casa.

Salida

Imprime un entero, que representa el número máximo posible de problemas que Limak puede resolver para poder llegar a la fiesta a medianoche o antes.

Ejemplo

Input	Output
`3 222`	2
`4 190`	4
`7 1`	7

Solución O(n) en C++

Esta solución es de fuerza bruta. Probando todos los elementos posibles.

// g++ solution-o(n).cpp -o solution
#include <iostream>
    
using namespace std;
    
int main() {
    long long n, k, available, total, acc;
    
    cin >> n >> k;
    
    available = 240 - k;
    total = 0;
    acc = 0;
    
    for(int i = 1; i <= n; i++) {
        acc += i * 5;
        if (acc <= available) {
            total += 1;
        }
    }
    
    cout << total << endl;
    
    return 0;
}

Solución O(1) en C++

Para poder resolver este problema se debe pensar matemáticamente (Estilo Ruso). En primer lugar tenemos una progresión de términos que se deben sumar para obtener el tiempo total necesario para resolver la cantidad de problemas dado por . Agradecimientos a Marcelo Guzman (13/09/2025) por detallar el análisis matemático.

Ejemplo:

Entonces al tener una progresión de elementos que se deben sumar, se puede usar lo que se conoce como progresión aritmética.

La progresión aritmética tiene dos fórmulas que pueden ser usadas dependiendo de la cantidad de información que se tenga disponible.

Se conoce el primer y último término de la progresión:
Solo se conoce el primer término de la progresión:

Según la información del enunciado se conoce los siguientes datos:

El tiempo disponible: .
La cantidad total de problemas: .

Como la progresión tiene una fórmula constante de . Podemos calcular el primer y último término de la progresión. El primer término siempre será , debido a que la cantidad de problemas siempre parte en . El último término siempre será , debido a que la cantidad máxima siempre será el total de problemas multiplicado por .

Por lo que la fórmula para calcular el total de tiempo dado un valor será:

Tenemos el valor que tomará resolver cantidad de problemas, sin embargo debemos verificar que esto sea menor o igual al tiempo disponible. La pregunta a responder es: ¿Cuál es el valor de cantidad de problemas de modo que sea menor o igual al tiempo disponible?.

Desarrollamos la ecuación.

Como es un valor constante, obtenemos una ecuación cuadrática.

Solo necesitamos despejar con la fórmula de ecuación cuadrática .

Siendo los siguientes los valores a reemplazar en la ecuación:

(Coeficiente cuadrático )
(Coeficiente lineal )
(Constante o término independiente).

Por lo que la ecuación quedan dos posibles resultados.

Solución Positiva:
Solución Negativa:

Como estamos contando minutos, estos no pueden ser negativos. Por lo que solamente consideramos con la Solución Positiva.

Reemplazamos por el valor "disponible"

Finalmente, la solución no puede ser mayor a la cantidad máxima de ejercicios disponibles. Por lo que debemos aplicar una operación de límite máximo. Conocida como clamp o abrazadera (clamp(x, min, max)).

// g++ solution-o(1).cpp -o solution
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int n, k, answer, available;
    cin >> n >> k;

    available = 240 - k;

    answer = (-1 + sqrt(1 + (8 * available) / 5)) / 2;
    // also can be: clamp(answer, 0, n);
    answer = min(max(answer, 0), n);
    
    cout << answer << endl;
    return 0;
}

Solución O(logn) en Python

La solución corresponde a encontrar la respuesta utilizando búsqueda binaria entre todo el espectro de candidatos posibles (técnica de Binary Search in answer).

Paso 1

Sabemos que el tiempo máximo será de 4 horas - el tiempo que tome llegar a la fiesta. Es decir minutos (siendo los minutos que tiene 4 horas).

El desafío consiste en averiguar la cantidad máxima de problemas que se pueden resolver dentro del tiempo disponible.

def main():
    n, k = map(int, input().split())
    available_time = 240 - k
    print(find_max_quantity_of_solved_problems(n, available_time))

if __name__ == "__main__":
  main()

Paso 2

Ahora se obtiene el máximo y el mínimo dentro de la función que aplicará la búsqueda binaria. Estos vienen siendo la cantidad de problemas posibles a resolver. Como mínimo resolveremos cero y como máximo la cantidad total de problemas.

Notar que si el candidato es válido, tenemos que averiguar si el siguiente candidato es mejor (más problemas posibles a resolver). Por lo que debemos aumentar el límite mínimo. Caso contrario deberemos reducir el límite máximo.

def find_max_quantity_of_solved_problems(total_problem_count, available_time):
    low = 0
    high = total_problem_count

    answer = high

    while low <= high:
        candidate = low + (high - low) // 2

        if candidate_is_valid(candidate, available_time):
            answer = candidate
            low = candidate + 1
        else:
            high = candidate - 1

    return answer

Paso 3

Luego se define la función para validar el candidato. Si el tiempo total necesario para resolver la cantidad de problemas sugeridas por el candidato es menor al tiempo disponible, entonces es un candidato válido. El range de es mínimo es y máximo la cantidad de soluciones del candidato + una adicional para compensar el contador desde cero.

def candidate_is_valid(quantity_to_solve, available_time):
  used_time = 0
  for i in range(1, quantity_to_solve + 1):
    used_time += i * 5
  return used_time <= available_time

Solución

Juntando todo el código se tiene la siguiente solución.

# python3 solution-bs.py
def candidate_is_valid(quantity_to_solve, available_time):
  used_time = 0
  for i in range(1, quantity_to_solve + 1):
    used_time += i * 5
  return used_time <= available_time
    
def find_max_quantity_of_solved_problems(total_problem_count, available_time):
    low = 0
    high = total_problem_count

    answer = high

    while low <= high:
        candidate = low + (high - low) // 2

        if candidate_is_valid(candidate, available_time):
            answer = candidate
            low = candidate + 1
        else:
            high = candidate - 1
            
    return answer

def main():
    n, k = map(int, input().split())
    available_time = 240 - k
    print(find_max_quantity_of_solved_problems(n, available_time))
    
if __name__ == "__main__":
  main()