Псевдо строчная таблица

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$ $12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$ $10$
$2 \ 3 \ 5$
$4 \ 4$ $96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$ $6$
$2 \\ 2 \\ 2$
$5 \ 3$ $430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$ $216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$ $945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$ $5$
$5$
$3 \ 7$ $210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$ $202$
$100 \ 1 \\ 100 \ 1$

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

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

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения

Строчная таблица

Задача

В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $1 \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Задача участников — начертить таблицу наименьшей высоты и вычислить ширину каждой ячейки. Алиса очень хочет победить, но она плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит натуральное число $n, \ (1 \leqslant n \leqslant 100).$ Вторая строка содержит $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

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

Тесты

Входные данные Выходные данные
$3$ $0.1333 \ 0.3333 \ 0.5333$
$2 \ 5 \ 8$
$6$ $0.0736 \ 0.2638 \ 0.3313 \ 0.0736 \ 0.1963 \ 0.0613$
$12 \ 43 \ 54 \ 12 \ 32 \ 10$
$2$ $0.3333 \ 0.6667$
$1 \ 2$
$3$ $0.3333 \ 0.3333 \ 0.3333$
$10 \ 10 \ 10$
$7$ $0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.2500$
$1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 2$
$1$ $1.0000$
$2$
$4$ $0.5102 \ 0.1735 \ 0.2653 \ 0.0510$
$100 \ 34 \ 52 \ 10$
$2$ $0.9901 \ 0.0099$
$100 \ 1$
$6$ $0.0702 \ 0.2515 \ 0.3158 \ 0.0351 \ 0.1287 \ 0.1988$
$12 \ 43 \ 54 \ 6 \ 22 \ 34$
$2$ $0.5000 \ 0.5000$
$2 \ 2$
$10$ $0.0182 \ 0.0364 \ 0.0545 \ 0.0727 \ 0.0909 \ 0.1091 \ 0.1273 \ 0.1455 \ 0.1636 \ 0.1818$
$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10$
$3$ $0.0098 \ 0.9804 \ 0.0098$
$1 \ 100 \ 1$

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

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

Пусть $h=\displaystyle\frac{1}{\gamma}$ — высота таблицы, а $x_1, \ x_2, \ \cdots, \ x_{n-1}, \ 1-x_1-x_2- \cdots -x_{n-1}$ – ширина каждой клетки. Тогда $\displaystyle\frac{x_1}{\gamma} \geqslant s_1, \ \displaystyle\frac{x_2}{\gamma} \geqslant s_2, \ \cdots, \ \displaystyle\frac{x_{n-1}}{\gamma} \geqslant s_{n-1}, \ \displaystyle\frac{1-x_1-x_2- \cdots -x_{n-1}}{\gamma} \geqslant s_n.$ Получаем $x_1 \geqslant s_1\gamma, \ x_2 \geqslant s_2\gamma, \ \cdots, \ x_{n-1} \geqslant s_{n-1}\gamma, \ 1-x_1-x_2- \cdots -x_{n-1} \geqslant s_n\gamma.$
Сделаем из неравенств равенства: $x_1=s_1\gamma+\varepsilon_1, \ x_2=s_2\gamma+\varepsilon_2, \ \cdots, \ x_{n-1}=s_{n-1}\gamma+\varepsilon_{n-1}.$
Имеем
$1-(s_1\gamma+\varepsilon_1)-(s_2\gamma+\varepsilon_2)- \cdots -(s_{n-1}\gamma+\varepsilon_{n-1}) \geqslant s_n\gamma \\
1 \geqslant (s_1+s_2+ \cdots +s_{n-1}+s_n)\gamma+\varepsilon_1+\varepsilon_2+ \cdots +\varepsilon_{n-1}
\\
\gamma \leqslant \displaystyle\frac{1-\varepsilon_1-\varepsilon_2- \cdots -\varepsilon_{n-1}}{s_1+s_2+ \cdots +s_{n-1}+s_n}.$
Максимальное значение $\gamma$ достигается при $\varepsilon_1=\varepsilon_2= \cdots =\varepsilon_{n-1}=0.$ Следовательно $\gamma \leqslant \displaystyle\frac{1}{s_1+s_2+ \cdots +s_{n-1}+s_n},$ а $h=s_1+s_2+ \cdots +s_{n-1}+s_n.$ Тогда ширина каждой ячейки будет равняться $\displaystyle\frac{s_i}{h}$

Ссылки

Код решения