Задача

В тридевятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из двух столбцов и двух строк. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Известно, что для правой верхней и левой нижней ячейки это значение равно $0.$ Но вот незадача: значения минимальных площадей для левой верхней — $S_{11}$ и правой нижней — $S_{22}$ ячеек могут быть какими угодно (в пределах разумного, конечно, хотя кто их этих сказочных персонажей разберет). Задача участников — начертить таблицу наименьшей высоты. Аленушка очень хочет победить, но она плохо знает математику, поэтому просит Вас помочь ей в этом непростом деле.

Входные данные

В единственной строке содержатся два натуральных числа: $S_{11}, \ S_{22},$ не превышающие $10^{14}.$

Выходные данные

Минимальная высота таблицы в магических миллиметрах, округленная до ближайшего меньшего целого.

Тесты

Код программы

Решение задачи

Пусть $h$ и $l$ — высота и ширина таблицы соответственно. Тогда ее площадь $S=hl.$ В силу того, что $l=1,$ задача о нахождении минимальной высоты таблицы сводится к нахождению ее минимальной площади. Обозначим высоту $i$-ой строки $h_i$, ширину $j$-го столбца $l_j$, а площадь ячейки таблицы, находящейся на пересечении $i$-ой строки и $j$-го столбца — $S_{ij}.$ Тогда $$\begin{multline}S = S_{11} +S_{12}+S_{21}+S_{22}=S_{11}+l_2 h_1+l_1 h_2+S_{22}= \\ =S_{11}+S_{11} \frac{l_2}{l_1} +S_{22} \frac{l_1}{l_2}+S_{22} = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22},\end{multline}$$ где $y=\frac{l_2}{l_1}.$ Зафиксируем теперь $S_{11}$ и $S_{22}$ и рассмотрим функцию площади $S \left( y \right ) = S_{11}+S_{11} y+S_{22} y^{-1}+S_{22}.$ Найдем наименьшее значение данной функции. $\frac{\mathrm{d} S \left( y \right )}{\mathrm{d} y} = S_{11}-\frac{S_{22}}{y^{2}}.$ Приравнивая производную функции к нулю, находим, что функция имеет единственную стационарную точку $y_{0} = \sqrt{\frac{S_{22}}{S_{11}}}.$ Легко убедиться, что $y_0$ – точка глобального минимума, тогда $\min\limits_{y \in D\left(S\right)}S\left( y \right ) = S \left(y_0\right) = S_{11} + S_{22} + 2 \cdot \sqrt{S_{11} \cdot S_{22}} = \left( \sqrt{S_{11}} + \sqrt{S_{22}} \right )^2.$ Очевидно теперь, что минимальное значение площадь таблицы будет принимать при $S_{11}={S_{11}}’, \ S_{22}={S_{22}}’$ где ${S_{11}}’, \ {S_{22}}’$ – данные в условии минимальные значения площадей соответствующих ячеек. Отсюда имеем минимальное значение высоты таблицы $h_{min}=\left( \sqrt{{S_{11}}’} + \sqrt{{S_{22}}’} \right )^2.$

Ссылки

Код решения на Ideone

Related Images: