Check-in [226a376552]
Not logged in
Overview
SHA1 Hash:226a3765521cb6298455c69ff02e880f1469bfdd
Date: 2011-12-28 14:46:22
User: kinaba
Comment:526.5
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

Name change from from SRM/526.5-U/1B.cpp to SRM/526.5-U/1B-U.cpp.

Deleted 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

Added SRM/526.5-U/2A.cpp version [85387e3cdd5302ba] 


            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 MagicStonesStore { public:
           29  + string ableToDivide(int n)
           30  + {
           31  +  return n==1 ? "NO" : "YES";
           32  + }
           33  +};
           34  +
           35  +// BEGIN CUT HERE
           36  +#include <ctime>
           37  +double start_time; string timer()
           38  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           39  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           40  + { os << "{ ";
           41  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           42  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           43  +void verify_case(const string& Expected, const string& Received) {
           44  + bool ok = (Expected == Received);
           45  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           46  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           47  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           48  +#define END  verify_case(_, MagicStonesStore().ableToDivide(n));}
           49  +int main(){
           50  +
           51  +CASE(0)
           52  + int n = 1;
           53  + string _ = "NO";
           54  +END
           55  +CASE(1)
           56  + int n = 2;
           57  + string _ = "YES";
           58  +END
           59  +CASE(2)
           60  + int n = 3;
           61  + string _ = "YES";
           62  +END
           63  +CASE(3)
           64  + int n = 5;
           65  + string _ = "YES";
           66  +END
           67  +CASE(4)
           68  + int n = ;
           69  + string _ = ;
           70  +END
           71  +CASE(5)
           72  + int n = ;
           73  + string _ = ;
           74  +END
           75  +
           76  +}
           77  +// END CUT HERE

Added SRM/526.5-U/2C.cpp version [71780af0d20da0b9] 


            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 MagicNaming { public:
           29  + int maxReindeers(string magicName)
           30  + {
           31  +  return rec(magicName, 0, "");
           32  + }
           33  +
           34  + map<pair<int,string>, int> memo;
           35  + int rec(const string& s, int i, const string& last)
           36  + {
           37  +  if( i == s.size() )
           38  +   return 0;
           39  +  pair<int,string> key(i, last);
           40  +  if( memo.count(key) )
           41  +   return memo[key];
           42  +
           43  +  // a+b <= b+a,  b+c <= c+b
           44  +  int score = -1;
           45  +  for(int e=i+1; e<=s.size(); ++e) {
           46  +   string t = s.substr(i, e-i);
           47  +   if( last+t <= t+last ) {
           48  +    int ss = rec(s, e, t);
           49  +    if( ss != -1 )
           50  +     score = max(score, 1 + ss);
           51  +   }
           52  +  }
           53  +  return memo[key] = score;
           54  + }
           55  +};
           56  +
           57  +// BEGIN CUT HERE
           58  +#include <ctime>
           59  +double start_time; string timer()
           60  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           61  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           62  + { os << "{ ";
           63  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           64  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           65  +void verify_case(const int& Expected, const int& Received) {
           66  + bool ok = (Expected == Received);
           67  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           68  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           69  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           70  +#define END  verify_case(_, MagicNaming().maxReindeers(magicName));}
           71  +int main(){
           72  +
           73  +CASE(0)
           74  + string magicName = "aba";
           75  + int _ = 2;
           76  +END
           77  +CASE(1)
           78  + string magicName = "babbaba";
           79  + int _ = 2;
           80  +END
           81  +CASE(2)
           82  + string magicName = "philosophersstone";
           83  + int _ = 5;
           84  +END
           85  +CASE(3)
           86  + string magicName = "knuthmorrispratt";
           87  + int _ = 7;
           88  +END
           89  +CASE(4)
           90  + string magicName = "acrushpetrtourist";
           91  + int _ = 7;
           92  +END
           93  +CASE(5)
           94  + string magicName = "zzzzz";
           95  + int _ = 5;
           96  +END
           97  +/*
           98  +CASE(6)
           99  + string magicName = ;
          100  + int _ = ;
          101  +END
          102  +CASE(7)
          103  + string magicName = ;
          104  + int _ = ;
          105  +END
          106  +*/
          107  +}
          108  +// END CUT HERE

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