Check-in [fa5fb91aff]
Not logged in
Overview
SHA1 Hash:fa5fb91affdc936535440b8a3c719dc23f2e9728
Date: 2011-12-28 15:25:19
User: kinaba
Comment:1B
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | manifest
Tags And Properties
Changes
hide diffs side-by-side diffs patch

Deleted SRM/526.5-U/1B-U.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

Modified SRM/526.5-U/1B.cpp from [0722a98dbeb899c2] to [6a80b80254e8b111]. 


    24     24   using namespace std;
    25     25   typedef long long LL;
    26     26   typedef complex<double> CMP;
    27     27   
    28     28   class MagicBlizzard { public:
    29     29    double expectation(vector <int> range, vector <int> amount)
    30     30    {
    31         -  map<LL,int> ram;
           31  +  vector< pair<int,int> > ar;
    32     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);
           33  +   ar.push_back(make_pair(range[i], amount[i]));
    36     34   
    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;
           35  +  sort(ar.begin(), ar.end());
           36  +  double total = 0.0;
           37  +  int cnt = 0;
           38  +  for(int i=0; i<ar.size(); ++i)
           39  +   for(int _=0; _<ar[i].second; ++_)
           40  +    total += 2.0 * (cnt++) / (ar[i].first*2+1) / (ar[i].first*2+1) + 1;
           41  +  return total;
    79     42    }
    80     43   };
    81     44   
    82     45   // BEGIN CUT HERE
    83     46   #include <ctime>
    84     47   double start_time; string timer()
    85     48    { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
................................................................................

   126     89   CASE(4)
   127     90    int range_[] = {0,0,0,0,0,0,0,0,0,0};
   128     91      vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
   129     92    int amount_[] = {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000};
   130     93      vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
   131     94    double _ = 1.0E10;
   132     95   END
           96  +/*
   133     97   CASE(5)
   134         - int range_[] = {1};
           98  + int range_[] = ;
   135     99      vector <int> range(range_, range_+sizeof(range_)/sizeof(*range_));
   136         -   int amount_[] = {100};
          100  + int amount_[] = ;
   137    101      vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
   138         - double _ = 10000;
          102  + double _ = ;
   139    103   END
   140    104   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         - };
          105  + int range_[] = ;
   148    106      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         - };
          107  + int amount_[] = ;
   156    108      vector <int> amount(amount_, amount_+sizeof(amount_)/sizeof(*amount_));
   157         - double _ = -1;
          109  + double _ = ;
   158    110   END
   159         -
          111  +*/
   160    112   }
   161    113   // END CUT HERE

Fossil version [8d758d3715] 2012-10-22 12:48:04