Задача №113506. Миша и снеговики
У Миши сегодня день рождения, и в честь этого события он решил погулять с друзьями. Поскольку день рождения Миши в морозный зимний день, дети отправились играть со снегом на поляне. Они уже заготовили n снежных шаров и были готовы лепить из них снеговиков, как вдруг Миша сообщил, что ему нравятся только красивые снеговики . В представлении Миши красивый снеговик — снеговик, состоящий из как минимум k снежных шаров, идущих в порядке невозрастания радиуса снизу вверх. Причём радиусы двух соседних шаров должны отличаться не менее чем на d сантиметров.
Поскольку дети больше не хотят катать новые снежные шары, им интересно узнать, какое максимальное число красивых снеговиков они смогут сделать из уже скатанных шаров. Помогите им решить эту задачу.
Первая строка содержит три целых числа n , k и d ( 1 ≤ k ≤ n ≤ 100 000 , 0 ≤ d ≤ 10 9 ) — количество снежных шаров, минимальное количество шаров в одном красивом снеговике и минимальную разность радиусов двух соседних шаров в красивом снеговике.
Вторая строка содержит n целых чисел r 1 , r 2 , ..., r n ( 1 ≤ r i ≤ 10 9 ) — радиусы имеющихся снежных шаров.
Выведите одно число — максимальное количество красивых снеговиков, которое можно слепить из данных снежных шаров.
В первом примере можно слепить только одного красивого снеговика, состоящего из шаров радиусами 13 и 5 .
Во втором примере можно слепить много различных пар красивых снеговиков, например из шаров радиусами 11 , 5 и 6 , 1 или 11 , 2 и 6 , 1 . Способа слепить трех красивых снеговиков нет.
В третьем примере можно лепить любых снеговиков, поскольку d = 0 , например 8 , 7 , 6 , 3 или 3 , 3 , 1 . Но оптимальным распределением шаров по снеговикам будет распределение, в котором каждый шар является отдельным снеговиком.
В четвертом примере нельзя слепить ни одного красивого снеговика.
3 2 6 5 10 13
1
7 2 5 1 6 3 4 2 11 5
2
8 1 0 1 3 3 3 5 8 7 6
8
2 2 100 1 1
0