В Берляндский ГУ поступила новая обучающая программа. Её надо скопировать на все N компьютеров. Сейчас она установлена только на первом. Компьютеры не объединены в локальную сеть и не снабжены дисководами. Единственный способ передать информацию с одного компьютера на другой - скопировать её, используя нуль-модем (провод, соединяющий два компьютера напрямую). К компьютеру может быть подключен в один момент времени только один нуль-модем. Таким образом, с любого компьютера, где установлена программа, её можно скопировать на какой-то другой (но только на один) всего за один час. В БерГУ есть всего K нуль-модемных шнуров. Ваша задача по заданным N и K найти наименьшее время, необходимое для копирования программы на все имеющиеся компьютеры.
Входные данные
В первой строке записаны через пробел числа N и K (1 <= N <= 10^9, 1 <= K <= 10^9).
Выходные данные
Выведите единственное число - наименьшее время (в часах), необходимое для копирования новой программы на все компьютеры.
Пример
Ввод
8 3
Вывод
4
какие предложения по решению???
Вот что полусилось
var
n,k,h,i : longint;
begin
n := 8;
k := 3;
h := 0;
i := 1;
repeat
if i < k then inc(i,i)
else inc(i,k);
inc(h);
until i >= n;
writeln(h);
readln;
end.
Эта задача полностью решается на листочке без всякого компьютера. Получается формула, которая дает ответ. Мне кажется, моделировать в таких случаях процесс не очень правильно - достаточно просто запрограммировать формулу (хотя конкретно в этом случае даже и этого не нужно - с любыми данными все решается на листочке за пару минут).
Формула следующая:
M=[(N-2^([log2(K)]+1)+1)/K] + [log2(K)]+2
Здесь log2 означает логарифм по основанию 2, квадратные скобки - целая часть.
Так что на эту задачу никакого респекта нету...
Но я не поленился все же ее запрограммировать . Вот текст:
var
n,k,i,l,m,s:integer;
begin
ReadLn(n,k);
l:=Trunc(ln(k)/ln(2));
s:=1; for i:=0 to l do s:=s*2; Dec(s);
m:=Trunc((n-s)/k)+l+2;
WriteLn(m);
end.
2 копма одним проводом 3 часа соединять ? не хорошо ... При n = 2, k=1 твоя программа врет
Да, врет..
Только не прога, а формула. Я даже знаю, где врет. Я прокололся на краевых аффектах, на стыковке.
Сейчас перекушу - и подправлю...
Спасибо, Klem4
Ну вот и я поспел
Сделал табличку для разных N K.
Прога:
Готово
В формуле я наврал откровенно (спешил слишком - опаздывал в зал, играть ).
Вот правильная:
M=[(N-2^([log2(K)]+1))/K] + [log2(K)] + Sign((N-2^([log2(K)]+1))-[(N-2^([log2(K)]+1))/K]*K)
Не пугайтесь последнего слагаемого (с Sign), он всего лишь означает, что нужно добавить единицу, если деление в первом слагаемом было не нацело . В программе он реализован, ессно, простым оператором if.
Вот исправленный текст программы.
var
n,k,i,l,m,s:longint;
begin
ReadLn(n,k);
l:=Trunc(ln(k)/ln(2))+1;
s:=1; for i:=1 to l do s:=s*2;
m:=(n-s) div k;
if m*k<n-s then Inc(m);
Inc(m,l);
WriteLn(m);
end.