题目描述
As if powers of numbers were not cruel enough, Bessie's cruel math teacher has created yet another cruel assignment: Find the 'root' or 'zero' of a polynomial. All of these polynomials have a highest degree D (1 <= D <= 11) that is odd and have but a single solution in the range -1,000,000 <= X <= 1,000,000; for that solution, the polynomial's value when evaluated for X is very close or equal to to 0 in computer math. Given a polynomial with real number coefficients (-500 <= coef_i <= 500), find a value of X that is within 0.0005 of the value of X that will yield 0 when the polynomial is evaluated. Multiply that value of X by 1,000 and print it as an (unrounded) integer. By way of example, consider the cubic polynomial problem 1.5xxx - 10 = 0. Astute algebra students will quickly recognize a solution for this as xxx = 100/15 = 20/3 = 6.66666. To five decimal places, the exactly solution is 1.88207. For this task, the proper output would be 1882. The polynomial is expressed as the sum from i=0..D of coef_ix^i (where x^i means x to the i-th power). No answer will require more than six significant digits and each answer will be small enough that it is able to be incremented by 0.0001 in the 'double' precision floating point datatype without losing lots of precision. HINT: Find a strategy to narrow the search space each time you choose a new X value as a guess.
就像数字的力量不够残忍一样，贝西残酷的数学老师又创造了另一个残酷的任务：找到多项式的“根”或“零”。所有这些多项式都有一个最高阶d（1<=d<=11），它是奇数，只有一个在-1000000<=x<=1000000范围内的解；对于该解，在计算机数学中，当对x进行评估时，多项式的值非常接近或等于0。给定一个实数系数的多项式（-500<=coef_i<=500），找到一个x值，该值在x值的0.0005范围内，当计算多项式时，x值将产生0。将x的值乘以1000，然后将其打印为（未求整数）。举例来说，考虑三次多项式问题1.5xxx-10=0。机敏的代数学生会很快把这个问题的答案认作xxx=100/15=20/3=6.66666。到小数点后五位，精确解为1.88207。对于这个任务，正确的输出应该是1882。多项式表示为系数ix^i的i=0..d的和（其中x^i表示x的i次方）。任何答案都不需要超过6个有效数字，并且每个答案都足够小，可以在“双精度”浮点数据类型中增加0.0001，而不会损失很多精度。提示：每次选择一个新的x值作为猜测时，都要找到一个缩小搜索空间的策略。
输入
- Line 1: A single integer: D * Lines 2..D+2: Line i+2 contains a single real number: coef_i
*第1行：单个整数：d
*第2.d+2行：第i+2行包含一个实数：coef_i
输出
- Line 1: A single integer that is the truncated product of 1,000 and the X value that is closest to the X value that causes the polynomial to evaluate to 0
*第1行：一个整数，它是1000的截断积和x值的最接近x值，x值使多项式的值为0。
样例
输入 复制
3
-10.0
0.0
0.0
1.50
输出 复制
1882
提示
INPUT DETAILS: [As in the example from the text.] OUTPUT DETAILS: As in the text.
来源/分类
USACO 2009 February Bronze
