4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class BouncingBalls { public: 4fd800b3a8 2011-02-23 kinaba: double expectedBounces(vector <int> x, int T) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: sort(x.begin(), x.end()); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double total = 0; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int N = x.size(); 4fd800b3a8 2011-02-23 kinaba: for(int m=0; m<(1<<N); ++m) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector<bool> goLeft(N); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<N; ++i) 4fd800b3a8 2011-02-23 kinaba: goLeft[i] = ((1<<i)&m) != 0; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: total += num(x, goLeft, T); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: return total / (1<<N); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double num( const vector<int>& x, const vector<bool>& goLeft, int T ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int cnt = 0; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<x.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: for(int j=i+1; j<x.size(); ++j) 4fd800b3a8 2011-02-23 kinaba: if( !goLeft[i] && goLeft[j] && x[j]-x[i]<=2*T ) 4fd800b3a8 2011-02-23 kinaba: ++cnt; 4fd800b3a8 2011-02-23 kinaba: return cnt; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const double& Expected, const double& Received) { 4fd800b3a8 2011-02-23 kinaba: double diff = Expected - Received; if (diff < 0) diff = -diff; bool ok = (diff < 1e-9); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, BouncingBalls().expectedBounces(x, T));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {5, 8}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int T = 2; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.25; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {5, 8}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int T = 1; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {91, 857, 692, 54, 8679, 83, 792, 86, 9537, 913, 64, 592}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int T = 458; 4fd800b3a8 2011-02-23 kinaba: double _ = 11.5; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {75432}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int T = 386; 4fd800b3a8 2011-02-23 kinaba: double _ = 0.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int T = 3; 4fd800b3a8 2011-02-23 kinaba: double _ = 12.75; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {1}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int T = 100000000; 4fd800b3a8 2011-02-23 kinaba: double _ = 0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(6) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {10000000}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int T = 100000; 4fd800b3a8 2011-02-23 kinaba: double _ = 0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE