Задача 2 «Космическое поселение»
Формат входного файла
Входной файл содержит пять разделенных пробелами целых чисел: n, a, b, w и h (1 ≤ n, a, b, w, h ≤ 1018). Гарантируется, что без дополнительного защитного слоя все модули можно разместить в поселении описанным образом.
Формат выходного файла
Выходной файл должен содержать одно целое число: максимальную возможную толщину дополнительного защитного слоя. Если дополнительный защитный слой установить не удастся, требуется вывести число 0.
Примеры входных и выходных файлов
|
space.in |
space.out |
|
11 2 3 21 25 |
2 |
|
1 5 5 6 6 |
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) модулей, а значит можно ускорить перебор.
