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

View as PDF

Submit solution


Points: 0.34 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Cruel Math Teacher II, USACO Feb 2009 Go
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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ẻ).


Comments

Please read the guidelines before commenting.


There are no comments at the moment.