Cô giáo dạy toán, phần II

Xem dạng PDF

Gửi bài giải


Điểm: 0,34 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
Cruel Math Teacher II, USACO Feb 2009 Go
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tính lũy thừa là chưa đủ, cô giáo Thảo còn có bài tập "khủng" cho bạn nữa, đó là tìm nghiệm của phương trình có dạng đa thức.

Cho đa thức bậc ~d~ lẻ với các hệ số thực: $$f(x) = a_0x^0+a_1x^{1}+\ldots+a_dx^d$$

Nghiệm của đa thức là một số thực ~X~ sao cho ~f(X)~ xấp xỉ ~0~ hoặc bằng ~0~, với độ chính xác tương đối.

Biết rằng đa thức trên có duy nhất 1 nghiệm thực ~X~ trong khoảng ~[-10^6,10^6]~. Bạn hãy tìm nghiệm ~X~ này và in ra số nguyên có giá trị bằng ~[1000X]~, với ~[X]~ là phần nguyên của nghiệm thực ~X~.

Ví dụ, đa thức bậc ~3~: ~1.5x^3 - 10 = 0~ có 1 nghiệm ~X = 1.88207~. Như vậy phải ghi ra ~1882~.

Input đảm bảo đáp án không vượt quá kiểu số nguyên 64-bit.

Input

Dòng đầu tiên là số tự nhiên lẻ ~d \leq 11~.

Dòng thứ hai là ~d+1~ số thực ~a_0,a_1,\ldots,a_d~, ~|a_i| \leq 500~, theo đúng thứ tự này, là các hệ số của đa thức ~f(x)~.

Output

In ra đáp án theo yêu cầu của bài toán.

Sample Input

3
-10.0 0.0 0.0 1.50

Sample Output

1882

Note

Hãy tìm 1 chiến lược để thu hẹp khoảng của nghiệm cần tìm kiếm mỗi lần "thử" 1 giá trị ~X~ nào đó (chú ý điều kiện ~d~ lẻ).


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -1
    NguyenHungBG  đã bình luận lúc 5, Tháng 8, 2023, 18:03

    Đây là một bài mình thấy rất hay về toán học và xử lí số thực. Spoiler Alert!

    Lời giải liên quan đến hàm số liên tục.

    Nếu hàm y = f(x) liên tục trên đoạn [a, b] và f(a), f(b) trái dấu. khi đó khoảng (a, b) chứa ít nhất một nghiệm của phương trình f(x) = 0.

    Gọi m là trung điểm, chặt nhị phân trong đoạn [a, b]. Có 3 trường hợp xảy ra:

    Nếu f(m) = 0, m là một nghiệm của phương trình.

    Nếu f(m) trái dấu f(a), phương trình có nghiệm nằm trong khoảng (a, m).

    Nếu f(m) trái dấu f(b), phương trình có nghiệm nằm trong khoảng (m, b).

    Hãy thử nghĩ tiếp trước khi xem lời giải.