1697. Как стать призёром

К тренеру на занятия по подготовке к олимпиаде ходит n школьников. Для каждого из школьников заданы два параметра: начальный условный опыт a_i и условный интеллект b_i.

Каждое занятие устроено так: тренер подходит к какому-нибудь школьнику и обсуждает с ним возникшие вопросы и проблемы. В результате такого обсуждения условный опыт этого школьника возрастёт на b_i (то есть чем выше условный интеллект школьника, тем больше этот школьник может взять от общения с тренером).

За всё время подготовки к олимпиаде тренер может подойти ко всем школьникам суммарно не более c раз (он может подходить к разным школьникам, может несколько раз подходить к одному и тому же школьнику). Для того, чтобы школьник стал призёром олимпиады, к началу олимпиады его условный опыт должен быть не меньше чем k.

Напишите программу, которая вычислит максимальное количество призёров олимпиады, которые сможет подготовить тренер.

Вход. Сначала вводятся натуральные числа n, c, k (1 ≤ n ≤ 10⁶, 1 ≤ c ≤ 10⁹, 1 ≤ k ≤ 10⁹), задающие количество школьников, количество подходов, которые может сделать учитель, и условный опыт, необходимый, чтобы стать призёром олимпиады, соответственно. Далее идёт n пар целых неотрицательных чисел a_i, b_i, задающих начальный условный опыт и условный интеллект каждого школьника. Каждое из чисел a_i и b_i не превышает 10⁹.

Выход. Выведите одно число – наибольшее количество призёров олимпиады, которое успеет подготовить тренер.

Пример входа 1	Пример выхода 1
3 5 6 1 1 2 1 4 2	2
Пример входа 2	Пример выхода 2
4 10 3 0 1 0 1 0 2 2 0	3

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Если для некоторого школьника a_i ≥ k, то он уже является призером и тренеру подходить к нему не надо. Если b_i = 0, то увеличить опыт такого школьника невозможно, станет ли он призером или нет – зависит только от его исходного значения a_i (при a_i ≥ k он призер, иначе – нет).

Через p подходов тренера к школьнику его опыт станет равным a_i + b_i * p. Для того чтобы это значение было не менее k (a_i + b_i * p ≥ k) следует совершить как минимум p = подходов.

Занесем в массив pts число подходов, которое следует совершить к каждому школьнику чтобы сделать его призером. Отсортируем по возрастанию массив pts. Поскольку количество подходов тренера ограничено, то следует сначала тренировать тех школьников, которые требуют меньшего количества подходов. Таким образом мы сможем обеспечить наибольшее количество призеров.

Реализация алгоритма

Пусть MAX содержит максимальное значение.

#define MAX 2000000000

Читаем входные данные.

scanf("%d %d %d",&n,&c,&k);

Заносим в массив pts число подходов, которое следует совершить к каждому школьнику чтобы сделать его призером.

for(i = 0; i < n; i++)

{

scanf("%d %d",&a,&b);

if (b == 0)

pts.push_back(MAX * (a < k));

else if (a >= k)

pts.push_back(0);

else

pts.push_back(((k - a) + b - 1) / b);

}

Отсотрируем массив pts.

sort(pts.begin(),pts.end());

Подсчитываем количество призеров. Обрабатываем школьников по возрастанию количества подходов к нему тренера.

for(res = i = 0; i < n; i++)

if (c >= pts[i])

{

c -= pts[i];

res++;

}

else break;

Выводим количество призеров.

printf("%d\n",res);