0113. Roots of a Polynomial

Input file name:	roots.in
Output file name:	roots.out
Time limit:	5 s
Memory limit:	64 megabytes

Your task is to find real roots of a given non-zero polynomial.

Input file

The first line of the input file contains an integer number N (1 ≤ N ≤ 10) – degree of the polynomial. The next line contains N+1 integer numbers a_n a_n-1 …a₀ (the polynomial is a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀). They do not exceed 10⁶ by an absolute value. The last line of the input contains a single integer D (1 ≤ D ≤ 1000) – the required number of digits after decimal point in output. It is guaranteed that all roots of the polynomial are simple.

Output file

Output the real roots with D digits after decimal point in ascending order. Standard rounding rules apply. That is, if the exact D+1-th digit after decimal point is 4 or smaller, the D-th digit in output is rounded downards; otherwise upwards.

Examples:

roots.in	roots.out
1 -1 1 1	1.0

Source: Petrozavodsk Summer 2003. Primary Contest, Sunday, August 24
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version