GFSSOC '15 Fall S3 - System(0);

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Calvin has almost finished his math 135 exam, but doesn't want to do the last section. Luckily, he remembered to bring his microscopic Raspberry Pi™, so he can contact his trusty deputy (that's you) to do all the problems for him. Instead of solving the problems one by one, you decide it's easier to solve the general problem. This general problem is as follows: Given a polynomial in the form c_n x^n+c_{n-1} x^{n-1}+\dots+c_1 x+c_0 that has only one real x intercept, find the single root of the function. By peeking at the exam beforehand, Calvin saw that none of the polynomials had any imaginary roots. Also, since the professors don't really care, your answer only needs to be accurate to 6 decimal places.

Input Specification

Line 1: One integer, n (1 \le n \le 1\,000).

Next n+1 lines: the (n-i)^{th} (0 \le i \le n) of these lines has one real number c_i which describes the coefficient for the term (0 < |c_i| \le 10^{310}). Coefficients will all be given in scientific notation with 12 significant digits (your programming language of choice should be able to read it directly without any issues). 10384.43 for example will be given to you as 1.038443000000e+004.

Output Specification

Output one line, the answer. Answers within an absolute or relative error of 10^{-6} of the actual answer will be accepted.

Sample Input


Sample Output


Explanation for Sample

The input describes the quadratic function 4x^2+4x+1. While he was waiting for you (slowpoke), Calvin, having done too much CS went for the obvious brute force solution: the quadratic formula!

\displaystyle \begin{align*}
x &= \frac{-b \pm \sqrt{b^2-4ac}}{2a} \\
&= \frac{-4 \pm \sqrt{4^2 - 4 \times 4 \times 1}}{2 \times 4} \\
&= \frac{-4}{8} \\
&= -0.5

Solving for x, we find the single real root -0.5.


  • 1
    Kirito  commented on Sept. 3, 2016, 12:02 a.m.

    0 < |c_i| < 10^{310} Is the 10^{310} part intentional?

    • 5
      aCookieBreak  commented on Sept. 9, 2016, 1:23 p.m.

      It appears that a double has an upper bound of 1.8e+308.

  • 4
    fifiman  commented on April 3, 2015, 10:36 p.m.

    Is my WA on test 9 due to precision?

    • 5
      awaykened  commented on April 3, 2015, 10:40 p.m.