Дипломы

Рассмотрим сначала частичное решение задачи, которое приходит в голову первым. Если перебирать всевозможные значения длины стороны квадратной доски x в порядке возрастания, то рано или поздно мы наткнемся на доску, пригодную для размещения n дипломов. Условие возможности размещения n дипломов, каждый их которых имеет размеры w*h эквивалентно выполнению следующего условия:

(x div w) * (x div h) >= n

Первое значение x, удовлетворяющее данному условию и будет ответом на задачу. Представим алгоритмическую модель данного решения:

  read(w,h,n)
  x=0
  while((x div w)*(x div h) < n) x=x+1;
  write(x)

Конечно, такое решение не вызывает сложности реализации. Однако, ограничения на размеры дипломов и их количество не позволяют решить задачу таким образом. Действительно, искомое значение может значительно превышать 10⁹, что позволит программе пройти не более половины тестов.

Для решения поставленной задачи можно применить метод бинарного поиска, который заключается в поиске решения на некотором отрезке с уменьшением его длины. Предположим, что нам известен отрезок поиска [l, r] искомого решения x. Первоначально мы можем взять l=1 и r=min(w,h)*n. Далее, следует рассмотреть возможность расположения дипломов для x=(l+r) div 2. Если такого размера доски достаточно, то дальнейший поиск следует продолжать на отрезке [l,x], в противном случае следует взять отрезок [x,r]. Процесс следует продолжить до максимального уменьшения отрезка поиска. Ответом будет служить значение правой границы отрезка. Описанная идея решения может выглядеть следующим образом:

  read(w,h,n)
  l = 1; r = 1018
  while( l < r){
    x = (r + l) div 2
    if ((x div w) * (x div h) >= n) r = x; else l = x+1
  }
  write(r)

Данный алгоритм работает очень быстро, так как уменьшение отрезка поиска происходит с экспонициальной скоростью, а сложность алгоритма равна O(ln(r-l)). Поскольку верхняя граница не может превышать значение 10¹⁸, то решение будет найдено не более чем за 63 итерации. Следует заметить, что целочисленные переменные могут превышать стандартный 4-байтовый целый тип, поэтому нужно использовать 8-байтовое целое (Int64 в Delphi или long long в Си).

Другой подход заключается в поиске решения по количеству дипломов вдоль одной из сторон. Пусть x - наименьшая из сторон, образующаяся при размещении n дипломов на минимально возможной доске. Тогда ответом на задачу будет служить либо w*x, либо h*x (в зависимости от стороны).

Для искомого значения x выполняется следующее ограничение: (x-1)*(x-1) < n, что позволяет перебрать всевозможные значения x и вычислить размеры доски для горизонтального и вертикального значения x. Среди всех таких значений необходимо найти наименьшую сторону квадратной доски.

Алгоритмическая реализация данного решения:

  read(w,h,n)
  x=0; m=1018
  while(x*x < n){
    x = x+1  
    y = (n-1) div x + 1
    m=min(m, max(w*x, h*y), max(w*y, h*x))
  }
  write(m)

[Обсуждение] [Все попытки] [Задача]