Overview
| SHA1 Hash: | 9d33e96a5e371330c8879a6cb8b343cb4eafc1b8 |
|---|---|
| Date: | 2012-03-31 14:05:38 |
| User: | kinaba |
| Comment: | 537 |
| 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/537-U/1A.cpp version [0cd8df21a9e202cb]
> 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 KingXNewCurrency { public: > 29 int howMany(int A, int B, int X) > 30 { > 31 if(A%X==0 && B%X==0) > 32 return -1; > 33 int cnt = 0; > 34 for(int Y=1; Y<=max(A,B); ++Y) > 35 if( possible(A,B,X,Y) ) > 36 cnt++; > 37 return cnt; > 38 } > 39 > 40 bool possible(int A, int B, int X, int Y) > 41 { > 42 bool Aok = false; > 43 for(int p=0; p*X<=A; ++p) > 44 if( (A-p*X)%Y == 0 ) > 45 Aok = true; > 46 bool Bok = false; > 47 for(int p=0; p*X<=B; ++p) > 48 if( (B-p*X)%Y == 0 ) > 49 Bok = true; > 50 return Aok&&Bok; > 51 } > 52 }; > 53 > 54 // BEGIN CUT HERE > 55 #include <ctime> > 56 double start_time; string timer() > 57 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 58 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 59 { os << "{ "; > 60 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 61 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 62 void verify_case(const int& Expected, const int& Received) { > 63 bool ok = (Expected == Received); > 64 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 65 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 66 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 67 #define END verify_case(_, KingXNewCurrency().howMany(A, B, X));} > 68 int main(){ > 69 > 70 CASE(0) > 71 int A = 5; > 72 int B = 8; > 73 int X = 5; > 74 int _ = 5; > 75 END > 76 CASE(1) > 77 int A = 8; > 78 int B = 4; > 79 int X = 2; > 80 int _ = -1; > 81 END > 82 CASE(2) > 83 int A = 7; > 84 int B = 4; > 85 int X = 13; > 86 int _ = 1; > 87 END > 88 CASE(3) > 89 int A = 47; > 90 int B = 74; > 91 int X = 44; > 92 int _ = 2; > 93 END > 94 CASE(4) > 95 int A = 128; > 96 int B = 96; > 97 int X = 3; > 98 int _ = 65; > 99 END > 100 /* > 101 CASE(5) > 102 int A = ; > 103 int B = ; > 104 int X = ; > 105 int _ = ; > 106 END > 107 CASE(6) > 108 int A = ; > 109 int B = ; > 110 int X = ; > 111 int _ = ; > 112 END > 113 */ > 114 } > 115 // END CUT HERE
Added SRM/537-U/1B.cpp version [814caf84cee0379a]
> 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 KingXMagicSpells { public: > 29 double expectedNumber(vector <int> ducks, vector <int> spellOne, vector > 30 { > 31 const int N = ducks.size(); > 32 > 33 vector<int> revSpellTwo(N); > 34 for(int i=0; i<N; ++i) revSpellTwo[spellTwo[i]] = i; > 35 > 36 double e = 0; > 37 for(int B=30; B>=0; --B) { > 38 vector<int> dd(N); > 39 for(int i=0; i<N; ++i) > 40 dd[i] = (ducks[i] & (1<<B) ? 1 : 0); > 41 vector<int> xx(N); > 42 for(int i=0; i<N; ++i) > 43 xx[i] = (spellOne[i] & (1<<B) ? 1 : 0); > 44 e += solve(dd, xx, revSpellTwo, K) * (1<<B); > 45 } > 46 return e; > 47 } > 48 > 49 double solve(const vector <int>& dd, const vector <int>& xx, const vecto > 50 { > 51 memo.clear(); > 52 return prob(dd, xx, moveBack, K, 0, 1); > 53 } > 54 > 55 map<int, double> memo; > 56 double prob( > 57 const vector <int>& dd, const vector <int>& xx, const vector <in > 58 int K, int room, int bit) { > 59 if( K == 0 ) { > 60 return dd[room]==bit ? 1.0 : 0.0; > 61 } > 62 > 63 int key = (K * 100 + room) * 2 + bit; > 64 if( memo.count(key) ) > 65 return memo[key]; > 66 double e = 0.5 * prob(dd,xx,moveBack,K-1,moveBack[room],bit) > 67 + 0.5 * prob(dd,xx,moveBack,K-1,room,bit^xx[room]); > 68 return memo[key] = e; > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const double& Expected, const double& Received) { > 81 bool ok = (abs(Expected - Received) < 1e-9); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, KingXMagicSpells().expectedNumber(ducks, spellOn > 86 int main(){ > 87 > 88 CASE(0) > 89 int ducks_[] = {5, 3, 7}; > 90 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 91 int spellOne_[] = {1, 7, 4}; > 92 vector <int> spellOne(spellOne_, spellOne_+sizeof(spellOne_)/sizeof(*s > 93 int spellTwo_[] = {1, 0, 2}; > 94 vector <int> spellTwo(spellTwo_, spellTwo_+sizeof(spellTwo_)/sizeof(*s > 95 int K = 1; > 96 double _ = 3.5; > 97 END > 98 CASE(1) > 99 int ducks_[] = {5, 8}; > 100 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 101 int spellOne_[] = {53, 7}; > 102 vector <int> spellOne(spellOne_, spellOne_+sizeof(spellOne_)/sizeof(*s > 103 int spellTwo_[] = {1, 0}; > 104 vector <int> spellTwo(spellTwo_, spellTwo_+sizeof(spellTwo_)/sizeof(*s > 105 int K = 2; > 106 double _ = 21.5; > 107 END > 108 CASE(2) > 109 int ducks_[] = {123, 456, 789, 1234, 56789}; > 110 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 111 int spellOne_[] = {0, 0, 0, 0, 0}; > 112 vector <int> spellOne(spellOne_, spellOne_+sizeof(spellOne_)/sizeof(*s > 113 int spellTwo_[] = {0, 1, 2, 3, 4}; > 114 vector <int> spellTwo(spellTwo_, spellTwo_+sizeof(spellTwo_)/sizeof(*s > 115 int K = 50; > 116 double _ = 123.0; > 117 END > 118 CASE(3) > 119 int ducks_[] = {83291232, 3124231, 192412, 3813249, 629231, 9998989}; > 120 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 121 int spellOne_[] = {58, 37, 44, 66, 72, 19}; > 122 vector <int> spellOne(spellOne_, spellOne_+sizeof(spellOne_)/sizeof(*s > 123 int spellTwo_[] = {2, 0, 1, 5, 4, 3}; > 124 vector <int> spellTwo(spellTwo_, spellTwo_+sizeof(spellTwo_)/sizeof(*s > 125 int K = 11; > 126 double _ = 2.888186784716797E7; > 127 END > 128 /* > 129 CASE(4) > 130 int ducks_[] = ; > 131 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 132 int spellOne_[] = ; > 133 vector <int> spellOne(spellOne_, spellOne_+sizeof(spellOne_)/sizeof(*s > 134 int spellTwo_[] = ; > 135 vector <int> spellTwo(spellTwo_, spellTwo_+sizeof(spellTwo_)/sizeof(*s > 136 int K = ; > 137 double _ = ; > 138 END > 139 CASE(5) > 140 int ducks_[] = ; > 141 vector <int> ducks(ducks_, ducks_+sizeof(ducks_)/sizeof(*ducks_)); > 142 int spellOne_[] = ; > 143 vector <int> spellOne(spellOne_, spellOne_+sizeof(spellOne_)/sizeof(*s > 144 int spellTwo_[] = ; > 145 vector <int> spellTwo(spellTwo_, spellTwo_+sizeof(spellTwo_)/sizeof(*s > 146 int K = ; > 147 double _ = ; > 148 END > 149 */ > 150 } > 151 // END CUT HERE