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ẻ).
Comments