REALROOT - Real Roots


In this problem you are challenged to factor the real roots of polynomials.

You are rewarded points based on the number of testcases you solve.

Input

The first line contains the number of test cases, T.

The first line of each test case contains an integer N, the number of coeficients.

The second line contains the polynomial coeficients aN-1, ..., a1, a0 such that (P(x) = aN-1xN-1 + ... + a1x+ a0x0).

Output

The roots of the polynomial, in sorted order. That is all real numbers r0, r1, r2, ... such that P(r) = 0.

Constrains

  • T ≤ 20
  • N ≤ 20
  • All coeficients are in the inclusive range [-106,106]
  • The output precision must be at least 2 decimal digits
  • The roots must truly be real. No complex roots even if the imaginative part is very small.

Cases

  1. Same as the example
  2. ~3  random integer roots
  3. ~15 random integer roots
  4. ~10 Random interger coefficients
  5. ~10 Random floating point roots
  6. ~10 Random floating point coefficients
  7. Polynomials on the form p0=x, pk+1=(pk-ak)^2 e.g. ((x-3)^2-1)^2

Example

Input:
4
3
1 0 -2                 x2 - 2
3
1 0 1                  x2 + 1
4
-1 3 -3 1              -x3 + 3x2 - 3x + 1
7
1 -1 -9 13 8 -12 0     x6 - x5 - 9x4 + 13x3 + 8x2 - 12x
Output:
-1.414214 1.4142135    -sqrt(2), sqrt(2)
                       No real roots
1 1 1                  Triple root in x=1
-3 -1 0 1 2 2          Mixed integer roots

Notes

  1. All testcases are double checked using Mathematica with 30 digits of precision.
  2. Constrains are set such that most approaches should be fine using double working precision.

 

 

 

 


hide comments
caopeng: 2014-06-12 20:50:21

What about duplicated root and what about no real root and why the description has a0x


Added by:Thomas Dybdahl Ahle
Date:2012-06-06
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64