НачалоПодразделы
Другие разделы
| 2. Комбинаторные объекты |
| 3. Поиск в глубину |
| 4. Поиск в ширину |
| 6. Динамическое программирование |
Дата и время
22/12/2024 21:08:05
1. Сортировка и поиск
Применение и виды сортировки Разбор задачи 1126. ICQ Разбор задачи 163. Анаграммы Разбор задачи 50. Закраска прямой Разбор задачи 1366. Дипломы
Разбор задачи 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.
