Имеется 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
Как решить??? а то горит зачет.
Полная версия: Бинарный поиск
А что именно не получается? Работа с файлами, подсчет кол-ва кусков, алгоритм бинарного поиска? Или может быть нужна программа целиком? Так это сюда: задачи на заказ.
Цитата(Shura @ 9.01.2006 19:15) 
А что именно не получается? Работа с файлами, подсчет кол-ва кусков, алгоритм бинарного поиска? Или может быть нужна программа целиком? Так это сюда: задачи на заказ.
Подсчет кол-во кусков.
Обычный поиск. Берешь число "p", равное максимальному элементу из А. Нацело делишь каждый элемент из А на "p". Результаты складываешь. Если сумма эта меньше, чем "к", значит эта длина (p) не подходит. Тогда уменьшаешь "p" на единицу и делаешь то же самое. И так до тех пор пока сумма эта не будет больше либо равна "k".
Бинарный поиск. Не врублюсь до конца, зачем он тут - только усложняется все... Делается примерно так же. По правилу бинарного поиска ищем первое число среди интервала 1..max (max - максимальный элемент из А), которое НЕ удовлетворяет условию "сумма >= k".
Бинарный поиск. Не врублюсь до конца, зачем он тут - только усложняется все... Делается примерно так же. По правилу бинарного поиска ищем первое число среди интервала 1..max (max - максимальный элемент из А), которое НЕ удовлетворяет условию "сумма >= k".
Цитата(Shura @ 9.01.2006 20:19)
Обычный поиск. Берешь число "p", равное максимальному элементу из А. Нацело делишь каждый элемент из А на "p". Результаты складываешь. Если сумма эта меньше, чем "к", значит эта длина (p) не подходит. Тогда уменьшаешь "p" на единицу и делаешь то же самое. И так до тех пор пока сумма эта не будет больше либо равна "k".
Бинарный поиск. Не врублюсь до конца, зачем он тут - только усложняется все... Делается примерно так же. По правилу бинарного поиска ищем первое число среди интервала 1..max (max - максимальный элемент из А), которое НЕ удовлетворяет условию "сумма >= k".
спасибо.
Вот набросок с обычным поиском. К и N задаются вручную в теле программы.
Uses
Crt;
var
a: Array [1..1000] of LongInt;
i,n,k,p: Word;
j,max,l,t: LongInt;
begin
Randomize;
ClrScr;
n:=10;
k:=15;
for i:=1 to n
do begin
a[i]:=Random(20)+10;
Write(a[i],' ')
end;
writeLn;
max:=a[1];
for i:=2 to n
do if a[i] > max
then max:=a[i];
j:=max+1;
repeat
Dec(j);
p:=0;
for i:=1 to n
do Inc(p,(a[i] div j))
until (j < 0)or(p >= k);
Write(j);
ReadLn
End.
Код
Uses
Crt;
var
a: Array [1..1000] of LongInt;
i,n,k,p: Word;
j,max,l,t: LongInt;
begin
Randomize;
ClrScr;
n:=10;
k:=15;
for i:=1 to n
do begin
a[i]:=Random(20)+10;
Write(a[i],' ')
end;
writeLn;
max:=a[1];
for i:=2 to n
do if a[i] > max
then max:=a[i];
j:=max+1;
repeat
Dec(j);
p:=0;
for i:=1 to n
do Inc(p,(a[i] div j))
until (j < 0)or(p >= k);
Write(j);
ReadLn
End.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.