UVa OJ Board

You may find this O(n) algorithm interesting (no need to know how many color there are).
http://citeseer.ist.psu.edu/494676.html

Thanks. I got it.

How do you prove the greedy is always correct?

Yes, you are right. My AC output is the same as yours.

I used a nlogn algorithm for finding median. Is there any better algorithm?

AC Finally. Thank you all. Just "guess" the constant.

The first product is ln2 but i still don't know what is the value of ln(1+x^2)/(x+1)dx

I read a paper and it said that :
For a n-gon (n>=5), there is no way to dissect it into m triangles with equal area with gcd(n,m)=1.

AC now after using string to read input!!!

My output has the same number of moves as your output. Could you please check what's wrong with my code : #include <iostream> #define MAXK 1005 #define MAXP 15 #define MAXQ 15 using namespace std; int m,n,k,p,q,x0,y0,k0; bool c[MAXK][MAXK]; int pq[MAXK*(MAXP+1)*(2*MAXQ+1)*3]; int d[MAXK],a[MAXK]; in...

Could someone give me the output for this input? 20 31 31 9 4 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 ...

In the case where n is odd, it should be :

i change your program to compute the condition for all 3 edges of the triangle and it got AC: bool valid(double a, double b, double c, double d){ double theta, alpha, eta, xx; if( a - d > eps ) return false ; theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ; alpha = acos( a/d ); // since D[j] = 2*r ; et...

It's the same as my AC code and i only considers flight (i,j) where i<j.

theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ; alpha = acos( a/D[j] ); // since D[j] = 2*r ; I believe that you have used the wrong angle. I used this one theta = acos( ( a*a + b*b - c*c )/(2*a*b) ) ; alpha = asin(c/D[j] ); if (alpha-theta>-eps) ... And you used it for all 3 edges of the triangle.[/...