Решение задачи Тренировки Поликарпа с Codeforces
Без пояснения   Просмотров: 69
Поликарп хочет потренироваться перед очередным важным соревнованием по программированию. В течение первого дня его тренировок он хочет решить ровно 1 задачу, в течение второго дня — ровно 2 задачи, в течение третьего дня — ровно 3 задачи, и так далее. В течение k-го дня он хочет решить ровно k задач.
У Поликарпа есть список из n контестов, i-й контест состоит из ai задач. В течение каждого дня Поликарп будет выбирать ровно один из контестов, который он еще не решал до этого, и решать его. Он решает ровно k задач из этого контеста. Остальные задачи исключаются из контеста. Если контестов, состоящих из не менее k задач, которые Поликарп еще не решал, в течение k-го дня нет, то Поликарп прекращает тренироваться.
Как много дней Поликарп сможет тренироваться, если будет выбирать контесты оптимально?
У Поликарпа есть список из n контестов, i-й контест состоит из ai задач. В течение каждого дня Поликарп будет выбирать ровно один из контестов, который он еще не решал до этого, и решать его. Он решает ровно k задач из этого контеста. Остальные задачи исключаются из контеста. Если контестов, состоящих из не менее k задач, которые Поликарп еще не решал, в течение k-го дня нет, то Поликарп прекращает тренироваться.
Как много дней Поликарп сможет тренироваться, если будет выбирать контесты оптимально?