잔인한 수학 선생님, II

수를 거듭제곱하는 것만으로는 충분히 잔인하지 않다는 듯, Bessie의 잔인한 수학 선생님은 더 잔인한 과제를 냈습니다. 바로 다항식의 근(영점)을 찾는 것입니다.

이 다항식들은 모두 홀수인 최고 차수 $D$ ($1 \le D \le 11$)를 가지며, 구간 $-1{,}000{,}000 \le X \le 1{,}000{,}000$ 안에 실수해가 정확히 하나만 존재합니다. 그 해에서 다항식의 값은 부동소수점 연산 기준으로 $0$에 매우 가깝거나 정확히 $0$입니다.

실수 계수 ($-500 \le coef_i \le 500$)로 이루어진 다항식이 주어지면, 실제 근과의 오차가 $0.0005$ 이내인 $X$ 값을 구하세요. 그 $X$에 $1{,}000$을 곱한 뒤, 반올림하지 않고 정수 부분만 잘라(0 방향으로 절삭하여) 출력합니다.

예를 들어 삼차식 $1.5 \cdot x^3 - 10 = 0$을 생각해 봅시다. 이 식의 해는 $x^3 = 100/15 = 20/3 = 6.6666\ldots$을 만족하므로 $x = 1.88207\ldots$이고, 따라서 정답은 $1882$입니다.

다항식은 $\sum_{i=0}^{D} coef_i \cdot x^i$이며, 여기서 $x^i$는 $x$의 $i$제곱을 뜻합니다.

어떤 정답도 유효숫자 6자리를 넘지 않으며, 모든 정답은 배정밀도 부동소수점에서 $0.0001$만큼 더해도 정밀도가 크게 손상되지 않을 만큼 작습니다.

힌트: 새로운 $X$ 추정값을 고를 때마다 탐색 구간이 줄어들도록 하세요.

• 첫째 줄: 정수 $D$ 하나.
• 둘째 줄부터 $D+2$째 줄까지: $i+2$째 줄에 실수 $coef_i$ 하나 ($i = 0, 1, \ldots, D$).

• 첫째 줄: 근에 가장 가까운 $X$ 값에 $1{,}000$을 곱한 뒤 0 방향으로 절삭한 정수 하나.