Задача
В тридевятом государстве новое соревнование. Организаторы поняли, что предыдущая задача «Низкая таблица» была слишком простой и решили усложнить жизнь нашей Аленушке. Она совсем растерялась и снова умоляет Вас о помощи. Итак, вот новое условие: каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, состоящую из $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.$
Ссылки
Код решения на Ideone
Related Images:
Для отправки комментария необходимо войти на сайт.