Overview
| SHA1 Hash: | d4ec396a2392fda8ad434d33a4430cd16d130b27 |
|---|---|
| Date: | 2014-04-21 09:16:26 |
| User: | kinaba |
| Comment: | TCO14 |
| 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/TCO14-1B/1A.cpp version [d72e60e00215d96c]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class SpamChecker { public: > 23 string spamCheck(string judgeLog, int good, int bad) > 24 { > 25 return isBad(judgeLog, good, bad) ? "SPAM" : "NOT SPAM"; > 26 } > 27 > 28 bool isBad(string judgeLog, int good, int bad) > 29 { > 30 int score = 0; > 31 for(char c: judgeLog) > 32 if((score += c=='o' ? good : -bad) < 0) > 33 return true; > 34 return false; > 35 } > 36 }; > 37 > 38 // BEGIN CUT HERE > 39 #include <ctime> > 40 double start_time; string timer() > 41 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 42 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 43 { os << "{ "; > 44 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 45 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 46 void verify_case(const string& Expected, const string& Received) { > 47 bool ok = (Expected == Received); > 48 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 49 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 50 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 51 #define END verify_case(_, SpamChecker().spamCheck(judgeLog, good, bad));} > 52 int main(){ > 53 > 54 CASE(0) > 55 string judgeLog = "ooooxxxo"; > 56 int good = 2; > 57 int bad = 3; > 58 string _ = "SPAM"; > 59 END > 60 CASE(1) > 61 string judgeLog = "ooooxxxo"; > 62 int good = 3; > 63 int bad = 4; > 64 string _ = "NOT SPAM"; > 65 END > 66 CASE(2) > 67 string judgeLog = "xooooooooooooooooooooooooooo"; > 68 int good = 1000; > 69 int bad = 1; > 70 string _ = "SPAM"; > 71 END > 72 CASE(3) > 73 string judgeLog = "oxxxxxxxxxxxxxxxxxxxxxxxxxxxx"; > 74 int good = 1000; > 75 int bad = 1; > 76 string _ = "NOT SPAM"; > 77 END > 78 CASE(4) > 79 string judgeLog = "ooxoxoxooxoxxoxoxooxoxoxoxxoxx"; > 80 int good = 15; > 81 int bad = 17; > 82 string _ = "SPAM"; > 83 END > 84 CASE(5) > 85 string judgeLog = "oooxoxoxoxoxoxooxooxoxooxo"; > 86 int good = 16; > 87 int bad = 18; > 88 string _ = "NOT SPAM"; > 89 END > 90 /* > 91 CASE(6) > 92 string judgeLog = ; > 93 int good = ; > 94 int bad = ; > 95 string _ = ; > 96 END > 97 CASE(7) > 98 string judgeLog = ; > 99 int good = ; > 100 int bad = ; > 101 string _ = ; > 102 END > 103 */ > 104 } > 105 // END CUT HERE
Added SRM/TCO14-1B/1B.cpp version [27ee55f46dcdfc29]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 int bitcnt(int x) > 23 { > 24 int c = 0; > 25 for(; x; x>>=1) > 26 c += x&1; > 27 return c; > 28 } > 29 > 30 class WolvesAndSheep { public: > 31 int getmin(vector <string> field) > 32 { > 33 int H = field.size(); > 34 int W = field[0].size(); > 35 int best = W*H; > 36 for(int mask=0; mask<(1<<(W-1)); ++mask) > 37 { > 38 vector<vector<pair<int,int>>> sw(H); > 39 for(int y=0; y<field.size(); ++y) > 40 for(int s=0,w=0,x=0; x<W; ++x) > 41 { > 42 if(field[y][x]=='S') s++; > 43 if(field[y][x]=='W') w++; > 44 if(s&&w) > 45 goto next; > 46 if((mask & (1<<x)) || x==W-1) { > 47 sw[y].emplace_back(s,w); > 48 s=w=0; > 49 } > 50 } > 51 { > 52 int score = bitcnt(mask); > 53 int WW = sw[0].size(); > 54 vector<pair<int,int>> cur(WW); > 55 for(int y=0; y<sw.size(); ++y) > 56 { > 57 bool dame = false; > 58 for(int x=0; x<WW; ++x) { > 59 cur[x].first += sw[y][x].first; > 60 cur[x].second += sw[y][x].second > 61 if(cur[x].first && cur[x].second > 62 dame = true; > 63 } > 64 if(dame) { > 65 score ++; > 66 cur = sw[y]; > 67 } > 68 } > 69 > 70 best = min(best, score); > 71 } > 72 next:; > 73 } > 74 return best; > 75 } > 76 }; > 77 > 78 // BEGIN CUT HERE > 79 #include <ctime> > 80 double start_time; string timer() > 81 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 82 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 83 { os << "{ "; > 84 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 85 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 86 void verify_case(const int& Expected, const int& Received) { > 87 bool ok = (Expected == Received); > 88 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 89 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 90 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 91 #define END verify_case(_, WolvesAndSheep().getmin(field));} > 92 int main(){ > 93 > 94 CASE(0) > 95 string field_[] = {"W.WSS", > 96 "WW.S.", > 97 ".SSS.", > 98 "SSS.S", > 99 ".SS.S"}; > 100 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 101 int _ = 2; > 102 END > 103 CASE(1) > 104 string field_[] = {".....", > 105 ".....", > 106 "....."}; > 107 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 108 int _ = 0; > 109 END > 110 CASE(2) > 111 string field_[] = {".SS", > 112 "...", > 113 "S..", > 114 "W.W"}; > 115 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 116 int _ = 1; > 117 END > 118 CASE(3) > 119 string field_[] = {"WWWSWWSSWWW", > 120 "WWSWW.SSWWW", > 121 "WS.WSWWWWS."}; > 122 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 123 int _ = 10; > 124 END > 125 CASE(4) > 126 string field_[] = {".W.S.W.W", > 127 "W.W.S.W.", > 128 ".S.S.W.W", > 129 "S.S.S.W.", > 130 ".S.W.W.S", > 131 "S.S.W.W.", > 132 ".W.W.W.S", > 133 "W.W.S.S."}; > 134 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 135 int _ = 7; > 136 END > 137 CASE(5) > 138 string field_[] = {"W.SSWWSSSW.SS", > 139 ".SSSSW.SSWWWW", > 140 ".WWWWS.WSSWWS", > 141 "SS.WSS..W.WWS", > 142 "WSSS.SSWS.W.S", > 143 "WSS.WS...WWWS", > 144 "S.WW.S.SWWWSW", > 145 "WSSSS.SSW...S", > 146 "S.WWSW.WWSWSW", > 147 ".WSSS.WWSWWWS", > 148 "..SSSS.WWWSSS", > 149 "SSWSWWS.W.SSW", > 150 "S.WSWS..WSSS.", > 151 "WS....W..WSS."}; > 152 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 153 int _ = 24; > 154 END > 155 CASE(6) > 156 string field_[] = {"WW..SS", > 157 "WW..SS", > 158 "......", > 159 "......", > 160 "SS..WW", > 161 "SS..WW"}; > 162 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 163 int _ = 2; > 164 END > 165 /* > 166 CASE(7) > 167 string field_[] = ; > 168 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 169 int _ = ; > 170 END > 171 CASE(8) > 172 string field_[] = ; > 173 vector <string> field(field_, field_+sizeof(field_)/sizeof(*field_)); > 174 int _ = ; > 175 END > 176 */ > 177 } > 178 // END CUT HERE
Added SRM/TCO14-1B/1C.cpp version [7c1aa38966342ddc]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 double C(int n, int k) > 23 { > 24 k = min(n-k, k); > 25 double t = 1; > 26 for(int i=1; i<=k; ++i) > 27 t = t * (n-i+1) / i; > 28 return t; > 29 } > 30 > 31 class EagleInZoo { public: > 32 double calc(vector <int> parent, int K) > 33 { > 34 int N = parent.size() + 1; > 35 vector<vector<int>> child(N); > 36 for(int i=1; i<N; ++i) > 37 child[parent[i-1]].push_back(i); > 38 return rec(child, 0, K); > 39 } > 40 > 41 map<pair<int,int>,double> memo; > 42 double rec(const vector<vector<int>>& child, int v, int K) > 43 { > 44 if(K == 1) > 45 return 1.0; > 46 if(child[v].empty()) > 47 return 0.0; > 48 pair<int,int> key(v, K); > 49 if(memo.count(key)) return memo[key]; > 50 > 51 double ans = 0.0; > 52 for(int u: child[v]) // When K-the eagle goes to |u|. > 53 for(int uN=0; uN<=K-2; ++uN) // When uN out of K-2 previ > 54 { > 55 ans += C(K-2, uN) > 56 * pow(1.0/child[v].size(), uN) > 57 * pow(1.0-1.0/child[v].size(), K-2-uN) > 58 * rec(child, u, uN+1); > 59 } > 60 return memo[key] = ans / child[v].size(); > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 double start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const double& Expected, const double& Received) { > 73 bool ok = (abs(Expected - Received) < 1e-9); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, EagleInZoo().calc(parent, K));} > 78 int main(){ > 79 > 80 CASE(0) > 81 int parent_[] = {0,0}; > 82 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 83 int K = 2; > 84 double _ = 1.0; > 85 END > 86 CASE(1) > 87 int parent_[] = {0,0}; > 88 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 89 int K = 3; > 90 double _ = 0.5; > 91 END > 92 CASE(2) > 93 int parent_[] = {0,1,0,3}; > 94 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 95 int K = 4; > 96 double _ = 0.75; > 97 END > 98 CASE(3) > 99 int parent_[] = {0,0,1,1,2,4,4,4,5,5,6,6}; > 100 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 101 int K = 20; > 102 double _ = 0.14595168754091617; > 103 END > 104 CASE(4) > 105 int parent_[] = {0,1,2,3,2,1,1,7,0,9,10,11,12,13,14,15,16,17,18,14,9}; > 106 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 107 int K = 24; > 108 double _ = 0.3272154791654077; > 109 END > 110 CASE(5) > 111 int parent_[] = {0,1,2,3,4,5,6,7,8,9,10}; > 112 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 113 int K = 50; > 114 double _ = 0.0; > 115 END > 116 /* > 117 CASE(6) > 118 int parent_[] = ; > 119 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 120 int K = ; > 121 double _ = ; > 122 END > 123 CASE(7) > 124 int parent_[] = ; > 125 vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)) > 126 int K = ; > 127 double _ = ; > 128 END > 129 */ > 130 } > 131 // END CUT HERE