Имеется N катушек с нитками. На первой из них A1 см ниток, на второй - A2 см,:, на N-ой - AN см. Для красивой вышивки требуется K штук кусков ниток равной длины. Требуется узнать какую наибольшую длину может иметь каждый из K кусков, если
1) нитки связывать нельзя, их можно только резать;
2) каждый из K кусков имеет длину равную целому числу сантиметров.

Входные данные
В первой строке входного файла записано два целых числа N и K (1 <= N, K <= 1000). Далее, во второй строке, следует N целых чисел A1, A2, ...,AN (1 <= Ai <= 100000, для всех i=1,..,N), разделенных пробелами и/или переводами строк.

Выходные данные
Выведите единственное целое число - наибольшую возможную длину каждого из K равных кусков (возможно, что ответ равен 0).

Пример

Ввод

2 5
2 4


Вывод

1

Как решить??? а то горит зачет.

А что именно не получается? Работа с файлами, подсчет кол-ва кусков, алгоритм бинарного поиска? Или может быть нужна программа целиком? Так это сюда: задачи на заказ.

Подсчет кол-во кусков.

Обычный поиск. Берешь число "p", равное максимальному элементу из А. Нацело делишь каждый элемент из А на "p". Результаты складываешь. Если сумма эта меньше, чем "к", значит эта длина (p) не подходит. Тогда уменьшаешь "p" на единицу и делаешь то же самое. И так до тех пор пока сумма эта не будет больше либо равна "k".
Бинарный поиск. Не врублюсь до конца, зачем он тут - только усложняется все... Делается примерно так же. По правилу бинарного поиска ищем первое число среди интервала 1..max (max - максимальный элемент из А), которое НЕ удовлетворяет условию "сумма >= k".

Сообщение отредактировано: Shura - 10.01.2006 0:23

спасибо.

Вот набросок с обычным поиском. К и N задаются вручную в теле программы.