Задача
В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $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$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int main() { int n; cin >> n; long double s[n], h=0; for(int i=0; i<n; i++) { cin >> s[i]; h+=s[i]; } for(int i=0; i<n; i++) { cout.precision(4); cout << fixed << s[i]/h << " "; } return 0; } |
Решение задачи
Пусть $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}$