• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/513-U/1A.cpp version [d303488aa6248209]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +static const int MODVAL = 1000000009;
           23  +
           24  +class YetAnotherIncredibleMachine { public:
           25  + int countWays(vector <int> platformMount, vector <int> platformLength, vector <int> balls)
           26  + {
           27  +  LL total = 1;
           28  +  for(int p=0; p<platformLength.size(); ++p)
           29  +  {
           30  +   vector< pair<int,int> > q;
           31  +   int len = platformLength[p];
           32  +   int pos = platformMount[p];
           33  +   q.push_back( make_pair(pos-len, pos) );
           34  +   for(int i=0; i<balls.size(); ++i)
           35  +    avoid( balls[i], q, len );
           36  +
           37  +   int cnt = 0;
           38  +   for(int i=0; i<q.size(); ++i)
           39  +    cnt += q[i].second - q[i].first + 1;
           40  +   total = total * cnt % MODVAL;
           41  +  }
           42  +  return int(total);
           43  + }
           44  +
           45  + void avoid(int x, vector< pair<int,int> >& q, int len)
           46  + {
           47  +  vector< pair<int,int> > q2;
           48  +  for(int i=0; i<q.size(); ++i)
           49  +   if( q[i].second+len < x || x < q[i].first )
           50  +    q2.push_back( q[i] );
           51  +   else {
           52  +    int L = q[i].first;
           53  +    int R = q[i].second;
           54  +    if( L<=x-len-1 )
           55  +     q2.push_back( make_pair(L, x-len-1) );
           56  +    if( x+1<=R )
           57  +     q2.push_back( make_pair(x+1, R) );
           58  +   }
           59  +  q.swap(q2);
           60  + }
           61  +};
           62  +
           63  +// BEGIN CUT HERE
           64  +#include <ctime>
           65  +double start_time; string timer()
           66  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           67  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           68  + { os << "{ ";
           69  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           70  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           71  +void verify_case(const int& Expected, const int& Received) {
           72  + bool ok = (Expected == Received);
           73  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           74  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           75  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           76  +#define END  verify_case(_, YetAnotherIncredibleMachine().countWays(platformMount, platformLength, balls));}
           77  +int main(){
           78  +
           79  +CASE(0)
           80  + int platformMount_[] = {7};
           81  +   vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_));
           82  + int platformLength_[] = {10};
           83  +   vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_));
           84  + int balls_[] = {3,4};
           85  +   vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_));
           86  + int _ = 3;
           87  +END
           88  +CASE(1)
           89  + int platformMount_[] = {1,4};
           90  +   vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_));
           91  + int platformLength_[] = {3,3};
           92  +   vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_));
           93  + int balls_[] = {2,7};
           94  +   vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_));
           95  + int _ = 1;
           96  +END
           97  +CASE(2)
           98  + int platformMount_[] = {4,4,4};
           99  +   vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_));
          100  + int platformLength_[] = {10,9,8};
          101  +   vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_));
          102  + int balls_[] = {1,100};
          103  +   vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_));
          104  + int _ = 27;
          105  +END
          106  +CASE(3)
          107  + int platformMount_[] = {0};
          108  +   vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_));
          109  + int platformLength_[] = {1};
          110  +   vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_));
          111  + int balls_[] = {0};
          112  +   vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_));
          113  + int _ = 0;
          114  +END
          115  +CASE(4)
          116  + int platformMount_[] = {100, -4215, 251};
          117  +   vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_));
          118  + int platformLength_[] = {400, 10000, 2121};
          119  +   vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_));
          120  + int balls_[] = {5000, 2270, 8512, 6122};
          121  +   vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_));
          122  + int _ = 250379170;
          123  +END
          124  +/*
          125  +CASE(5)
          126  + int platformMount_[] = ;
          127  +   vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_));
          128  + int platformLength_[] = ;
          129  +   vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_));
          130  + int balls_[] = ;
          131  +   vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_));
          132  + int _ = ;
          133  +END
          134  +CASE(6)
          135  + int platformMount_[] = ;
          136  +   vector <int> platformMount(platformMount_, platformMount_+sizeof(platformMount_)/sizeof(*platformMount_));
          137  + int platformLength_[] = ;
          138  +   vector <int> platformLength(platformLength_, platformLength_+sizeof(platformLength_)/sizeof(*platformLength_));
          139  + int balls_[] = ;
          140  +   vector <int> balls(balls_, balls_+sizeof(balls_)/sizeof(*balls_));
          141  + int _ = ;
          142  +END
          143  +*/
          144  +}
          145  +// END CUT HERE

Added SRM/513-U/1B.cpp version [d2075b0ec6259c1a]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +template<typename T>
           23  +struct DP2
           24  +{
           25  + const int N1, N2;
           26  + vector<T> data;
           27  + DP2(int N1, int N2, const T& t = T())
           28  +  : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           29  + T& operator()(int i1, int i2)
           30  +  { return data[ (i1*N2)+i2 ]; }
           31  + void swap(DP2& rhs)
           32  +  { data.swap(rhs.data); }
           33  +};
           34  +
           35  +class PerfectMemory { public:
           36  + double getExpectation(int N, int M)
           37  + {
           38  +  const int C = N*M;
           39  +  DP2<double> dp(C+1, C+1);
           40  +  for(int u=0; u<=C; ++u)
           41  +   for(int k=0; k<=C; ++k) if( (u+k)%2==0 && k+u<=C )
           42  +   {
           43  +    if( k > u )
           44  +    {
           45  +     dp(k,u) = 1 + dp(k-2,u);
           46  +    }
           47  +    else if( k == u )
           48  +    {
           49  +     if( k==0 && u==0 )
           50  +      dp(k,u) = 0;
           51  +     else
           52  +      dp(k,u) = 1 + dp(k-1, u-1);
           53  +    }
           54  +    else // k < u
           55  +    {
           56  +     dp(k,u) = 1;
           57  +
           58  +     double pFirstIsKnown = double(k) / u;
           59  +     double pSecondIsIt = double(1) / (u-1);
           60  +     if(k)
           61  +      dp(k,u) += pFirstIsKnown * dp(k-1, u-1);
           62  +     double pSecondIsThat = double(k) / (u-1);
           63  +     dp(k,u) += (1-pFirstIsKnown) * pSecondIsIt * dp(k, u-2);
           64  +     dp(k,u) += (1-pFirstIsKnown) * (1-pSecondIsIt-pSecondIsThat) * dp(k+2, u-2);
           65  +     dp(k,u) += (1-pFirstIsKnown) * pSecondIsThat * (1 + dp(k, u-2));
           66  +    }
           67  +//    cerr << k << " " << u << " " << dp(k,u) << endl;
           68  +   }
           69  +  return dp(0,C);
           70  + }
           71  +};
           72  +
           73  +// BEGIN CUT HERE
           74  +#include <ctime>
           75  +double start_time; string timer()
           76  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           77  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           78  + { os << "{ ";
           79  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           80  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           81  +void verify_case(const double& Expected, const double& Received) {
           82  + bool ok = (abs(Expected - Received) < 1e-9);
           83  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           84  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           85  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           86  +#define END  verify_case(_, PerfectMemory().getExpectation(N, M));}
           87  +int main(){
           88  +
           89  +CASE(0)
           90  + int N = 1;
           91  + int M = 2;
           92  + double _ = 1.0;
           93  +END
           94  +CASE(1)
           95  + int N = 2;
           96  + int M = 2;
           97  + double _ = 2.6666666666666665;
           98  +END
           99  +CASE(2)
          100  + int N = 2;
          101  + int M = 3;
          102  + double _ = 4.333333333333334;
          103  +END
          104  +CASE(3)
          105  + int N = 4;
          106  + int M = 4;
          107  + double _ = 12.392984792984793;
          108  +END
          109  +/*
          110  +CASE(4)
          111  + int N = 50;
          112  + int M = 50;
          113  + double _ = -1;
          114  +END
          115  +CASE(5)
          116  + int N = 2;
          117  + int M = 1;
          118  + double _ = 1.0;
          119  +END
          120  +*/
          121  +}
          122  +// END CUT HERE