Overview
| SHA1 Hash: | 5af29f0d04580400517ff12e4c63fa5b348224c9 |
|---|---|
| Date: | 2012-04-01 02:43:38 |
| User: | kinaba |
| Comment: | TCO12 |
| 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/TCO12-1/1A.cpp version [5b4985a0bbd0b903]
> 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 EllysJuice { public: > 29 vector <string> getWinners(vector <string> players) > 30 { > 31 set<string> winners; > 32 > 33 sort(players.begin(), players.end()); > 34 do > 35 winners.insert( play(players) ); > 36 while( next_permutation(players.begin(), players.end()) ); > 37 > 38 winners.erase(""); > 39 return vector<string>(winners.begin(), winners.end()); > 40 } > 41 > 42 string play(const vector<string>& p) > 43 { > 44 int juice[2] = {65536, 65536}; > 45 map<string, int> total; > 46 for(int i=0; i<p.size(); ++i) > 47 total[p[i]] += (juice[i%2]/=2); > 48 > 49 string best_name; > 50 int best = 0; > 51 bool tie = false; > 52 for(map<string, int>::iterator it=total.begin(); it!=total.end() > 53 if( it->second > best ) { > 54 best_name = it->first; > 55 best = it->second; > 56 tie = false; > 57 } > 58 else if( it->second == best ) > 59 tie = true; > 60 return tie ? "" : best_name; > 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 vector <string>& Expected, const vector <string>& Receive > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, EllysJuice().getWinners(players));} > 78 int main(){ > 79 > 80 CASE(0) > 81 string players_[] = { "elly", "kriss", "stancho", "elly", "stancho" }; > 82 vector <string> players(players_, players_+sizeof(players_)/sizeof(*pl > 83 string __[] = {"elly", "stancho" }; > 84 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 85 END > 86 CASE(1) > 87 string players_[] = {"torb", "elly", "stancho", "kriss"}; > 88 vector <string> players(players_, players_+sizeof(players_)/sizeof(*pl > 89 vector <string> _; > 90 END > 91 CASE(2) > 92 string players_[] = {"elly", "elly", "elly", "elly", "elly"}; > 93 vector <string> players(players_, players_+sizeof(players_)/sizeof(*pl > 94 string __[] = {"elly" }; > 95 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 96 END > 97 CASE(3) > 98 string players_[] = { "ariadne", "elly", "ariadne", "stancho", "stancho" > 99 vector <string> players(players_, players_+sizeof(players_)/sizeof(*pl > 100 string __[] = {"ariadne", "elly", "stancho" }; > 101 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 102 END > 103 CASE(4) > 104 string players_[] = {"b","b","a","a"}; > 105 vector <string> players(players_, players_+sizeof(players_)/sizeof(*pl > 106 string __[] = {"a","b"}; > 107 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 108 END > 109 /* > 110 CASE(5) > 111 string players_[] = ; > 112 vector <string> players(players_, players_+sizeof(players_)/sizeof(*pl > 113 string __[] = ; > 114 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 115 END > 116 */ > 117 } > 118 // END CUT HERE
Added SRM/TCO12-1/1B.cpp version [ada6668a1964faea]
> 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 EllysFractions { public: > 29 long long getCount(int N) > 30 { > 31 LL total = 0; > 32 for(int k=2; k<=N; ++k) > 33 total += getExact(k); > 34 return total; > 35 } > 36 > 37 LL getExact(int N) > 38 { > 39 int np = 0; > 40 for(int p=2; p<=N; ++p) > 41 if(is_prime(p)) > 42 ++np; > 43 LL v = 1; > 44 for(int i=0; i<np; ++i) > 45 v *= 2; > 46 return v/2; > 47 } > 48 > 49 bool is_prime(int n) > 50 { > 51 for(int k=2; k<n; ++k) > 52 if(n%k == 0) > 53 return false; > 54 return true; > 55 } > 56 }; > 57 > 58 // BEGIN CUT HERE > 59 #include <ctime> > 60 double start_time; string timer() > 61 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 62 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 63 { os << "{ "; > 64 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 65 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 66 void verify_case(const long long& Expected, const long long& Received) { > 67 bool ok = (Expected == Received); > 68 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 69 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 70 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 71 #define END verify_case(_, EllysFractions().getCount(N));} > 72 int main(){ > 73 > 74 CASE(0) > 75 int N = 1; > 76 long long _ = 0LL; > 77 END > 78 CASE(1) > 79 int N = 2; > 80 long long _ = 1LL; > 81 END > 82 CASE(2) > 83 int N = 3; > 84 long long _ = 3LL; > 85 END > 86 CASE(3) > 87 int N = 5; > 88 long long _ = 9LL; > 89 END > 90 CASE(4) > 91 int N = 100; > 92 long long _ = 177431885LL; > 93 END > 94 CASE(5) > 95 int N = 250; > 96 long long _ = -1LL; > 97 END > 98 CASE(6) > 99 int N = 4; > 100 long long _ = 5LL; > 101 END > 102 } > 103 // END CUT HERE
Added SRM/TCO12-1/1C.cpp version [add6efd3494f287b]
> 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 struct UnionFind > 29 { > 30 vector<int> uf, sz; > 31 int nc; > 32 > 33 UnionFind(int N): uf(N), sz(N,1), nc(N) > 34 { for(int i=0; i<N; ++i) uf[i] = i; } > 35 int size() > 36 { return nc; } > 37 int Find(int a) > 38 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } > 39 bool Union(int a, int b) > 40 { > 41 a = Find(a); > 42 b = Find(b); > 43 if( a != b ) > 44 { > 45 if( sz[a] >= sz[b] ) swap(a, b); > 46 uf[a] = b; > 47 sz[b] += sz[a]; > 48 --nc; > 49 } > 50 return (a!=b); > 51 } > 52 }; > 53 > 54 class EllysLights { public: > 55 int getMinimum(string initial, vector <string> switches) > 56 { > 57 int N = switches.size(); > 58 UnionFind uf(N*2+2); > 59 #define TR 0 > 60 #define FL 1 > 61 #define POS(x) ((x)+2) > 62 #define NEG(x) ((x)+N+2) > 63 > 64 for(int i=0; i<initial.size(); ++i) > 65 { > 66 vector<int> sw; > 67 for(int k=0; k<N; ++k) > 68 if( switches[k][i]=='Y' ) > 69 sw.push_back(k); > 70 > 71 if(initial[i] == 'Y') > 72 if(sw.size() == 0) > 73 { > 74 return -1; > 75 } > 76 else if(sw.size() == 1) > 77 { > 78 uf.Union(POS(sw[0]), TR); > 79 uf.Union(NEG(sw[0]), FL); > 80 } > 81 else > 82 { > 83 uf.Union(POS(sw[0]), NEG(sw[1])); > 84 uf.Union(NEG(sw[0]), POS(sw[1])); > 85 } > 86 else > 87 if(sw.size() == 0) > 88 { > 89 } > 90 else if(sw.size() == 1) > 91 { > 92 uf.Union(POS(sw[0]), FL); > 93 uf.Union(NEG(sw[0]), TR); > 94 } > 95 else > 96 { > 97 uf.Union(POS(sw[0]), POS(sw[1])); > 98 uf.Union(NEG(sw[0]), NEG(sw[1])); > 99 } > 100 } > 101 > 102 if( uf.Find(TR) == uf.Find(FL) ) > 103 return -1; > 104 for(int k=0; k<N; ++k) > 105 if( uf.Find(POS(k)) == uf.Find(NEG(k)) ) > 106 return -1; > 107 > 108 int minSwitch = 0; > 109 set<int> done; > 110 for(int k=0; k<N; ++k) > 111 if( !done.count(k) ) > 112 { > 113 vector<int> pos(1, k); > 114 vector<int> neg; > 115 for(int j=k+1; j<N; ++j) > 116 if( !done.count(j) ) > 117 if( uf.Find(POS(k)) == uf.Find(P > 118 pos.push_back(j); > 119 done.insert(j); > 120 } else if( uf.Find(POS(k)) == uf > 121 neg.push_back(j); > 122 done.insert(j); > 123 } > 124 if( uf.Find(POS(k)) == uf.Find(TR) ) { > 125 minSwitch += pos.size(); > 126 } > 127 else if( uf.Find(POS(k)) == uf.Find(FL) ) { > 128 minSwitch += neg.size(); > 129 } > 130 else { > 131 minSwitch += min(pos.size(), neg.size()) > 132 } > 133 } > 134 return minSwitch; > 135 } > 136 }; > 137 > 138 // BEGIN CUT HERE > 139 #include <ctime> > 140 double start_time; string timer() > 141 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 142 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 143 { os << "{ "; > 144 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 145 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 146 void verify_case(const int& Expected, const int& Received) { > 147 bool ok = (Expected == Received); > 148 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 149 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 150 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 151 #define END verify_case(_, EllysLights().getMinimum(initial, switches));} > 152 int main(){ > 153 > 154 CASE(0) > 155 string initial = "YNYNNN"; > 156 string switches_[] = {"YNNYNY", "NYYYNN", "YNYNYN", "NNNNYN", "NYNNNY"}; > 157 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 158 int _ = 2; > 159 END > 160 CASE(1) > 161 string initial = "YNYNYN"; > 162 string switches_[] = {"NNNNNN", "YYYYYY", "NYNNNN", "NNNYNN", "NNNNNY"}; > 163 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 164 int _ = 4; > 165 END > 166 CASE(2) > 167 string initial = "YYN"; > 168 string switches_[] = {"YNY", "NYN"}; > 169 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 170 int _ = -1; > 171 END > 172 CASE(3) > 173 string initial = "NNYNYNYYYNNYYYYN"; > 174 string switches_[] = {"NYNYNYNYNYNYNYNY", > 175 "YNYNYNYNYNYNYNYN", > 176 "NNNNNNNNNNNNNNNN", > 177 "YNNNNNNNNNNNNNNN", > 178 "NYNNNNNNNNNNNNNN", > 179 "NNYNNNNNNNNNNNNN", > 180 "NNNYNNNNNNNNNNNN", > 181 "NNNNYNNNNNNNNNNN", > 182 "NNNNNYNNNNNNNNNN", > 183 "NNNNNNYNNNNNNNNN", > 184 "NNNNNNNYNNNNNNNN", > 185 "NNNNNNNNYNNNNNNN", > 186 "NNNNNNNNNYNNNNNN", > 187 "NNNNNNNNNNYNNNNN", > 188 "NNNNNNNNNNNYNNNN", > 189 "NNNNNNNNNNNNYNNN", > 190 "NNNNNNNNNNNNNYNN", > 191 "NNNNNNNNNNNNNNYN", > 192 "NNNNNNNNNNNNNNNY"}; > 193 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 194 int _ = 6; > 195 END > 196 CASE(4) > 197 string initial = "NYNYNYYYNNYYYNNYNNYYYYYNNYNYYYY"; > 198 string switches_[] = {"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", > 199 "NNNNNNNNYNNNYNNNNYYNYNNNNYNNNNN", > 200 "NNNNNNNNNYNNNNNNNNNNNNYNNNNNNNN", > 201 "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNN", > 202 "NYNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", > 203 "NNNNNNNNNNNNNYYNNNNNNNNNNNNNNNY", > 204 "NNNNNNYNNNNNNNNNNNNYNNNNNYNNNNN", > 205 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 206 "YNNNNNNNNNNNNNNNNNNYNNNNNNNNNNN", > 207 "NNNYNNNNNNNNNNNNNNNNNNNYYNNNNNN", > 208 "NYNNNNNNNNNNYNNNNNNNNNNNNNNNYNN", > 209 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 210 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 211 "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNY", > 212 "NNNNNNNNNNYNNNNNNNNNYYYNNNNNNNN", > 213 "NNNYNNNNNNNNNNNNNNNNNNNNNNNYNNN", > 214 "NNNNNNNNYNNNNNNNNNNNNNNNYNNNNNN", > 215 "YNNNYNNNNNNNNNNNNNNNNNNNNNNYNNN", > 216 "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNN", > 217 "NNNNYNNYNNNNNNNNNNNNNNNNNNNNNNN", > 218 "NNNNNNNYNNNYNNNYNNNNNNNNNNNNNYN"}; > 219 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 220 int _ = 7; > 221 END > 222 CASE(5) > 223 string initial = "NYNYYNYNYYYYNNYNYNNYYNNNNNYNYNNNNNYNNNYN"; > 224 string switches_[] = {"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNN", > 225 "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNN", > 226 "NNNNNNNNNYNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN", > 227 "NNNNNNNNNNNNNNNNNNNYNNNNYNNNNNNNYNNNNNNN", > 228 "NNNNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", > 229 "NNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNYNNNNNYNN", > 230 "NNNNNNNNNNYNNNNNNNNNNNNNNYNNNNNYNNYNNNNN", > 231 "NNNNNYNNYNNYNNNNNNNNNNNNNNNNNNNNNYNNNNNN", > 232 "YNNNYNNNNNNNNNNNNNYNNNYNNYNNNNNNNYNNNNNN", > 233 "NNNNNNNNNYYNNNNNNNNNNNNYNNNNYNNNNNNNNNNN", > 234 "NNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNY", > 235 "NNNNNNNNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNNN", > 236 "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNN", > 237 "NNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNN", > 238 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 239 "NNNNNNNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN", > 240 "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYNNY", > 241 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", > 242 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 243 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 244 "NNNNNNNYNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNN", > 245 "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNN", > 246 "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNN", > 247 "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 248 "NYNNNNYNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", > 249 "NNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNN", > 250 "NNNNNNNNNNNNYNNYYNNNNNNNNNNNNNNNNNNNNNNN", > 251 "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 252 "NNNYNNNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNN", > 253 "NNNNNNNNYNNNNNNNNNNNNNNNNNNNYNYNNNNNNNNN", > 254 "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNYNNN"}; > 255 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 256 int _ = -1; > 257 END > 258 /* > 259 CASE(6) > 260 string initial = ; > 261 string switches_[] = ; > 262 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 263 int _ = ; > 264 END > 265 CASE(7) > 266 string initial = ; > 267 string switches_[] = ; > 268 vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof > 269 int _ = ; > 270 END > 271 */ > 272 } > 273 // END CUT HERE