Задача 2 «Космическое поселение»

Формат входного файла

Входной файл содержит пять разделенных пробелами целых чисел: n, a, b, w и h (1 ≤ n, a, b, w, h ≤ 10¹⁸). Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.

Формат выходного файла

Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя. Если дополнительный защитный слой установить не удастся, требуется вывести число 0.

Примеры входных и выходных файлов

В первом примере можно установить дополнительный защитный слой толщиной 2 метра и разместить модули на поле, как показано на рисунке.

Во втором примере жилой отсек имеет в основании размер 5 × 5 метров, а поле – размер 6 × 6 метров. Добавить дополнительный защитный слой к модулю нельзя.

 Моделирование.

Общее количество модулей (n) разбивается на сомножители-количества модулей по вертикали (v) и горизонтали (g) n<=v*g (последний ряд может быть неполным). Возможны два варианта ориентации модулей: 1) a—w, b—h и 2) a—h, b—w. При этом очевидны формулы: (a+2d)*g<=w; (b+2d)*v<=h или (a+2d)*v<=h; (b+2d)*g<=w

Для полного решения этой задачи воспользуемся двоичным поиском. Заметим, что если можно установить защиту толщиной d, то можно установить и меньшую защиту.

Для проверки возможности установки защиты данной толщины переберем два варианта ориентации модулей. Пусть, например, модуль ориентирован так, что сторона длиной a ориентирована вдоль стороны поля длиной w. Тогда после установки защиты толщиной d вдоль этой стороны можно установить w div (a + 2d) модулей (при делении округлять следует вниз). Аналогично, вдоль другой стороны можно установить h div (b + 2d) модулей. В целом же на поле можно установить (w div (a + 2d)) × (h div (b + 2d)) модулей. Если это число больше или равно n, то защиту толщиной d или меньше установить можно, иначе нельзя.

program space;

   var

      fin, fout: text;

      a,b,w,h,l,r,m: longint;

      n,ad,ac,bd,bc: longint;

begin

   assign(fin, 'space.in');

   assign(fout, 'space.out');

   reset(fin);

   rewrite(fout);

   readln(fin, n,a,b,w,h);{ввод кол модулей, их разм, разм базы}

   close(fin);

   l:=0;{левая граница базы}

   if w<h then r:=w else r:=h; {правая граница базы}

   inc(r);

while l+1<r do {пока границы не пересекаются}

     begin

       m:=(l+r) div 2; {ширина защиты равна половине}

       ad:=a+2*m; bd:=b+2*m;{размеры модуля с защитой}

       ac:=w div ad; bc:= h div bd;{колич модулей}

                    {если общее число модулей не менее заданного, то}

                    {возвращаем результат, иначе уменьшаем защиту}

       if (ac*bc>=n) then l:=m else r:=m

     end;

   write(fout, l);

   close(fout);

 end.

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

       ac:=w div ad; bc:= h div bd;

заменить на строку:

       ac:=h div ad; bc:= w div bd; 

Отметим следующий аспект. Хотя, кажется, что при вычислении может произойти переполнение 64-битного типа, на самом деле это не так. В случае, если M больше ответа на задачу, переполнения не происходит, так как перемножаются числа, которые дают в произведении число, меньшее n. Если же M оказывается меньше ответа, то, благодаря структуре двоичного поиска, M меньше ответа не более чем вдвое, значит вычисляемое значение не превышает 4n и помещается в 64-битный тип данных.

Для решения подзадачи 1 достаточно перебрать все возможные значения толщины защиты линейным проходом.

Для решения подзадачи 2 требуется заметить, что при размещении модулей вдоль каждой стороны поля размещается не более n модулей, поэтому можно осуществить перебор, сколько модулей будет расположено вдоль стороны длиной w и проверить для такого количества модулей вдоль этой стороны, какая толщина защиты возможна.

Для решения подзадачи 3 можно развить эту мысль, заметив, что вдоль одной из сторон размещается не более sqrt(n) модулей, а значит можно ускорить перебор.