Задача №115123. Стабильные параллели
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Паша и Тёма приехали преподавать в зимний ноутбучный университет. Теперь им необходимо разобраться с учениками.
Есть \(n\) учеников, пронумерованных от \(1\) до \(n\). Уровень знаний \(i\)-го ученика равен \(a_i\). Всех учеников нужно распределить на стабильные параллели . Параллель называется стабильной , если после сортировки всех учеников параллели в порядке возрастания их уровня знаний у любых двух подряд идущих учеников разница уровня знаний не превосходит \(x\).
Преподаватели достаточно находчивые люди, поэтому они могут пригласить не более \(k\) дополнительных учеников с любым требуемым уровнем знаний. Определите минимальное число стабильных параллелей, на которые можно распределить всех учеников (возможно, пригласив не более \(k\) новых учеников).
В первой строке вводятся три целых числа \(n\), \(k\), \(x\) (\(1 \le n \le 200\,000, 0 \le k \le 10^{18}, 1 \le x \le 10^{18}\)) — количество учеников, сколько учеников можно пригласить дополнительно и максимальная допустимая разница уровня знаний.
Во второй строке вводится \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^{18}\)) — уровни знаний учеников.
В единственной строке выведите одно число — искомое минимальное число стабильных параллелей, на которое можно разбить учеников.
В первом примере из условия можно пригласить учеников с уровнями знаний, равными \(2\) и \(11\). Тогда учеников можно разделить на следующие стабильные параллели:
- \([1, 1, 2, 5, 8, 11, 12, 13]\),
- \([20, 22]\).
Во втором примере из условия новых учеников приглашать нельзя, поэтому потребуется \(3\) параллели:
- \([1, 1, 5, 5, 20, 20]\)
- \([60, 70, 70, 70, 80, 90]\)
- \([420]\)
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(n, k, x, a_i \le 10\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(k = 0\), наберут не менее \(14\) баллов.
Решения, корректно работающие, когда ответ не превосходит \(2\), наберут не менее \(16\) баллов.
Решения, корректно работающие при \(n, k, x, a_i \le 1000\), наберут не менее \(40\) баллов.
8 2 3 1 1 5 8 12 13 20 22
2
13 0 37 20 20 80 70 70 70 420 5 1 5 1 60 90
3