Đổi biến ~a_i=x_i^2+c~ thì sẽ bỏ được điều kiện ~a_i\ge c~.

Ta viết lại bài toán dưới dạng:

• Cực tiểu hoá: ~f(x_1,x_2,\ldots,x_n)=\displaystyle\sum_{i=1}\sum_{j=i+1} \frac{a_i}{a_j}~

• Dưới điều kiện: ~\displaystyle g(x_1,x_2,\ldots,x_n)=\sum a_i=s~

Ta sẽ sử dụng phương pháp nhân tử Lagrange. Tính các đạo hàm riêng: $$\begin{align*} \displaystyle \frac{\partial f}{\partial x_i}&=\left(\sum_{j>i}\frac{a_i}{a_j}\right)^\prime + \left(\sum_{j\lt i}\frac{a_j}{a_i}\right)^\prime = 2x_i\sum_{j>i}\frac{1}{a_j}-2x_i\sum_{j\lt i}\frac{a_j}{a_i^2} \\ \displaystyle \frac{\partial g}{\partial x_i}&=\sum (a_i)^\prime =2x_i \end{align*}$$ Điểm dừng ~(x_1,x_2,\ldots,x_n)~ thoả mãn hệ phương trình: $$\begin{cases} \displaystyle 2x_i\left (\sum_{j>i}\frac{1}{a_j}-\sum_{j\lt i}\frac{a_j}{a_i^2}\right)=\lambda\cdot 2x_i\\ g(x_1,x_2,\ldots,x_n)=s \end{cases}$$ Có thể thấy rằng với ~x_i=0~ thì phương trình thứ nhất thoả mãn mà đáp án tối ưu thoả mãn ~a_1\le a_2\le \ldots\le a_n~, suy ra tồn tại một tiền tố ~p~ thoả mãn ~x_1=x_2=\ldots=x_p=0~ và phần hậu tố còn lại có ~x_i\neq 0~.

Ta cố định ~p~, xét ~p\lt i\lt n~, ta có: $$\begin{align*} &\sum_{j>i}\frac{1}{a_j}-\sum_{j\lt i}\frac{a_j}{a_i^2}=\sum_{j>i+1}\frac{1}{a_j}-\sum_{j\lt i+1}\frac{a_j}{a_{i+1}^2}\\ \Leftrightarrow &\frac{1}{a_{i+1}}+\frac{a_i}{a_{i+1}^2}=\sum_{j\lt i}a_j\cdot\left(\frac{1}{a_i^2}-\frac{1}{a_{i+1}^2}\right) \\ \Leftrightarrow &\frac{a_i+a_{i+1}}{a_{i+1}^2}=\sum_{j\lt i}a_j \cdot\frac{(a_{i+1}-a_i)(a_i+a_{i+1})}{a_i^2a_{i+1}^2}\\ \Leftrightarrow &\sum_{j\lt i}a_j \cdot \frac{a_{i+1}-a_i}{a_i^2}=1\quad (*) \end{align*}$$ Đặt ~\displaystyle s_i=\sum_{j\le i} a_j~, ta có: $$\begin{align*} (*)&\Leftrightarrow s_{i-1}\cdot \frac{s_{i+1}+s_{i-1}-2s_i}{(s_i-s_{i-1})^2}=1\\ &\Leftrightarrow s_{i-1}s_{i+1}+s_{i-1}^2-2s_{i-1}s_i=s_{i-1}^2-2s_{i-1}s_i+s_i^2 \\ &\Leftrightarrow \frac{s_i}{s_{i-1}}=\frac{s_{i+1}}{s_i} \end{align*}$$ Từ đây suy ra bắt đầu từ vị trí ~p~, dãy ~s~ tạo thành một cấp số nhân với công bội ~k~ thoả mãn: $$s = s_n=s_p\cdot k^{n-p} = pc\cdot k^{n-p}\Leftrightarrow k=\left(\frac{s}{pc}\right)^{\frac{1}{n-p}}$$ Từ đây ta có thuật toán là duyệt ~p~, xác định ~k~ và kiểm tra điều kiện ~a_{p+1}=pc(k-1)\ge c~, sau đó cập nhật kết quả với ~\displaystyle f(p)=\frac{p(p-1)}{2}+\frac{n-p}{k-1}~.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, c, s;
    cin >> n >> c >> s;
    if (n * c == s) {
        for (int i = 0; i < n; ++i) cout << c << ' ';
        return 0;
    }
    vector<double> f(n, 1e18);
    for (int p = 1; p < n; ++p) {
        double k = pow(1.0 * s / (p * c), 1.0 / (n - p));
        if (p * c * (k - 1) >= c) {
            f[p] = 1.0 * p * (p - 1) / 2 + 1.0 * (n - p) / (k - 1);
        }
    }
    int p = min_element(f.begin(), f.end()) - f.begin();
    double k = pow(1.0 * s / (p * c), 1.0 / (n - p));
    for (int i = 1; i <= p; ++i) cout << c << ' ';
    double lst = p * c * (k - 1);
    for (int i = p + 1; i <= n; ++i) {
        cout << fixed << setprecision(6) << lst << ' ';
        lst *= k;
    }
}