Editorial for tet: Bài tập về nhà dịp tết

Hiểu bài toán

Cho phương trình: q*sin(x) + r*cos(x) + s*tan(x) + t*x^2 + u = 0 với x trong đoạn [0, 1]. Các hệ số q, r, s, t, u được cho với các ràng buộc về dấu và giá trị tuyệt đối (khoảng -20 đến 20). Nhiệm vụ là tìm nghiệm x trong khoảng đã cho, làm tròn đến 6 chữ số thập phân, hoặc in ra 'No solution' nếu không có nghiệm.

Phân tích:

• Hàm số f(x) = q*sin(x) + r*cos(x) + s*tan(x) + t*x^2 + u.
• Trong khoảng [0, 1], sin(x) và cos(x) liên tục, tan(x) cũng liên tục và tăng dần từ 0 đến tan(1) ≈ 1.557. Hàm t*x^2 là đa thức bậc 2, liên tục. Do đó f(x) là hàm số liên tục trên [0, 1].
• Để tồn tại nghiệm trong (0, 1), cần có f(0) * f(1) <= 0 (theo định lý giá trị trung gian).
• Bài toán này yêu cầu tìm một nghiệm duy nhất (hoặc một giá trị làm tròn), nên phương pháp chia đôi (Binary Search) là phù hợp nhất vì độ chính xác cao và dễ cài đặt.

Các cách tiếp cận

Cách Chia đôi nhị phân (Binary Search)

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

long long q, r, s, t, u;

// Hàm tính giá trị của phương trình tại điểm x
double f(double x) {
    return q * sin(x) + r * cos(x) + s * tan(x) + t * x * x + u;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    while (cin >> q >> r >> s >> t >> u) {
        double l = 0, r_ = 1;
        double val_l = f(l);
        double val_r = f(r_);

        // Kiểm tra xem có nghiệm trong đoạn [0, 1] không
        // Nếu val_l * val_r > 0 => cùng dấu => không có nghiệm theo định lý GTTG
        if (val_l * val_r > 0) {
            cout << "No solution" << "\n";
            continue;
        }

        // Tiến hành chia đôi
        // Dừng lại khi độ dài đoạn đủ nhỏ (độ chính xác ~1e-9)
        while (r_ - l > 1e-9) {
            double mid = (l + r_) / 2;
            // Nếu đoạn [l, mid] chứa dấu đổi (nghĩa là f(l)*f(mid) <= 0),
            // thì nghiệm nằm trong [l, mid], ta thu hẹp về bên phải (r_ = mid).
            if (val_l * f(mid) <= 0) {
                r_ = mid;
                val_r = f(mid); // Cập nhật giá trị tại ranh giới mới (tối ưu)
            } else {
                l = mid;
                val_l = f(mid);
            }
        }

        // In kết quả làm tròn 6 chữ số
        cout << fixed << setprecision(6) << (l + r_) / 2 << "\n";
    }
    return 0;
}

• Time Complexity: O(T * log(1/epsilon)) với epsilon là độ sai số (~1e-9). Với T <= 2016, thời gian chạy rất nhanh.
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp và hiệu quả nhất.

1. Kiểm tra tồn tại nghiệm: Gọi f(x) là hàm phương trình. Tính f(0) và f(1). Nếu f(0) * f(1) > 0 (cùng dấu), phương trình không có nghiệm (vì hàm liên tục).
2. Thuật toán chia đôi: Nếu f(0) * f(1) <= 0, ta biết chắc chắn có ít nhất một nghiệm trong [0, 1]. Ta thực hiện lặp:
   • Chia đôi đoạn [l, r] thành [l, mid] và [mid, r].
   • Tính giá trị hàm số tại mid.
   • Xác định đoạn nào chứa điểm đổi dấu (dấu hiệu của nghiệm).
   • Thu hẹp đoạn tìm kiếm lại.
3. Độ chính xác: Lặp cho đến khi độ dài đoạn nhỏ hơn 1e-9 (đủ để làm tròn 6 số thập phân).
4. Lưu ý: Trong code mẫu có tối ưu việc tính f(l) và f(r) để tránh tính toán lại.

Cách Phương pháp Newton (Newton-Raphson)

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

long long q, r, s, t, u;

// Hàm f(x)
double f(double x) {
    return q * sin(x) + r * cos(x) + s * tan(x) + t * x * x + u;
}

// Đạo hàm f'(x)
// q*cos(x) - r*sin(x) + s/cos(x)^2 + 2*t*x
double df(double x) {
    return q * cos(x) - r * sin(x) + s / (cos(x) * cos(x)) + 2 * t * x;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        long long q, r, s, t, u;
        cin >> q >> r >> s >> t >> u;

        if (f(0) * f(1) > 0) {
            cout << "No solution\n";
            continue;
        }

        // Chọn điểm bắt đầu (x0)
        double x = 0.5;
        // Đảm bảo ban đầu x nằm trong [0, 1] và hàm đủ tốt

        // Lặp Newton
        for (int i = 0; i < 100; ++i) {
            double fx = f(x);
            double dfx = df(x);

            if (abs(dfx) < 1e-12) break; // Tránh chia cho 0

            double x_next = x - fx / dfx;

            // Nếu vượt quá [0, 1] hoặc hội tụ quá nhanh, ta có thể xử lý
            // nhưng với bài này đơn giản là cập nhật
            if (x_next < 0 || x_next > 1) {
                // Nếu bay ra ngoài, ta thử lại với điểm bắt đầu khác hoặc dùng chia đôi
                // Ở đây ta đơn giản là dừng hoặc dùng chia đôi làm fallback
                break;
            }

            if (abs(x_next - x) < 1e-9) break;
            x = x_next;
        }

        // Kiểm tra lại độ chính xác
        if (abs(f(x)) > 1e-6 && (x <= 0 || x >= 1)) {
             cout << "No solution\n";
        } else {
             cout << fixed << setprecision(6) << x << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(K) với K là số lần lặp (thường ~10-20 lần là đủ).
• Space Complexity: O(1)

Phương pháp Newton tìm điểm tiến tới nghiệm nhanh hơn (tốc độ bậc 2).

1. Đạo hàm: Cần tính đạo hàm của f(x): f'(x) = q*cos(x) - r*sin(x) + s/cos^2(x) + 2*t*x
2. Công thức lặp: x_{new} = x_{old} - f(x_{old}) / f'(x_{old}).
3. Điểm bắt đầu: Chọn x = 0.5 làm điểm xuất phát.
4. Rủi ro: Phương pháp Newton không đảm bảo hội tụ nếu điểm bắt đầu không đủ gần nghiệm, hoặc nếu đạo hàm sát 0. Trong bài toán này, do x bị giới hạn trong [0, 1], nếu phép lặp đưa x ra ngoài khoảng này, nó có thể thất bại. Vì vậy, Binary Search thường là lựa chọn an toàn hơn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Hàm số f(x) là hàm liên tục trên đoạn [0, 1] vì tan(x) liên tục tại mọi điểm trong khoảng này (cos(x) != 0).
• Định lý giá trị trung gian (Intermediate Value Theorem) là cơ sở để kiểm tra sự tồn tại nghiệm: nếu f(0) và f(1) trái dấu, chắc chắn có nghiệm.
• Bài toán yêu cầu độ chính xác 6 số thập phân, nên thuật toán chia đôi (Binary Search) với độ chính xác 1e-9 là quá đủ và đảm bảo an toàn.

Lỗi thường gặp

• Bỏ qua tan(0) = 0 và tan(1) ≈ 1.557. Nếu s (hệ số của tan) lớn, s*tan(x) có thể gây ra giá trị lớn hoặc biến đổi nhanh, nhưng vẫn đảm bảo liên tục.
• Lỗi tính toán số học: Với x gần 1, cos(x) vẫn dương (~0.54), không có lỗi chia cho 0.
• Không kiểm tra biên f(0) * f(1) > 0: Nếu cùng dấu, vẫn có khả năng có 2 nghiệm (vượt rào) nhưng trong bài này yêu cầu 'nghiệm' (số lượng không xác định), nhưng các giải pháp mẫu đều in 'No solution' nếu f(0)*f(1)>0. Điều này ngụ ý giả sử hàm không vượt rào quá nhiều hoặc chỉ tìm 1 nghiệm đơn giản.
• Sai độ chính xác: Dùng float thay vì double có thể gây sai lệch.