Умакса в огороде есть большой вишневый сад, состоящий из n деревьев, расположенных по кругу. на каждом из деревьев висит некоторое количество вишен.
макс хочет собрать ягоды, а для этого выбрать дерево с которого начинать сбор и идти по кругу, либо по часовой, либо против часовой стрелки. макс решил собирать ягоды в ведра, каждое из которых вмещает k вишен. сбор ягод с высоких деревьев – трудоемкая , поэтому для удобства макс хочет, чтобы вместимости текущего ведра всегда хватало, чтобы собрать всю вишню с дерева полностью. тогда, если вместимости ведра не хватает, макс кладет текущее ведро и берет новое.
макс хочет выбрать точку начала и направление оптимально так, чтобы использовать как можно меньшее количество ведер.
выведите минимальное количество ведер, которое понадобится максу для сбора всех ягод.

входные данные

первая строка содержит целые числа n и k (1≤n≤2⋅1051≤n≤2⋅105, 1≤k≤1091≤k≤109) — соответственно количество деревьев и вместимость одного ведра.
вторая строка содержит nn целых чисел xi (1≤xi≤k1≤xi≤k) — количество вишен на каждом из деревьев.

выходные данные

выведите одно целое число — количество ведер, которое понадобится максу, чтобы собрать всю вишню.

примеры

входные данные

5 10 3 3 3 7 2

выходные данные

2

входные данные

7 10 3 3 7 3 4 4 3

выходные данные

3

желательно алгоритм на питоне)
заранее

243

296

Посмотреть ответы 1

Ответы на вопрос:

Kell500

Информатика

4,5(11 оценок)

program gwr;

var

i : integer;

begin

writeln('Введите объём файла в Кб');

readln(i);

writeln('Информационный объём в битах равен:', i * 1024 * 8);

writeln('Информационный объём в байтах равен: ', i * 1024);

writeln('Информационный объём в Мегабайтах равен: ', i /1024);

end.

Задай свой вопрос

Как otvet5GPT работает?

otvet5GPT использует большую языковую модель вместе с базой данных GPT для обеспечения высококачественных образовательных результатов. otvet5GPT действует как доступный академический ресурс вне класса.
Сколько это стоит?

Проект находиться на стадии тестирования и все услуги бесплатны.
Могу ли я использовать otvet5GPT в школе?

Конечно! Нейросеть может помочь вам делать конспекты лекций, придумывать идеи в классе и многое другое!
В чем отличия от ChatGPT?

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