images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:21:22

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2010. Забор

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Петя решил сделать небольшой забор из нескольких имеющихся у него досок разной длины. Из эстетических соображений разница в длине планок забора не должна превышать некоторой величины `D`. Петя может разрезать доску на любое количество планок, имеющих любую длину. Необязательно, чтобы их длина была целым числом или планки из одной доски имели одинаковую длину. Но после разрезания нельзя выбрасывать ничего – все отрезанные от доски части становятся планками забора. Так как Пете приходится пилить доски ножовкой (вручную), то он хочет минимизировать количество распилов.
Напишите программу, которая подсчитает минимальное количество распилов для заданного набора досок на планки, при котором разница в длине между самой длинной и самой короткой планкой не будет превышать `D`.
Первая строка ввода содержит два целых числа — количество досок `N` (`2\ ≤\ N\ ≤\ 1000`) и ограничение по разнице длин планок `D` (`100\ ≤\ D\ ≤\ 1000`). Во второй строке содержится `N` целых чисел в диапазоне от 1000 до 100000 — длины досок.
Вывести одно целое число — минимальное количество распилов.

Пример ввода

2 100
1600 1100

Пример вывода

3
Пояснение к примеру: Петя может первую доску распилить на планки длиной 500, 500 и 600 с помощью двух распилов, а вторую доску – на две планки длиной 500 и 600. Это не единственный вариант. Можно распилить вторую доску на части длиной 501 и 599 или 502.36 и 597.64.
Характеристика тестов к задаче:
Для 10-11 классов в 20% тестов `N=2`, в 30% тестов `N=10`, в 50% тестов `N=1000`.
Для 7-9 классов `N≤10` и использовалась половина всех тестов, в 40% тестов `N=2`, в 60% тестов `N=10`.
loading