2015年2月10日 星期二

2015/02/10 Codeforces 513C. Second price auction

/*
    math
    probability
    inclusion-exclusion
*/
// http://codeforces.com/problemset/problem/513/C
#include <iostream>
#include <cstdio>

using namespace std;

int N;
double L[10], R[10];

int main()
{
    scanf("%d", &N);

    for(int Ni = 0; Ni < N; Ni++)
        scanf("%lf %lf", &L[Ni], &R[Ni]);

    double Ans = 0;

    for(int i = 1; i <= 10000; i++)
    {
        for(int Ni = 0; Ni < N; Ni++)
        {
            if( i+1 > R[Ni] ) continue;

            double p1 = 1, p2 = 1;

            for(int Nj = 0; Nj < N; Nj++)
            {
                if( Ni == Nj ) continue;

                if( L[Nj] > i ) p1 = 0;
                if( L[Nj] > i-1 ) p2 = 0;

                p1 *= (min(R[Nj], (double)i)-L[Nj]+1 )/(R[Nj]-L[Nj]+1);
                p2 *= (min(R[Nj], (double)i-1)-L[Nj]+1 )/(R[Nj]-L[Nj]+1);
            }

            Ans += i*(p1-p2)*(R[Ni]-max(L[Ni], (double)i+1)+1 )/(R[Ni]-L[Ni]+1);
        }

        for(int Ni = 0; Ni < N; Ni++)
        {
            if( L[Ni] > i || i > R[Ni] ) continue;

            double p1 = 1, p2 = 1;

            for(int Nj = 0; Nj < Ni; Nj++)
            {
                if( L[Nj] > i-1 ) p1 = 0;
                if( L[Nj] > i-1 ) p2 = 0;

                p1 *= (min(R[Nj], (double)i-1)-L[Nj]+1 )/(R[Nj]-L[Nj]+1);
                p2 *= (min(R[Nj], (double)i-1)-L[Nj]+1 )/(R[Nj]-L[Nj]+1);
            }

            for(int Nj = Ni+1; Nj < N; Nj++)
            {
                if( Ni == Nj ) continue;

                if( L[Nj] > i ) p1 = 0;
                if( L[Nj] > i-1 ) p2 = 0;

                p1 *= (min(R[Nj], (double)i)-L[Nj]+1 )/(R[Nj]-L[Nj]+1);
                p2 *= (min(R[Nj], (double)i-1)-L[Nj]+1 )/(R[Nj]-L[Nj]+1);
            }

            Ans += i*(p1-p2)/(R[Ni]-L[Ni]+1);
        }

    }

    printf("%.10f\n", Ans);

}

沒有留言:

張貼留言