Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Флагштокинг

(Время: 1 сек. Память: 64 Мб Сложность: 33%)

На всемирный чемпионат по Лагопроге приехали n команд. У каждой команды есть флаг, и организаторы хотят разместить их на n подготовленных флагштоках.

Высота i-го флагштока hi метров, но организаторы хотят, чтобы максимальная разница высот двух флагштоков не превосходила D метров.

К счастью, на площадке проведения есть опытный флагштокер. За одну секунду он может поднять или опустить любой флагшток на один метр.

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа n и D — количество флагштоков и максимальная допустимая разница (1 ≤ n ≤ 2×105; 0 ≤ D ≤ 109).

Вторая строка содержит n целых чисел: h1, h2, …, hn (1 ≤ hi ≤ 109). Число hi обозначает высоту i-го флагштока.

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

В выходной файл OUTPUT.TXT выведите минимальное количество секунд, за которое можно изменить высоты флагштоков требуемым образом. То есть так, чтобы для любых двух флагштоков модуль разности их высот не превосходил D.

Примеры

INPUT.TXTOUTPUT.TXT
15 4
4 2 8 1 10
7
26 0
1 2 3 4 5 6
9
36 10
1 2 3 4 5 6
0

Примечание

В первом примере, как один из вариантов, нужно поднять второй и четвёртый флагштоки до высоты 3 метра (на это потребуется 3 секунды), а третий и пятый опустить до высоты 7 метров (на это потребуется 4 секунды).


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Хитрое число
 B. Сортировка за линию?
 C. Игра Рогалик
 D. Школа Зебры
 E. Локдаун Империи
 F. Флагштокинг
 G. GCD Пары
 H. Ещё одна игровая механика
 I. Столкновение пермутонов
 J. Равномерные раскраски

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru