И опять «низкая» таблица

Задача

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

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

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

Поменяем местами строки таблицы так, чтобы ячейки, для которых указана минимальная площадь, лежали на главной диагонали. От этого не изменится ни ширина, ни высота таблицы. Обозначим эти ячейки $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

«Низкая» таблица

Задача

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

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

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

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

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

Тесты

Входные данные Выходные данные
1 2 5828
466 1194 3151849
8067 2659 19988861
5125 6755 23647646
3317 2652 11900840
25 9293 10282002
7081 7189 10282002
8192 1042 15077308
6795 1568 14891264
680 4510 8692456
9107 4760 27035040
7095 7846 29863113
6142 3794 19590583
9347 3639 24650258
8495 5394 27427394
2179 8718 19613999
1187 778 3886963
71 5592 6923209
100000000000000 100000000000000 400000000000000000

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

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

Пусть $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

e-olymp 5868. A xor B

Задача

На стандартный вход подаются 2 натуральных числа [latex]A[/latex] и [latex]B[/latex]. Выведите на стандартный вывод результат применения к ним операции побитового исключающего или.

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

2 натуральных числа [latex]A, B ≤ 10^9[/latex] в десятичной системе счисления, разделённые пробелом.

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

Выведите результат указанной операции над числами.

Тесты

# Входные данные Выходные данные
1 3 7 4
2 12 11 7
3 15 9 6
4 8 10 2
5 10 10 0

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

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

Введем два числа и применим операцию исключающего или.В языке программирования С++ данная операция выглядим так как показано в коде программы.

Ссылки

e-olymp
ideone

e-olymp 7944. Площадь прямоугольника

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex]  [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 [latex]1[/latex] [latex]1[/latex] [latex]1[/latex]
2 [latex]2[/latex] [latex]4[/latex] [latex]8[/latex]
3 [latex]511[/latex] [latex]428[/latex] [latex]218708[/latex]
4 [latex]5555[/latex] [latex]4444[/latex] [latex]24686420[/latex]
5 [latex]11[/latex] [latex]11[/latex] [latex]121[/latex]

 

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

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

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

e-olymp 920. Использование функций min и max

Задача

Задано три вещественных числа [latex]x, y[/latex] и [latex]z[/latex]. Определить [latex]\min\left(\max\left(x,y\right), \max\left(y,z\right), x+y+z\right)[/latex], воспользовавшись вспомогательными функциями для вычисления минимального и максимального элементов из двух заданных.

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

В одной строке задано три вещественных числа [latex]x, y[/latex] и [latex]z[/latex]. Значения чисел не превышают по модулю [latex]100[/latex].

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

Вывести ответ с двумя десятичными знаками.

Тесты

# Входные данные Выходные данные
1  5 6 7  7.00
2  1.05 2.25 -2.15  1.15
3  3 3 3  3
4  8.85 5.67 7.33  7.33
5  12 -15 13  10

 

Алгоритм решения

  1. Находим максимум из [latex]x[/latex] и [latex]y[/latex].
  2. Находим максимум из [latex]y[/latex] и [latex]z[/latex].
  3. Находим минимум из найденных максимумов.
  4. Находим минимум из найденного минимума и суммы данных чисел.

Условие задачи можно найти на e-olymp
Код решения — ideone

e-olymp 949. Двузначное из четырёхзначного

Задача

Из заданного четырёхзначного натурального числа образовать двузначное, состоящее из его средних цифр.

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

Одно четырёхзначное натуральное число.

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

Полученное двузначное число.

Тесты

# Входные данные Выходные данные
1 4765 76
2 7999 99
3 2514 51
4 9423 42
5 8234 23

 

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

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

Первым делом мы используем деление на 10 с присваиванием, чтобы избавиться от последней цифры числа. Дальше используем остаток от деления на 100, чтобы избавиться от первой цифры числа.

Ссылки

Задача на сайте e-olymp

Код решения Ideone