Начало
Соревнования
2. Дипломы
Задача средней сложности.
Количество дипломов, которые можно разместить вдоль одной из сторон квадратной доски, не превосходит `sqrt(n)`. Если вдоль вертикальной стороны квадратной доски размещено `a` дипломов, а вдоль горизонтальной – `b` дипломов, тогда общее число дипломов составляет `a*b\ ≤\ n`. Если оба числа a и b больше `sqrt(n)`, тогда `a*b\ >\ n`. Получили противоречие, следовательно, либо `a\ ≤\ sqrt(n)`, либо `b\ ≤\ sqrt(n)`.
Мы должны для всех `k` от 1 до `sqrt(n)` определить размер доски при размещении `k` дипломов вдоль вертикальной или вдоль горизонтальной стороны квадрата.
uses math;
var n,w,h,s,m:int64;
k,sn:integer;
begin
read(w,h,n);
sn:=trunc(sqrt(n))+1;
s:=(w+h)*n;
for k:=1 to sn do
begin
m:=(n+k-1) div k; { целочисленное деление с округлением вверх }
s:=min(s,max(k*w,m*h)); { k дипломов по горизонтали }
s:=min(s,max(m*w,k*h)); { k дипломов по вертикали }
end;
writeln(s);
end.
Другой вариант – с помощью двоичного поиска найти наименьшую длину стороны квадрата, которая позволит разместить `n` дипломов.
uses math;
var n,w,h,a,b,c:int64;
k:extended;
begin
read(w,h,n);
a:=0; { в квадрате со стороной a не должно гарантированно поместиться n дипломов }
b:=n*max(w,h); { в квадрате со стороной b должно гарантированно поместиться n дипломов }
while a<b do
begin
c:=(b+a) div 2; { пробная длина стороны квадрата посредине между a и b }
k:=c div w; { предотвращение переполнения }
k:=k*(c div h); { при вычислениях }
{ k - количество дипломов, которое поместится в квадрате со стороной c }
if k>=n then b:=c { изменяем верхнюю границу }
else a:=c+1; { изменяем нижнюю границу }
end;
{ a=b }
writeln(a);
end.
