Минимальный уровень сжатия

Ты собираешься отправить другу набор файлов. В телефоне есть «уровень сжатия» d — целое число.

Если файл имеет размер a, то после сжатия он занимает ceil(a / d) «единиц трафика». (То есть при делении с остатком округляем вверх.)

У тебя есть лимит трафика T. Хочется выбрать самый маленький уровень сжатия d, чтобы суммарный трафик на все файлы не превышал T.

Важно: сумма трафика может быть больше 2^31, поэтому в других языках нужен 64-битный тип (int64). В Python это не проблема.

Формат ввода

В первой строке даны два целых числа n и T — количество файлов и лимит трафика. Во второй строке даны n целых чисел a1, a2, ..., an — размеры файлов.

Формат вывода

Выведи одно целое число d — минимальный уровень сжатия, при котором сумма ceil(ai / d) по всем файлам не превышает T.

Ограничения

• 1 ≤ n ≤ 5000
• 1 ≤ ai ≤ 1 000 000
• n ≤ T ≤ 1 000 000 000

Пример

Ввод:

5 7
8 3 5 10 2

Вывод:

5

Ключевое наблюдение: если увеличить уровень сжатия d, каждый член ceil(ai / d) не возрастает, значит и сумма по всем файлам тоже не возрастает. То есть условие «сумма <= T» — монотонное по d: для маленьких d обычно плохо, для достаточно больших — хорошо. Это идеальная ситуация для бинарного поиска по ответу.

Как считать трафик без вещественных чисел: ceil(ai / d) удобно выразить целочисленно: (ai + d - 1) // d.

План решения:

• Заведи функцию ok(d): пробегает по всем файлам, накапливает s += (ai + d - 1) // d.
• Если в процессе s > T, сразу возвращай False (ранний выход ускоряет).
• Иначе после цикла True.
• Бинарный поиск по d:
• левая граница lo = 1 (сжатие минимум 1);
• правая hi = max(ai) (при таком d каждый файл даст 1, а по условию T >= n, значит точно поместимся).
• пока lo < hi:
• mid = (lo + hi) // 2;
• если ok(mid) истинно, сдвигай hi = mid (можно попробовать меньше);
• иначе lo = mid + 1.
• Ответ — lo.

Сложность: ok(d) работает за O(n), бинарный поиск делает O(log max(ai)) шагов, итого O(n log maxA), что проходит при n до 5000.

Частая ошибка: считать ceil(ai / d) через обычное деление (получаются float и погрешности) или поставить неверную верхнюю границу (например, hi = 1e9 без надобности). Лучше держать hi = max(ai) и использовать формулу с //.