Overview
| SHA1 Hash: | c0b96abfe590ee061487b4a1bc38e1c63e8336aa |
|---|---|
| Date: | 2013-03-15 00:56:24 |
| User: | kinaba |
| Comment: | 572 |
| 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/572-U/1A.cpp version [22fb8b993e155b65]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 struct UnionFind > 23 { > 24 vector<int> uf, sz; > 25 int nc; > 26 > 27 UnionFind(int N): uf(N), sz(N,1), nc(N) > 28 { for(int i=0; i<N; ++i) uf[i] = i; } > 29 int size() > 30 { return nc; } > 31 int size(int a) > 32 { return sz[Find(a)]; } > 33 int Find(int a) > 34 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } > 35 bool Union(int a, int b) > 36 { > 37 a = Find(a); > 38 b = Find(b); > 39 if( a != b ) > 40 { > 41 if( sz[a] >= sz[b] ) swap(a, b); > 42 uf[a] = b; > 43 sz[b] += sz[a]; > 44 --nc; > 45 } > 46 return (a!=b); > 47 } > 48 }; > 49 > 50 class NewArenaPassword { public: > 51 int minChange(string oldPassword, int K) > 52 { > 53 int N = oldPassword.size(); > 54 UnionFind uf(N); > 55 for(int i=0; i<K; ++i) > 56 uf.Union(i, N-K+i); > 57 > 58 int total = 0; > 59 for(int r=0; r<N; ++r) if(uf.Find(r) == r) { > 60 map<char,int> freq; > 61 for(int i=0; i<N; ++i) > 62 if(uf.Find(i) == r) > 63 freq[oldPassword[i]]++; > 64 vector<int> fff; > 65 for(map<char,int>::iterator it=freq.begin(); it!=freq.en > 66 fff.push_back(it->second); > 67 total += accumulate(fff.begin(), fff.end(), -*max_elemen > 68 } > 69 return total; > 70 } > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const int& Expected, const int& Received) { > 82 bool ok = (Expected == Received); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, NewArenaPassword().minChange(oldPassword, K));} > 87 int main(){ > 88 > 89 CASE(0) > 90 string oldPassword = "topcoderopen"; > 91 int K = 5; > 92 int _ = 3; > 93 END > 94 CASE(1) > 95 string oldPassword = "puyopuyo"; > 96 int K = 4; > 97 int _ = 0; > 98 END > 99 CASE(2) > 100 string oldPassword = "loool"; > 101 int K = 3; > 102 int _ = 1; > 103 END > 104 CASE(3) > 105 string oldPassword = "arena"; > 106 int K = 5; > 107 int _ = 0; > 108 END > 109 CASE(4) > 110 string oldPassword = "amavckdkz"; > 111 int K = 7; > 112 int _ = 5; > 113 END > 114 /* > 115 CASE(5) > 116 string oldPassword = ; > 117 int K = ; > 118 int _ = ; > 119 END > 120 CASE(6) > 121 string oldPassword = ; > 122 int K = ; > 123 int _ = ; > 124 END > 125 */ > 126 } > 127 // END CUT HERE
Added SRM/572-U/1B.cpp version [b8011a6ba09fe38f]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class EllysBulls { public: > 23 string getNumber(vector <string> guesses, vector <int> bulls) > 24 { > 25 vector<int> pTen(1,1); > 26 for(int i=0; i<10; ++i) > 27 pTen.push_back(pTen.back()*10); > 28 > 29 int Q = guesses.size(); > 30 int N = guesses[0].size(); > 31 int B = min(N, 4); > 32 int F = N - B; > 33 map<string, vector<int> > back; > 34 for(int b=0; b<pTen[B]; ++b) > 35 { > 36 string sig; > 37 for(int i=0; i<Q; ++i) > 38 { > 39 int s = bulls[i]; > 40 for(int k=0; k<B; ++k) > 41 if( (guesses[i][N-1-k]-'0') == b/pTen[k] > 42 --s; > 43 if(s>=0) > 44 sig += char('0'+s); > 45 else > 46 goto next; > 47 } > 48 back[sig].push_back(b); > 49 next:; > 50 } > 51 > 52 string cand = ""; > 53 for(int f=0; f<pTen[F]; ++f) > 54 { > 55 string sig; > 56 map<string, vector<int> >::iterator it; > 57 for(int i=0; i<Q; ++i) > 58 { > 59 int s = 0; > 60 for(int k=0; k<F; ++k) > 61 if( (guesses[i][F-1-k]-'0') == f/pTen[k] > 62 ++s; > 63 if(s<=bulls[i]) > 64 sig += char('0'+s); > 65 else > 66 goto next2; > 67 } > 68 it = back.find(sig); > 69 if( it != back.end() ) { > 70 for(int j=0; j<it->second.size(); ++j) { > 71 if(!cand.empty()) > 72 return "Ambiguity"; > 73 for(int k=0; k<F; ++k) > 74 cand += char('0'+f/pTen[F-1-k]%1 > 75 for(int k=0; k<B; ++k) > 76 cand += char('0'+it->second[j]/p > 77 } > 78 } > 79 next2:; > 80 } > 81 > 82 if(cand.empty()) > 83 return "Liar"; > 84 return cand; > 85 } > 86 }; > 87 > 88 // BEGIN CUT HERE > 89 #include <ctime> > 90 double start_time; string timer() > 91 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 92 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 93 { os << "{ "; > 94 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 95 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 96 void verify_case(const string& Expected, const string& Received) { > 97 bool ok = (Expected == Received); > 98 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 99 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 100 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 101 #define END verify_case(_, EllysBulls().getNumber(guesses, bulls));} > 102 int main(){ > 103 > 104 CASE(0) > 105 string guesses_[] = {"1234", "4321", "1111", "2222", "3333", "4444", "55 > 106 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 107 int bulls_[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0}; > 108 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 109 string _ = "1337"; > 110 END > 111 CASE(1) > 112 string guesses_[] = {"0000", "1111", "2222"}; > 113 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 114 int bulls_[] = {2, 2, 2}; > 115 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 116 string _ = "Liar"; > 117 END > 118 CASE(2) > 119 string guesses_[] = {"666666", "666677", "777777", "999999"}; > 120 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 121 int bulls_[] = {2, 3, 1, 0}; > 122 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 123 string _ = "Ambiguity"; > 124 END > 125 CASE(3) > 126 string guesses_[] = {"000", "987", "654", "321", "100", "010"}; > 127 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 128 int bulls_[] = {2, 1, 0, 0, 1, 1}; > 129 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 130 string _ = "007"; > 131 END > 132 CASE(4) > 133 string guesses_[] = {"28", "92", "70", "30", "67", "63", "06", "65", > 134 "11", "06", "88", "48", "09", "65", "48", "08"}; > 135 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 136 int bulls_[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; > 137 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 138 string _ = "54"; > 139 END > 140 CASE(5) > 141 string guesses_[] = {"0294884", "1711527", "2362216", "7666148", "729564 > 142 "4166623", "1166638", "2767693", "8650248", "2486509", > 143 "6138934", "4018642", "6236742", "2961643", "8407361", > 144 "2097376", "6575410", "6071777", "3569948", "2606380"}; > 145 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 146 int bulls_[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, > 147 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 148 string _ = "4266642"; > 149 END > 150 /* > 151 CASE(6) > 152 string guesses_[] = ; > 153 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 154 int bulls_[] = ; > 155 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 156 string _ = ; > 157 END > 158 CASE(7) > 159 string guesses_[] = ; > 160 vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*gu > 161 int bulls_[] = ; > 162 vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_)); > 163 string _ = ; > 164 END > 165 */ > 166 } > 167 // END CUT HERE