- Ejercicio Entrenamiento de Polycarp
- Presentaciones
- Mejores Presentaciones
Entrenamiento de Polycarp
Polycarp quiere entrenar antes de otra competencia de programación.
Tiene una lista de n concursos. El i-ésimo concurso contiene aᵢ problemas.
El entrenamiento dura varios días. En el día 1 debe resolver exactamente 1 problema; en el día 2 exactamente 2 problemas; en el día 3 exactamente 3 problemas; y en general, en el día k debe resolver exactamente k problemas.
Cada día, Polycarp debe elegir exactamente un concurso que aún no haya usado, y resolver exactamente k problemas de ese concurso. Los problemas restantes de ese concurso (si los hay) se descartan y ya no se pueden usar en días futuros.
Si en el día k no existe ningún concurso disponible con al menos k problemas, Polycarp detiene su entrenamiento.
Determina el máximo número de días que puede entrenar si elige los concursos de forma óptima.
Descripción de entrada:
La primera línea contiene un entero T: el número de casos de prueba.
Para cada caso de prueba:
• La primera línea contiene un entero n (1 ≤ n ≤ 2000): la cantidad de concursos.
• La segunda línea contiene n enteros a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 2·10⁵): problemas en cada concurso.
Descripción de salida:
Para cada caso de prueba, imprime un entero: el máximo número de días que Polycarp puede entrenar, en una línea.
Nota de BlitzCoding:
La primera línea del INPUT siempre será un entero T que indica el número de casos de prueba. Para este ejercicio, T será 3
Notas del ejercicio:
• Cada concurso se puede usar como máximo una vez.
• En el día k, el concurso elegido debe tener al menos k problemas; Polycarp resuelve exactamente k y el resto se descarta.