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

Added SRM/526.5-U/1A.cpp version [577cfc25d3b1c3b9]

            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  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class MagicCandy { public:
           29  + int whichOne(int n)
           30  + {
           31  +  int r = n;
           32  +  while( n > 1 ) {
           33  +   int sn = int(sqrt(n));
           34  +   r -= (sn*sn == n);
           35  +   n -= sn;
           36  +  }
           37  +  return r;
           38  + }
           39  +};
           40  +
           41  +// BEGIN CUT HERE
           42  +#include <ctime>
           43  +double start_time; string timer()
           44  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           45  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           46  + { os << "{ ";
           47  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           48  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           49  +void verify_case(const int& Expected, const int& Received) {
           50  + bool ok = (Expected == Received);
           51  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           52  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           53  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           54  +#define END  verify_case(_, MagicCandy().whichOne(n));}
           55  +int main(){
           56  +CASE(0)
           57  + int n = 5;
           58  + int _ = 5;
           59  +END
           60  +CASE(1)
           61  + int n = 9;
           62  + int _ = 7;
           63  +END
           64  +CASE(2)
           65  + int n = 20;
           66  + int _ = 17;
           67  +END
           68  +CASE(3)
           69  + int n = 5265;
           70  + int _ = 5257;
           71  +END
           72  +CASE(4)
           73  + int n = 20111223;
           74  + int _ = 20110741;
           75  +END
           76  +/*
           77  +CASE(5)
           78  + int n = 1;
           79  + int _ = 1;
           80  +END
           81  +CASE(6)
           82  + int n = ;
           83  + int _ = ;
           84  +END
           85  +CASE(7)
           86  + int n = ;
           87  + int _ = ;
           88  +END
           89  +*/
           90  +}
           91  +// END CUT HERE

Added SRM/526.5-U/1B.cpp version [0722a98dbeb899c2]

            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  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class MagicBlizzard { public:
           29  + double expectation(vector <int> range, vector <int> amount)
           30  + {
           31  +  map<LL,int> ram;
           32  +  for(int i=0; i<range.size(); ++i)
           33  +   ram[range[i]] += amount[i];
           34  +  vector< pair<LL,int> > ra(ram.begin(), ram.end());
           35  +  int all = accumulate(amount.begin(), amount.end(), 0);
           36  +
           37  +  double e = 0;
           38  +  for(int i=0; i<ra.size(); ++i)
           39  +  {
           40  +   LL r = ra[i].first;
           41  +   int a = ra[i].second;
           42  +   LL r_area = (2*r+1)*(2*r+1) - (i==0 ? 0 : (2*ra[i-1].first+1)*(2*ra[i-1].first+1));
           43  +   for(int sf=0; sf<=all; ++sf)
           44  +    e += rec(ra, i, sf, all) * r_area * sf * sf;
           45  +   all -= a;
           46  +  }
           47  +  return e;
           48  + }
           49  +
           50  + map<pair<int,int>, double> memo;
           51  + double rec(vector< pair<LL,int> >& ra, int i, int snow_fall, int all)
           52  + {
           53  +  if( i == ra.size() )
           54  +   return snow_fall == 0  ? 1.0 : 0.0;
           55  +  if( all < snow_fall )
           56  +   return 0.0;
           57  +
           58  +  pair<int,int> key(i, snow_fall);
           59  +  if( memo.count(key) )
           60  +   return memo[key];
           61  +
           62  +  LL r = ra[i].first;
           63  +  int a = ra[i].second;
           64  +  double p1 = double(1)/((2*r+1)*(2*r+1));
           65  +  double p0 = 1 - p1;
           66  +  // (p0 #0 + p1 #1)^a
           67  +  double csum = 0;
           68  +  double Cak = 1;
           69  +  for(int k=0; k<=min(a, snow_fall); ++k)
           70  +  {
           71  +   // coord of ^k
           72  +   // C(a,k) p1^k p0^(a-k)
           73  +   double c = Cak * pow(p1,k) * pow(p0,a-k);
           74  +   csum += c * rec(ra, i+1, snow_fall-k, all-a);
           75  +
           76  +   Cak  = Cak * (a-k) / (k+1);
           77  +  }
           78  +  return memo[key] = csum;
           79  + }
           80  +};
           81  +
           82  +// BEGIN CUT HERE
           83  +#include <ctime>
           84  +double start_time; string timer()
           85  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           86  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           87  + { os << "{ ";
           88  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           89  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           90  +void verify_case(const double& Expected, const double& Received) {
           91  + bool ok = (abs(Expected - Received) < 1e-9);
           92  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           93  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           94  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           95  +#define END  verify_case(_, MagicBlizzard().expectation(range, amount));}
           96  +int main(){
           97  +
           98  +CASE(0)
           99  + int range_[] = {1,0};
          100  +   vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
          101  + int amount_[] = {1,1};
          102  +   vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
          103  + double _ = 2.2222222222222223;
          104  +END
          105  +CASE(1)
          106  + int range_[] = {1,0};
          107  +   vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
          108  + int amount_[] = {2,1};
          109  +   vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
          110  + double _ = 3.666666666666667;
          111  +END
          112  +CASE(2)
          113  + int range_[] = {5,2,6,5};
          114  +   vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
          115  + int amount_[] = {1,2,2,3};
          116  +   vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
          117  + double _ = 8.46525111252384;
          118  +END
          119  +CASE(3)
          120  + int range_[] = {7,11,2,13,3,19,5,17};
          121  +   vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
          122  + int amount_[] = {16,8,4,15,12,9,10,6};
          123  +   vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
          124  + double _ = 98.55659436211914;
          125  +END
          126  +CASE(4)
          127  + int range_[] = {0,0,0,0,0,0,0,0,0,0};
          128  +   vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
          129  + int amount_[] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000};
          130  +   vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
          131  + double _ = 1.0E10;
          132  +END
          133  +CASE(5)
          134  + int range_[] = {1};
          135  +   vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
          136  +   int amount_[] = {100};
          137  +   vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
          138  + double _ = 10000;
          139  +END
          140  +CASE(6)
          141  + int range_[] = {
          142  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          143  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          144  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          145  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          146  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          147  + };
          148  +   vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
          149  + int amount_[] = {
          150  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          151  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          152  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          153  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          154  +  10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,
          155  + };
          156  +   vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
          157  + double _ = -1;
          158  +END
          159  +
          160  +}
          161  +// END CUT HERE