Overview
| SHA1 Hash: | 96fdfab500d575209c9b6eb814917ae0f4ec5f7f |
|---|---|
| Date: | 2011-03-20 00:13:59 |
| User: | kinaba |
| Comment: | 500 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/500/1A.cpp version [86caa30b4834e1a2]
> 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 class MafiaGame { public: > 23 double probabilityToLose(int N, vector <int> decisions) > 24 { > 25 vector<int> vc; > 26 { > 27 map<int,int> voteCnt; > 28 for(int i=0; i<decisions.size(); ++i) > 29 voteCnt[decisions[i]] ++; > 30 for(map<int,int>::iterator it=voteCnt.begin(); it!=voteC > 31 vc.push_back( it->second ); > 32 } > 33 const int MAX = *max_element(vc.begin(), vc.end()); > 34 if( MAX == 1 ) > 35 return 0.0; > 36 > 37 const int GotMAX = count(vc.begin(), vc.end(), MAX); > 38 for(int k=GotMAX; k; k=(N-k*MAX)%k) > 39 if( k == 1 ) > 40 return 1.0/GotMAX; > 41 return 0.0; > 42 } > 43 }; > 44 > 45 // BEGIN CUT HERE > 46 #include <ctime> > 47 double start_time; string timer() > 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 49 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 50 { os << "{ "; > 51 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 52 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 53 void verify_case(const double& Expected, const double& Received) { > 54 bool ok = (abs(Expected - Received) < 1e-9); > 55 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 56 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 57 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 58 #define END verify_case(_, MafiaGame().probabilityToLose(N, decisions));} > 59 int main(){ > 60 > 61 CASE(0) > 62 int N = 3; > 63 int decisions_[] = {1, 1, 1}; > 64 vector <int> decisions(decisions_, decisions_+sizeof(decisions_)/sizeo > 65 double _ = 1.0; > 66 END > 67 CASE(1) > 68 int N = 5; > 69 int decisions_[] = {1, 2, 3}; > 70 vector <int> decisions(decisions_, decisions_+sizeof(decisions_)/sizeo > 71 double _ = 0.0; > 72 END > 73 CASE(2) > 74 int N = 20; > 75 int decisions_[] = {1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0} > 76 vector <int> decisions(decisions_, decisions_+sizeof(decisions_)/sizeo > 77 double _ = 0.0; > 78 END > 79 CASE(3) > 80 int N = 23; > 81 int decisions_[] = {17, 10, 3, 14, 22, 5, 11, 10, 22, 3, 14, 5, 11, 17}; > 82 vector <int> decisions(decisions_, decisions_+sizeof(decisions_)/sizeo > 83 double _ = 0.14285714285714285; > 84 END > 85 /* > 86 CASE(4) > 87 int N = ; > 88 int decisions_[] = ; > 89 vector <int> decisions(decisions_, decisions_+sizeof(decisions_)/sizeo > 90 double _ = ; > 91 END > 92 CASE(5) > 93 int N = ; > 94 int decisions_[] = ; > 95 vector <int> decisions(decisions_, decisions_+sizeof(decisions_)/sizeo > 96 double _ = ; > 97 END > 98 */ > 99 } > 100 // END CUT HERE
Added SRM/500/1B.cpp version [5fcb34f3f46b9954]
> 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 class FractalPicture { public: > 23 double getLength(int x1, int y1, int x2, int y2) > 24 { > 25 return rec(1, x1, y1, x2, y2); > 26 } > 27 > 28 double rec(int i, int x1, int y1, int x2, int y2) > 29 { > 30 x1 = clip<-27,+27>(x1); > 31 x2 = clip<-27,+27>(x2); > 32 y1 = clip< 0,+81>(y1); > 33 y2 = clip< 0,+81>(y2); > 34 > 35 if( i == 501 ) > 36 return 0; > 37 if( x1<=-27 && 27<=x2 && y1<=0 && 81<=y2 ) > 38 return 81 + (500-i)*54; > 39 if( x2<=-27 || 27<=x1 || y2<=0 || 81<=y1 ) > 40 return 0; > 41 double L0 = (x1<=0 && 0<=x2 ? clip<0,54>(y2)-clip<0,54>(y1) : 0) > 42 x1=x1*3, x2=x2*3, y1=(y1-54)*3, y2=(y2-54)*3; > 43 double L1 = rec(i+1, x1, y1, x2, y2); > 44 double L2 = rec(i+1, y1, x1, y2, x2); > 45 double L3 = rec(i+1, y1, -x2, y2, -x1); > 46 return L0 + (L1+L2+L3)/3; > 47 } > 48 > 49 template<int m, int M> > 50 int clip(int v) { return max(m, min(v, M)); } > 51 }; > 52 > 53 // BEGIN CUT HERE > 54 #include <ctime> > 55 double start_time; string timer() > 56 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 57 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 58 { os << "{ "; > 59 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 60 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 61 void verify_case(const double& Expected, const double& Received) { > 62 bool ok = (abs(Expected - Received) < 1e-9); > 63 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 65 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 66 #define END verify_case(_, FractalPicture().getLength(x1, y1, x2, y2));} > 67 int main(){ > 68 > 69 CASE(0) > 70 int x1 = -1; > 71 int y1 = 0; > 72 int x2 = 1; > 73 int y2 = 53; > 74 double _ = 53.0; > 75 END > 76 CASE(1) > 77 int x1 = 1; > 78 int y1 = 1; > 79 int x2 = 10; > 80 int y2 = 10; > 81 double _ = 0.0; > 82 END > 83 CASE(2) > 84 int x1 = -10; > 85 int y1 = 54; > 86 int x2 = 10; > 87 int y2 = 55; > 88 double _ = 21.0; > 89 END > 90 CASE(3) > 91 int x1 = 14; > 92 int y1 = 45; > 93 int x2 = 22; > 94 int y2 = 54; > 95 double _ = 2999.0; > 96 END > 97 CASE(4) > 98 int x1 = -28; > 99 int y1 = 44; > 100 int x2 = -16; > 101 int y2 = 62; > 102 double _ = 6992.0; > 103 END > 104 CASE(5) > 105 int x1 = 0; > 106 int y1 = 80; > 107 int x2 = 1; > 108 int y2 = 81; > 109 double _ = 332; > 110 END > 111 } > 112 // END CUT HERE
Added SRM/500/1C.cpp version [45a3476fb0482db3]
> 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 = 500500573; > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(LL x):val(x%MODVAL) {} > 29 }; > 30 mint operator+(mint x, mint y) { return x.val+y.val; } > 31 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } > 32 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } > 33 mint POW(mint x, int e) { > 34 mint v = 1; > 35 for(;e;x=x*x,e>>=1) > 36 if(e&1) > 37 v=v*x; > 38 return v; > 39 } > 40 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } > 41 > 42 class ProductAndSum { public: > 43 int getSum(int p2, int p3, int p5, int p7, int S) > 44 { > 45 // Precomputing n!, 1/n!, and 111...111 > 46 vector<mint> FACT(2501), FACT_INV(2501), ONES(2501); > 47 FACT[0] = FACT_INV[0] = 1; > 48 ONES[0] = 0; > 49 for(int n=1; n<FACT.size(); ++n) > 50 { > 51 FACT[n] = FACT[n-1] * n; > 52 FACT_INV[n] = 1 / FACT[n]; > 53 ONES[n] = ONES[n-1]*10 + 1; > 54 } > 55 > 56 mint answer = 0; > 57 > 58 // Exhaustive search over the number of 4,6,8,9s : at most 33*50 > 59 for(int v8=0; v8*3<=p2; ++v8) > 60 for(int v4=0; v4*2+v8*3<=p2; ++v4) > 61 for(int v9=0; v9*2<=p3; ++v9) > 62 for(int v6=0; v6+v4*2+v8*3<=p2 && v6+v9*2<=p3; ++v6) > 63 { > 64 // then, the number of 1,2,3s are computable > 65 int v[] = {-1, -1, p2-v8*3-v4*2-v6, p3-v9*2-v6, v4, p5, > 66 { > 67 int v1 = S; > 68 for(int i=2; i<=9; ++i) > 69 v1 -= i * v[i]; > 70 if( v1 < 0 ) > 71 continue; > 72 v[1] = v1; > 73 } > 74 int N = accumulate(v+1, v+10, 0); > 75 > 76 // Now, let's compute the sum of all integers, who have > 77 > 78 // It can be calculated as follows: > 79 // Q: how many of the integers have, say "1" in the la > 80 // A: it is, of course, C(N-1, v[1]-1, v[2], ..., v[9] > 81 // where C(k,a,b,..) is the # of ways of spliting k > 82 // So, the sum of the least digits of the integers are > 83 // X = \Sigma_{d=1..9} (d * C(N-1, v[1], v[2], ..., v[ > 84 // By the same argument, the sum of the second-last digi > 85 // 10 * X > 86 // For hundreds, the sum is 100*X, and so on. Eventualy, > 87 // t = (1+10+...+10^N) * X > 88 // = 111...111 * \Sigma_{d=1..9} (d * C(N-1, v[1], v > 89 // Let us simplify the formula by using C(k,a,b,...) = k > 90 // t = 111...111 * \Sigma_{d=1..9} (d * (N-1)! / v[1]! > 91 // = 111...111 * (N-1)! / v[1]! / ... / v[9]! * \Sig > 92 // = 111...111 * (N-1)! / v[1]! / ... / v[9]! * S > 93 // That's it! > 94 > 95 mint t = ONES[N] * FACT[N-1] * S; > 96 for(int i=1; i<=9; ++i) > 97 t = t * FACT_INV[v[i]]; > 98 answer = answer + t; > 99 } > 100 return answer.val; > 101 } > 102 }; > 103 > 104 // BEGIN CUT HERE > 105 #include <ctime> > 106 double start_time; string timer() > 107 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 108 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 109 { os << "{ "; > 110 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 111 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 112 void verify_case(const int& Expected, const int& Received) { > 113 bool ok = (Expected == Received); > 114 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 115 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 116 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 117 #define END verify_case(_, ProductAndSum().getSum(p2, p3, p5, p7, S));} > 118 int main(){ > 119 > 120 CASE(0) > 121 int p2 = 2; > 122 int p3 = 0; > 123 int p5 = 0; > 124 int p7 = 0; > 125 int S = 4; > 126 int _ = 26; > 127 END > 128 CASE(1) > 129 int p2 = 0; > 130 int p3 = 0; > 131 int p5 = 0; > 132 int p7 = 0; > 133 int S = 10; > 134 int _ = 110109965; > 135 END > 136 CASE(2) > 137 int p2 = 2; > 138 int p3 = 0; > 139 int p5 = 0; > 140 int p7 = 0; > 141 int S = 5; > 142 int _ = 610; > 143 END > 144 CASE(3) > 145 int p2 = 1; > 146 int p3 = 1; > 147 int p5 = 1; > 148 int p7 = 1; > 149 int S = 10; > 150 int _ = 0; > 151 END > 152 CASE(4) > 153 int p2 = 5; > 154 int p3 = 5; > 155 int p5 = 5; > 156 int p7 = 5; > 157 int S = 100; > 158 int _ = 61610122; > 159 END > 160 CASE(5) > 161 int p2 = 100; > 162 int p3 = 100; > 163 int p5 = 100; > 164 int p7 = 100; > 165 int S = 2500; > 166 int _ = -1; > 167 END > 168 /* > 169 CASE(6) > 170 int p2 = ; > 171 int p3 = ; > 172 int p5 = ; > 173 int p7 = ; > 174 int S = ; > 175 int _ = ; > 176 END > 177 */ > 178 } > 179 // END CUT HERE