Solution #1: AC in 0.8 sec

Just calculate sum using Gauss's method.

Int[-1..1] f(x)dx ~= (5*f(-sqrt(3/5)) + 8*f(0) + 5*f(+sqrt(3/5))) / 9

Number of parts, N = (int)7e6

Length of part number i = (1e-4)*koef^i, where koef = 1 + x/N. Try some different x = 0.1 ... 10, and get AC =)

Solution #2: WA 11 on MSVC or AC on Java, Pascal, GNU C++

http://en.wikipedia.org/wiki/Residue_theorem says that we have to find all complex roots of the polynom.

I do not like exact formulas for degree 3 and 4.

There is numerical way to find all complex roots for any degree of polynom.

Just take point z = (0,0) and shift it to any direction in such a way that |P(z+shift)| < |P(z)|. Shift it while |P(z)| > eps. Now z is a root. This method works not only for polynoms, it works even for arbitrary "holomorphic function" (see Complex Analysis). Prove is smth like this http://en.wikipedia.org/wiki/Maximum_modulus_principle

The only thing that I need now -- to calculate f(z) for any complex z.

And using only "double" of Microsoft Visual C++ I can't. I have no enough precision and get WA 11 =(

Using BigDecimal (java), extended (pascal) or long double (GNU C/C++) this method gets AC (the task is from Petrozavodsk, so I have original tests).

P.S. 2 Admins: Ну сколько можно добавлять задачки с контестов, где у С++ программистов был под рукой long double, и это было важно. Даешь GNU C/C++!

Edited by author 27.10.2012 08:08

I found many other ways.
1)Monte Carlo - slow for this problem
2)Separation of real and complex roots. Can be used to solve this problem. Binary search for Re(z)=alfa, Re(z)=beta, Im(z)=gamma, Im(z)=delta
  Березин И.С., Жидков Н.П. Методы вычислений, Т.2. М.: ГИФМЛ, 1959.
3)Ferrari method.
  Куликов Л.Я. Алгебра и теория чисел
4)Barstow method. It's numeric iterative method.
  Саманчук_билеты_с_ответами.pdf
  Численные методы

I use combination from 3):
binary search for yo
then formulas

Edited by author 12.08.2018 21:04

https://en.wikipedia.org/wiki/Adaptive_quadrature

with Gaussian method to estimate value of definite integral:

approx_integrate(Func f, long double l, long double r) {
    long double A = sqrtl(3.0l/5.0l)/2, x1=0.5-A, x2 = 0.5+A;
    return (5*f(l*x1 + r*x2) + 8*f((l+r)/2) + 5*f(l*x2+r*x1))/18 * (r-l);
}

AC in 0.015.

That is, you don't even need to think to solve this problem.

Edited by author 16.02.2020 23:48