Should i use long ariphmetics???
How should i correctly calculate the value of polynom for given variable?

Interesting question. I think that is important to understand distinction between root and point of small value. Now i am solving 1503 but have wa9. I have program for finding all roots in complex plane but can't improve precision from 0.0001 to 0.000001. For it would enough to have float with 30 right digits. Question depend also on position of testmakers. I think that if we have
a +0.000001*i complex root then answer a+-0.000001 must be right. To approach root near 0.000001 we must have 30 digits int results.

I've calculated precision up to last digit of standard pascal's type Extended, so, my precision should be up to 1e-16. But still WA #9...

Edited by author 03.11.2006 14:45

example:
x^5==0
x0=0-root;
x1=0.00001- bad value
but x1^5=1.0*E-25- very small

My reqursive approach of solving equation P(x)=0 is: to solve equation P'(x)=0, and then binary search on all the intervals, whose ends are roots of equation P'(x)=0. So, I haven't problems with "excess psevdoroots", but still WA #9...

Eqution P'(x)=0 is  also bad because P'(x) may has multiple roots. It should start from d(N-1)P/dx=0 which is linear and go up applying binary search on each stage. If root multiple then on previous stage it was simple and is founded. As result all candidates for roots will be found with hight precision. The problem is to make choice which of them are roots of  P(x)=0. Here we must use existence theoren of Sturm . Simplest variant is P(a)*P(b)<0=> x in [a,b]. I used with success long aritmetic and now on WA16.

AC finally.
In Java only using my BigFraction baseg on BigInt
I implemented famous Stourm's theorem which garantees
absolutely correct considering multiple roots
without any eps and so on.
But in question what degree of found multiple root
I needed in unknown constant h which garantes that if
d/dtP(t)!=0 and P(t)==0 than in (t-h,t+h) d/dtP(t)!=0.
I taken h=1e-12. In other words I think that if
P(t)==0 and in (t-h,t+h) exists t1 such that d/dtP(t1)==0
then t==t1.

h=1e-6 works also.

Edited by author 08.12.2007 19:43

I think it's impossible to calculate P(x) with
given accuracy (10^-6), without long arrithmetics

i do it more simply.
int r[n] - array of int which represent roots P'(x)
int i,j;
for (i=0;i<n;i++)
    for (j=0;j<n;j++) if (i!=j) trytofindroot(P,r[i],r[j]);

Edited by author 04.11.2006 15:41

Fortunatelly, it is possible... :)
I don't know what in fact is the problem with test #9 but I had WA10 and the problem with is was the equal roots. If you concern about these particular cases, you won't have the need of long arrithmetics (I don't wish long float arithmetics to anyone!!!)

And what problem with my approach, when P'(x) has multiple roots? At some stage we make binsearch from x to x, where x - multiple root, and, as a result, we'll get still 3 new roots of P(x). For input
5
1
0
0
0
0
0

my program outputs

0
0
0
0
0

I think, it is right answer. Isn't it?

Edited by author 06.11.2006 00:54

Vedernikoff Sergey: yes, this output is correct.
Alexander Prudaev: I had a precision error but eliminated it by checking whether the given function has zero value for the borders of the searching interval.

p.s. I am sorry for the late post. I haven't seen your posts (it might be usefull the admins to create an informational/notificational system)

Edited by author 17.01.2007 06:59

Edited by author 24.01.2007 02:22

Edited by author 24.01.2007 02:23

I solve it problem with long double!!

Did you use Ferrary method or Euler solution for polynomial of fourth degree? I understood that you don't find root using general methods because of your time.