print1. Сортировка и поиск

printРазбор задачи 1366. Дипломы

Задача средней сложности.
Количество дипломов, которые можно разместить вдоль одной из сторон квадратной доски, не превосходит `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.
loading