Задача
В тридевятом государстве новое соревнование. Организаторы поняли, что предыдущая задача «Низкая таблица» была слишком простой и решили усложнить жизнь нашей Аленушке. Она совсем растерялась и снова умоляет Вас о помощи. Итак, вот новое условие: каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из $n$ строк и $n$ столбцов. В каждой строке и столбце выбрано по одной ячейке, для которой указана минимальная площадь, которую должна занимать эта ячейка — $S_i$ для ячейки, расположенной в $i$-ой строке. Остальные могут иметь площадь $0.$ Задача участников аналогична предыдущей — начертить таблицу наименьшей высоты.
Входные данные
В первой строке содержится единственное натуральное число $n \leqslant 20.$
Во второй строке содержатся $n$ натуральных чисел $S_{1}, \ldots, S_{n}$, не превышающие $10^{4}.$
Выходные данные
Минимальная высота таблицы в магических миллиметрах, округленная до ближайшего меньшего целого.
Тесты
| Входные данные | Выходные данные |
|
3 1 2 3 |
17191 |
|
19 2899 338 8846 5896 3325 9199 6493 211 7878 6083 2074 8493 2889 3743 133 5725 9453 7890 3594 |
1548340398 |
|
18 3823 5708 1356 9979 8801 5310 2123 4575 566 5039 9367 26 1966 6540 1514 7193 7667 994 |
1252560358 |
|
8 8283 8769 3568 869 8285 4494 7185 4519 |
340953967 |
|
9 6375 3059 6206 4221 6027 2064 6278 1347 996 |
301905233 |
|
17 2765 8226 4472 1139 9080 675 3712 7735 9566 223 8899 9716 6594 9631 8871 6176 313 |
1414903854 |
|
10 2654 7458 2284 8767 6061 1149 7243 607 757 8532 |
385237635 |
|
6 6429 9121 9490 7035 6352 2021 |
231968881 |
|
8 52 6380 8169 5689 367 2403 3112 2850 |
185108459 |
|
2 8063 3128 |
21235115 |
|
9 9226 7811 4279 68 5976 1418 9721 6784 8580 |
418145363 |
|
13 8987 3714 247 679 1416 3489 1501 7654 2164 9101 7347 4043 3289 |
591377417 |
|
18 9349 9854 4308 1799 1501 8647 6300 9379 1123 7369 1164 3083 1207 2754 2933 1051 8566 4016 |
1324052855 |
|
3 1311 2984 9564 |
35581065 |
|
16 3460 6135 8911 5656 5496 5463 9566 8473 7575 7444 2717 8241 9868 6698 849 7118 |
1576424119 |
|
15 2264 4988 4454 726 17 9279 422 7916 698 5780 2517 9352 6291 2954 4775 |
763779068 |
|
10 3625 7189 773 7283 2952 7865 588 1670 1013 2982 |
305484098 |
|
18 2741 2630 4163 4926 9431 2212 6978 1607 9489 6746 4947 3333 3144 4809 3352 207 1919 1918 |
1207862952 |
|
5 4320 8413 1175 4527 1519 |
88794894 |
|
6 9534 5380 2500 683 4281 4803 |
145815522 |
|
14 1458 1341 6248 8840 8877 6891 409 5853 6726 6401 4932 9007 5710 745 |
905996755 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <cmath> #include <climits> using namespace std; int main(){ int n; cin >> n; double sqrtOfHeight = 0; for(int i = 0; i < n; i++){ int square; cin >> square; sqrtOfHeight += sqrt(square); } cout << (unsigned long long) (1000 * sqrtOfHeight * sqrtOfHeight); return 0; } |
Решение задачи
Поменяем местами строки таблицы так, чтобы ячейки, для которых указана минимальная площадь, лежали на главной диагонали. От этого не изменится ни ширина, ни высота таблицы. Обозначим эти ячейки $S_{ii}$ для ячейки, лежащей на пересечении $i$-ой строки и $i$-ого столбца.
Докажем, что минимальная площадь указанной в условии таблицы $S = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}} \right )^2.$ Воспользуемся методом математической индукции.
База индукции. Случай при $n=2$ был доказан здесь.
Предположение индукции. Пусть утверждение верно $\forall n \leq k, \ k \geq 2.$
Шаг индукции. Докажем, что утверждение верно для $n = k+1.$ Рассмотрим подтаблицу $T_1$ нашей таблицы $T$, которая состоит из первых $k$ столбцов и $k$ строк исходной таблицы. По предположени индукции ее минимальная площадь $S_{T_1} = \left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2.$ Теперь можем рассматривать таблицу $T$ как таблицу, состоящую из двух строк и двух столбцов, так, что таблица $T_1$ будет верхней левой ячейкой. Тогда, учитывая утверждение, доказанное в базе индукции находим минимальную площать таблицы $T$ $$\begin{multline}S_{T} = \left (\sqrt{S_{T_1}}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left (\sqrt{\left (\sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}} \right )^2}+\sqrt{S_{k+1k+1}} \right ) ^ 2 = \\ = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{kk}}+\sqrt{S_{k+1k+1}}\right )^2.\end{multline}$$ Что и требовалось доказать. Заметим, что для тривиального случая $n = 1$ формула также остается в силе. Пусть $h$ высота таблицы, а $l$ — ее ширина. Учитывая, что по условию $l = 1,$ а $S = hl,$ находим, что минимальное значение высоты таблицы $h_{min} = \left ( \sqrt{S_{11}} + \sqrt{S_{22}} + \ldots + \sqrt{S_{nn}}\right )^2.$
В данном доказательстве упущен один маленький момент: ширина таблицы 1 метр. А это значит, что переход от k к (k+1) просто добавлением столбика и строки к оптимальной таблице невозможен. Они просто не поместятся. А так Вы вывели формулу для площади квадратной таблицы. По индукции.
Не совсем. В доказательстве формулы для минимальной площади нигде не используется то, что ширина таблицы равна 1. Т. е. мы просто находим минимальную площадь таблицы при заданных минимальных площадях диагональных элементов, а затем, уже используя, что ширина таблицы равна 1, утверждаем, что высота таблицы численно равна ее площади.
Вот именно, что не использовалось. А должно бы.
Если Вы посмотрите на доказательство базы индукции, то увидите, что на вопрос, является ли площадь минимально допустимой отвечает соотношение ширин столбцов таблицы, а именно, если обобщить его на таблицу $n$-ого порядка получаем: $\frac{l_i}{l_j} = \sqrt{\frac{S_{ii}}{S_{jj}}}.$ Такое соотношение можно сделать, какой бы ни была ширина таблицы. Т. е. при добавлении $k+1$-ого столбца мы меняем абсолютную ширину первых $k$ столбцов, но так, чтоб выписанное выше оставалось в силе, и это будет нам гарантировать минимальность площади таблицы $T_1,$ и вот образуется место для добавления нового столбца и строки.
Теперь согласен. Решение выглядит неочевидным, но оно очень похоже на правильное.