Overview
| SHA1 Hash: | 46d6ab9496a00b1e971471ce3ab8ab1d4303be39 |
|---|---|
| Date: | 2011-12-07 02:01:43 |
| User: | kinaba |
| Comment: | 525 |
| 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/524-U/2C-U.cpp version [925481462bafb3b0]
> 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 MultiplesWithLimit { public: > 29 string minMultiples(int N, vector <int> forbiddenDigits) > 30 { > 31 vector<int> allowed; > 32 for(int i=0; i<=9; ++i) > 33 if( find(forbiddenDigits.begin(), forbiddenDigits.end(), > 34 allowed.push_back(i); > 35 > 36 vector< vector< pair<char,int> > > G(N); > 37 for(int v=0; v<N; ++v) > 38 for(int k=0; k<allowed.size(); ++k) > 39 G[v].push_back( make_pair(char('0'+allowed[k]), > 40 > 41 vector<int> dist_to_zero(N, INF); > 42 queue<int> Q; > 43 dist_to_zero[0] = 0; > 44 Q.push(0); > 45 while( !Q.empty() ) > 46 { > 47 int v = Q.front(); > 48 Q.pop(); > 49 for(int i=0; i<allowed.size(); ++i) > 50 { > 51 int vv = (allowed[i]*POW(10,dist_to_zero[v],N) + > 52 if( dist_to_zero[vv] == INF ) { > 53 dist_to_zero[vv] = dist_to_zero[v] + 1; > 54 Q.push(vv); > 55 } > 56 } > 57 } > 58 > 59 string all; > 60 int v = 0; > 61 do { > 62 int best = INF; > 63 int besta = -1; > 64 for(int i=0; i<allowed.size(); ++i) > 65 if(v>0 || allowed[i]>0) > 66 { > 67 int vv = (v*10 + allowed[i]) % N; > 68 if( dist_to_zero[vv] < best ) { > 69 best = dist_to_zero[vv]; > 70 besta = allowed[i]; > 71 } > 72 } > 73 if( best == INF ) > 74 return "IMPOSSIBLE"; > 75 all += char('0' + besta); > 76 v = (v*10 + besta) % N; > 77 cerr << v << " " << dist_to_zero[v] << " " << besta << e > 78 } while( v ); > 79 > 80 if( all.size() <= 8 ) > 81 return all; > 82 else { > 83 stringstream ss; > 84 ss << all.substr(0,3) << "..." << all.substr(all.size()- > 85 return ss.str(); > 86 } > 87 } > 88 > 89 int POW(int v, int e, int m) > 90 { > 91 int r = 1%m; > 92 for(; e; e>>=1,v=v*v%m) > 93 if( e&1 ) > 94 r = r*v%m; > 95 return r; > 96 } > 97 > 98 static const int INF = 0x1fffffff; > 99 }; > 100 > 101 // BEGIN CUT HERE > 102 #include <ctime> > 103 double start_time; string timer() > 104 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 105 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 106 { os << "{ "; > 107 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 108 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 109 void verify_case(const string& Expected, const string& Received) { > 110 bool ok = (Expected == Received); > 111 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 112 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 113 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 114 #define END verify_case(_, MultiplesWithLimit().minMultiples(N, forbiddenDi > 115 int main(){ > 116 > 117 CASE(0) > 118 int N = 8; > 119 int forbiddenDigits_[] = {2,3,4,5,6,7,8,9}; > 120 vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof > 121 string _ = "1000"; > 122 END > 123 CASE(1) > 124 int N = 9; > 125 int forbiddenDigits_[] = {1,3,4,5,6,7,8,9}; > 126 vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof > 127 string _ = "222...222(9 digits)"; > 128 END > 129 CASE(2) > 130 int N = 524; > 131 int forbiddenDigits_[] = {5,2,4}; > 132 vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof > 133 string _ = "3668"; > 134 END > 135 CASE(3) > 136 int N = 10000; > 137 int forbiddenDigits_[] = {0}; > 138 vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof > 139 string _ = "IMPOSSIBLE"; > 140 END > 141 CASE(4) > 142 int N = 1; > 143 int forbiddenDigits_[] = {0,1,2,3,4,5,6,7,8,9}; > 144 vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof > 145 string _ = "IMPOSSIBLE"; > 146 END > 147 /* > 148 CASE(5) > 149 int N = ; > 150 int forbiddenDigits_[] = ; > 151 vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof > 152 string _ = ; > 153 END > 154 CASE(6) > 155 int N = ; > 156 int forbiddenDigits_[] = ; > 157 vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof > 158 string _ = ; > 159 END > 160 */ > 161 } > 162 // END CUT HERE
Added SRM/525-U/1A.cpp version [e66e79bfc0293cc6]
> 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 DropCoins { public: > 29 int getMinimum(vector <string> board, int K) > 30 { > 31 static const int INF = 0x3fffffff; > 32 int best = INF; > 33 int H = board.size(); > 34 int W = board[0].size(); > 35 vector< vector<int> > sum(H, vector<int>(W+1)); > 36 for(int y=0; y<H; ++y) > 37 for(int x=0; x<W; ++x) > 38 sum[y][x+1] = sum[y][x] + (board[y][x]=='o' ? 1 > 39 > 40 for(int x=0; x<W; ++x) > 41 for(int X=x; X<=W; ++X) > 42 for(int y=0; y<H; ++y) > 43 for(int Y=y; Y<=H; ++Y) > 44 { > 45 // count > 46 int cnt = 0; > 47 for(int i=y; i<Y; ++i) > 48 cnt += sum[i][X]-sum[i][ > 49 if( cnt == K ) > 50 { > 51 int L = x; > 52 int R = W-X; > 53 int T = y; > 54 int B = H-Y; > 55 int move = L+R+min(L,R)+ > 56 best = min(best, move); > 57 } > 58 } > 59 return best==INF ? -1 : best; > 60 } > 61 }; > 62 > 63 // BEGIN CUT HERE > 64 #include <ctime> > 65 double start_time; string timer() > 66 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 67 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 68 { os << "{ "; > 69 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 70 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 71 void verify_case(const int& Expected, const int& Received) { > 72 bool ok = (Expected == Received); > 73 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 74 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 75 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 76 #define END verify_case(_, DropCoins().getMinimum(board, K));} > 77 int main(){ > 78 > 79 CASE(0) > 80 string board_[] = {".o.." > 81 ,"oooo" > 82 ,"..o."} > 83 ; > 84 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 85 int K = 3; > 86 int _ = 2; > 87 END > 88 CASE(1) > 89 string board_[] = {".....o" > 90 ,"......" > 91 ,"oooooo" > 92 ,"oooooo" > 93 ,"......" > 94 ,"o....."} > 95 ; > 96 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 97 int K = 12; > 98 int _ = 3; > 99 END > 100 CASE(2) > 101 string board_[] = {"...." > 102 ,".oo." > 103 ,".oo." > 104 ,"...."} > 105 ; > 106 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 107 int K = 3; > 108 int _ = -1; > 109 END > 110 CASE(3) > 111 string board_[] = {"......." > 112 ,"..ooo.." > 113 ,"ooooooo" > 114 ,".oo.oo." > 115 ,"oo...oo"} > 116 ; > 117 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 118 int K = 12; > 119 int _ = 4; > 120 END > 121 CASE(4) > 122 string board_[] = {"................." > 123 ,".ooooooo...oooo.." > 124 ,".ooooooo..oooooo." > 125 ,".oo.......oo..oo." > 126 ,".oo.......oo..oo." > 127 ,".ooooo.....oooo.." > 128 ,".ooooooo...oooo.." > 129 ,".....ooo..oo..oo." > 130 ,"......oo..oo..oo." > 131 ,".ooooooo..oooooo." > 132 ,".oooooo....oooo.." > 133 ,"................."} > 134 ; > 135 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 136 int K = 58; > 137 int _ = 6; > 138 END > 139 CASE(5) > 140 string board_[] = {"oooooooooooooooooooooooooooooo", > 141 "oooooooooooooooooooooooooooooo", > 142 "oooooooooooooooooooooooooooooo", > 143 "oooooooooooooooooooooooooooooo", > 144 "oooooooooooooooooooooooooooooo", > 145 "oooooooooooooooooooooooooooooo", > 146 "oooooooooooooooooooooooooooooo", > 147 "oooooooooooooooooooooooooooooo", > 148 "oooooooooooooooooooooooooooooo", > 149 "oooooooooooooooooooooooooooooo", > 150 "oooooooooooooooooooooooooooooo", > 151 "oooooooooooooooooooooooooooooo", > 152 "oooooooooooooooooooooooooooooo", > 153 "oooooooooooooooooooooooooooooo", > 154 "oooooooooooooooooooooooooooooo", > 155 "oooooooooooooooooooooooooooooo", > 156 "oooooooooooooooooooooooooooooo", > 157 "oooooooooooooooooooooooooooooo", > 158 "oooooooooooooooooooooooooooooo", > 159 "oooooooooooooooooooooooooooooo", > 160 "oooooooooooooooooooooooooooooo", > 161 "oooooooooooooooooooooooooooooo", > 162 "oooooooooooooooooooooooooooooo", > 163 "oooooooooooooooooooooooooooooo", > 164 "oooooooooooooooooooooooooooooo", > 165 "oooooooooooooooooooooooooooooo", > 166 "oooooooooooooooooooooooooooooo", > 167 "oooooooooooooooooooooooooooooo", > 168 "oooooooooooooooooooooooooooooo", > 169 "oooooooooooooooooooooooooooooo", > 170 }; > 171 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 172 int K = 1; > 173 int _ = 58; > 174 END > 175 /* > 176 CASE(6) > 177 string board_[] = ; > 178 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 179 int K = ; > 180 int _ = ; > 181 END > 182 */ > 183 } > 184 // END CUT HERE
Added SRM/525-U/1B.cpp version [1cfc045ea674117f]
> 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 Rumor { public: > 29 int getMinimum(string knowledge, vector <string> graph) > 30 { > 31 const int N = knowledge.size(); > 32 const int ALL = (1<<N) - 1; > 33 > 34 // Turn the input into bit-vectors. > 35 int know=0; > 36 for(int v=0; v<N; ++v) > 37 know |= (knowledge[v]=='Y') << v; > 38 vector<int> g(N); > 39 for(int v=0; v<N; ++v) > 40 for(int u=0; u<N; ++u) > 41 g[v] |= (graph[v][u]=='Y') << u; > 42 > 43 // Try all possible patterns (which rumor each rabit spreads fir > 44 int best = N+1; > 45 for(int preferA=0; preferA<(1<<N); ++preferA) > 46 for(int knowA=know, knowB=know, didA=0, didB=0, step=0; > 47 if( knowA==ALL && knowB==ALL ) > 48 {best=step; break;} > 49 > 50 int doA=0, doB=0; > 51 for(int v=0; v<N; ++v) { > 52 bool a_ok = (knowA & 1<<v) && !(didA & 1 > 53 bool b_ok = (knowB & 1<<v) && !(didB & 1 > 54 doA |= (a_ok && b_ok && (preferA & 1<<v) > 55 doB |= (a_ok && b_ok && !(preferA & 1<<v > 56 } > 57 didA |= doA; > 58 didB |= doB; > 59 for(int v=0; v<N; ++v) { > 60 if(doA & 1<<v) knowA |= g[v]; > 61 if(doB & 1<<v) knowB |= g[v]; > 62 } > 63 } > 64 return best==N+1 ? -1 : best; > 65 } > 66 }; > 67 > 68 // BEGIN CUT HERE > 69 #include <ctime> > 70 double start_time; string timer() > 71 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 72 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 73 { os << "{ "; > 74 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 75 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 76 void verify_case(const int& Expected, const int& Received) { > 77 bool ok = (Expected == Received); > 78 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 79 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 80 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 81 #define END verify_case(_, Rumor().getMinimum(knowledge, graph));} > 82 int main(){ > 83 > 84 CASE(0) > 85 string knowledge = "YNN"; > 86 string graph_[] = {"NYN" > 87 ,"NNY" > 88 ,"NNN"}; > 89 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 90 int _ = 3; > 91 END > 92 CASE(1) > 93 string knowledge = "YNNY"; > 94 string graph_[] = {"NYYN" > 95 ,"YNNY" > 96 ,"YNNY" > 97 ,"NYYN"}; > 98 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 99 int _ = 1; > 100 END > 101 CASE(2) > 102 string knowledge = "YYYY"; > 103 string graph_[] = {"NYNN" > 104 ,"YNYN" > 105 ,"NYNY" > 106 ,"NNYN"}; > 107 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 108 int _ = 0; > 109 END > 110 CASE(3) > 111 string knowledge = "YYYYYN"; > 112 string graph_[] = {"NYYYYN" > 113 ,"YNYYYN" > 114 ,"YYNYYN" > 115 ,"YYYNYN" > 116 ,"YYYYNN" > 117 ,"NNNNNN"}; > 118 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 119 int _ = -1; > 120 END > 121 CASE(4) > 122 string knowledge = "NNNY"; > 123 string graph_[] = {"NNNN" > 124 ,"YNNN" > 125 ,"YNNN" > 126 ,"NYYN"}; > 127 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 128 int _ = 3; > 129 END > 130 CASE(5) > 131 string knowledge = "NNNNNNNYYY"; > 132 string graph_[] = {"NYNNYNNYNN" > 133 ,"NNYNYNNNNY" > 134 ,"YYNNNYNNNN" > 135 ,"YNNNYNYNNN" > 136 ,"NNYNNYNNYN" > 137 ,"NNNNYNNNYY" > 138 ,"NYNYNYNNNN" > 139 ,"NNNNNNYNYY" > 140 ,"NNNYNNNYNY" > 141 ,"NYYNNNNYNN"} > 142 ; > 143 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 144 int _ = 2; > 145 END > 146 CASE(6) > 147 string knowledge = "YYYNNN"; > 148 string graph_[] = { > 149 "NNNYNY", > 150 "NNNYYN", > 151 "NNNNYY", > 152 "NNNNNN", > 153 "NNNNNN", > 154 "NNNNNN" > 155 }; > 156 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 157 int _ = 2; > 158 END > 159 /* > 160 CASE(7) > 161 string knowledge = ; > 162 string graph_[] = ; > 163 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 164 int _ = ; > 165 END > 166 */ > 167 } > 168 // END CUT HERE