Artifact 9180662f25d62836a12c4545c257ee3a342283ae

• File SRM/TCO9-1/B.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;

class KthProbableElement {
public:
  double probability(int M, int lowerBound, int upperBound, int N, int K) 
  {
    double dp1[101][101]={0}, dp2[101][101], (*P)[101]=dp1, (*Q)[101]=dp2;

    P[0][0] = 1.0;
    for(int i=0; i<M; ++i)
    {
      memset( Q, 0, sizeof(double)*101*101 );
      for(int a=0; a<=i; ++a)
        for(int b=0; a+b<=i; ++b)
        {
          Q[a+1][b] += P[a][b] * (N-lowerBound) / (upperBound-lowerBound+1);
          Q[a][b+1] += P[a][b] * 1 / (upperBound-lowerBound+1);
          Q[a][b]   += P[a][b] * (upperBound-N) / (upperBound-lowerBound+1);
        }
      swap(P, Q);
    }

    double p = 0.0;
    for(int a=0; a<=M; ++a)
      for(int b=0; a+b<=M; ++b)
        if( a<K && K<=a+b )
          p += P[a][b];
    return p;
  }
};

// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const double &Expected, const double &Received) { double diff = Expected - Received; if (diff < 0) diff = -diff; if (diff < 1e-9) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
  int M = 1; 
  int lowerBound = 1; 
  int upperBound = 10; 
  int N = 3; 
  int K = 1; 
  double RetVal = 0.1; 
  return verify_case(RetVal, KthProbableElement().probability(M, lowerBound, upperBound, N, K)); }
int Test_(Case_<1>) {
  int M = 3; 
  int lowerBound = 1; 
  int upperBound = 2; 
  int N = 2; 
  int K = 2; 
  double RetVal = 0.5; 
  return verify_case(RetVal, KthProbableElement().probability(M, lowerBound, upperBound, N, K)); }
int Test_(Case_<2>) {
  int M = 3; 
  int lowerBound = 1; 
  int upperBound = 3; 
  int N = 2; 
  int K = 2; 
  double RetVal = 0.48148148148148145; 
  return verify_case(RetVal, KthProbableElement().probability(M, lowerBound, upperBound, N, K)); }
int Test_(Case_<3>) {
  int M = 10; 
  int lowerBound = 1; 
  int upperBound = 10; 
  int N = 1; 
  int K = 10; 
  double RetVal = 1.0000000000000003E-10; 
  return verify_case(RetVal, KthProbableElement().probability(M, lowerBound, upperBound, N, K)); }
int Test_(Case_<4>) {
  int M = 4; 
  int lowerBound = 61; 
  int upperBound = 65; 
  int N = 62; 
  int K = 3; 
  double RetVal = 0.15200000000000002; 
  return verify_case(RetVal, KthProbableElement().probability(M, lowerBound, upperBound, N, K)); }

template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE