Задача 14 из 21

Зарядки на маршруте

Время 2 с · память 256 МБ

Робот движется по прямой из точки с координатой 0 в точку с координатой RR, только вперёд. Полного заряда батареи хватает на VV единиц пути; в начале пути батарея заряжена полностью. Вдоль пути расположены NN зарядных станций, на каждой из них батарею можно зарядить полностью. Участок длиной ровно VV робот преодолеть может.

Определите минимальное количество зарядок, необходимое для того, чтобы добраться до конечной точки, и минимально возможную при таком количестве зарядок координату станции, на которой робот заряжается в последний раз.

Входные данные

В первой строке находятся три натуральных числа: NN — количество станций (N≤100 000N \le 100\,000), RR — координата конечной точки (R≤109R \le 10^9) и VV — запас хода (V<RV < R). В каждой из следующих NN строк находится координата одной станции — натуральное число, меньшее RR.

Координаты станций различны и идут в произвольном порядке. Гарантируется, что робот может добраться до конечной точки.

Выходные данные

Выведите два целых числа: сначала минимальное количество зарядок, затем минимально возможную координату станции, на которой робот заряжается в последний раз.

Примеры

Ввод 1
6 30 12
5
11
17
20
23
27
Вывод 1
2 20
Ввод 2
4 20 12
3
15
12
9
Вывод 2
1 9

Примечание

В первом примере можно зарядиться в точках 11 и 20. Одной зарядки недостаточно, чтобы добраться до точки 30, а при двух зарядках последняя станция не может находиться раньше точки 20. Во втором примере достаточно одной зарядки: до конечной точки можно добраться со станций 9 и 12, меньшая координата — 9.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче