CRUELL2 - Cô giáo dạy toán, phần II
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Tính lũy thừa là chưa đủ, cô giáo còn có bài tập "khủng" nữa, đó là tìm nghiệm của phương trình có dạng đa thức. Biết rằng các đa thức này có bậc cao nhất là D (1 <= D <= 11) , D là số lẻ và đa thức chỉ có duy nhất 1 nghiệm X trong khoảng -1,000,000 <= X <= 1,000,000; X là nghiệm nếu nó làm cho giá trị của đa thức xấp xỉ 0 hoặc đúng bằng 0.
Cho đa thức cùng với các hệ số thực (-500 <= hệ số bậc i <= 500), hãy tìm giá trị X với độ chính xác đến 0.0005. Khi tìm được X rồi thì ghi ra phần nguyên của X*1,000 (chú ý không làm tròn X).
Ví dụ, đa thức bậc 3: 1.5*x^3 - 10 = 0 có 1 nghiệm X = 1.88207. Như vậy phải ghi ra 1882.
Các bậc của đa thức là tính từ 0..D.
Không có đáp án nào có nhiều hơn 6 chữ số có nghĩa và mỗi đáp án đều đủ nhỏ để tăng 0.0001 (với kiểu dữ liệu double) thì cũng không làm mất đi tính chính xác.
GỢI Ý: 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 đó.
Dữ liệu
* Dòng 1: Một số nguyên: D
* Dòng 2..D+2: Dòng i+2 chứa 1 số thực: hệ số của bậc i
Kết quả
* Dòng 1: Một số nguyên là phần nguyên của 1,000 nhân với nghiệm X tìm được.
Ví dụ
Dữ liệu:
3
-10.0
0.0
0.0
1.50
Kết quả:
1882
- Người up: hphong
- Nguồn bài: USACO Feb,2009