Overview
| SHA1 Hash: | 47cb6fde79ea073b67c09f41c355d9ff7e29812d |
|---|---|
| Date: | 2013-06-08 15:08:05 |
| User: | kinaba |
| Comment: | 581 |
| 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/581-U/1A.cpp version [0a6601339e127c92]
> 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<double> CMP; > 21 > 22 class SurveillanceSystem { public: > 23 string getContainerInfo(string containers, vector <int> reports, int L) > 24 { > 25 const int N = containers.size(); > 26 > 27 map< int, vector<int> > seen_to_pos; > 28 for(int s=0; s+L<=N; ++s) > 29 seen_to_pos[count(containers.begin()+s, containers.begin > 30 > 31 map<int,int> seen_to_cnt; > 32 for(int i=0; i<reports.size(); ++i) > 33 seen_to_cnt[reports[i]]++; > 34 > 35 string result(N, '-'); > 36 for(map<int,int>::iterator it=seen_to_cnt.begin(); it!=seen_to_c > 37 { > 38 int s = it->first; > 39 int c = it->second; > 40 vector<int>& p = seen_to_pos[s]; > 41 mask(N, L, p, c, result); > 42 } > 43 return result; > 44 } > 45 > 46 // May/must choose |K| ranges out of |p|. Update |result|. > 47 void mask(int N, int L, vector<int>& p, int K, string& result) > 48 { > 49 assert(K > 0); > 50 sort(p.begin(), p.end()); > 51 > 52 // Any range can be watched. > 53 for(int i=0; i<p.size(); ++i) { > 54 for(int x=p[i]; x<p[i]+L; ++x) > 55 if(result[x] == '-') > 56 result[x] = '?'; > 57 } > 58 > 59 // Do "always" check. > 60 for(int x=0; x<N; ++x) { > 61 int cover = 0; > 62 for(int i=0; i<p.size(); ++i) > 63 if(p[i]<=x && x<p[i]+L) > 64 ++cover; > 65 // If |x| is covered by some range but avoiding them lea > 66 if(cover && (p.size()-cover) < K) > 67 result[x] = '+'; > 68 } > 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 string& Expected, const string& Received) { > 81 bool ok = (Expected == Received); > 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(_, SurveillanceSystem().getContainerInfo(containers > 86 int main(){ > 87 > 88 CASE(0) > 89 string containers = "-X--XX"; > 90 int reports_[] = {1, 2}; > 91 vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*repor > 92 int L = 3; > 93 string _ = "??++++"; > 94 END > 95 CASE(1) > 96 string containers = "-XXXXX-"; > 97 int reports_[] = {2}; > 98 vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*repor > 99 int L = 3; > 100 string _ = "???-???"; > 101 END > 102 CASE(2) > 103 string containers = "------X-XX-"; > 104 int reports_[] = {3, 0, 2, 0}; > 105 vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*repor > 106 int L = 5; > 107 string _ = "++++++++++?"; > 108 END > 109 CASE(3) > 110 string containers = "-XXXXX---X--"; > 111 int reports_[] = {2, 1, 0, 1}; > 112 vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*repor > 113 int L = 3; > 114 string _ = "???-??++++??"; > 115 END > 116 CASE(4) > 117 string containers = "-XX--X-XX-X-X--X---XX-X---XXXX-----X"; > 118 int reports_[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}; > 119 vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*repor > 120 int L = 7; > 121 string _ = "???++++?++++++++++++++++++++??????--"; > 122 END > 123 /* > 124 CASE(5) > 125 string containers = ; > 126 int reports_[] = ; > 127 vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*repor > 128 int L = ; > 129 string _ = ; > 130 END > 131 CASE(6) > 132 string containers = ; > 133 int reports_[] = ; > 134 vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*repor > 135 int L = ; > 136 string _ = ; > 137 END > 138 */ > 139 } > 140 // END CUT HERE
Added SRM/581-U/1B.cpp version [0ed1faf3d467caed]
> 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<double> CMP; > 21 > 22 class TreeUnion { public: > 23 double expectedCycles(vector <string> tree1, vector <string> tree2, int > 24 { > 25 vector<int> t1, t2; > 26 { > 27 stringstream sin(accumulate(tree1.begin(), tree1.end(), > 28 for(int v; sin>>v; ) t1.push_back(v); > 29 } > 30 { > 31 stringstream sin(accumulate(tree2.begin(), tree2.end(), > 32 for(int v; sin>>v; ) t2.push_back(v); > 33 } > 34 > 35 int N = t1.size() + 1; > 36 vector<vector<int> > d1 = make_d(t1, N); > 37 vector<vector<int> > d2 = make_d(t2, N); > 38 > 39 map<int, int> len_to_cnt_2; > 40 for(int u=0; u<N; ++u) > 41 for(int v=u+1; v<N; ++v) > 42 len_to_cnt_2[d2[u][v]] += 2; > 43 int total = N * (N-1); > 44 > 45 double e = 0.0; > 46 for(int u=0; u<N; ++u) > 47 for(int v=u+1; v<N; ++v) > 48 { > 49 e += (double)len_to_cnt_2[K - 2 - d1[u][v]] / total; > 50 } > 51 return e; > 52 } > 53 > 54 vector<vector<int> > make_d(const vector<int>& x, int N) > 55 { > 56 vector<vector<int> > d(N, vector<int>(N, 0x3fffffff)); > 57 for(int i=0; i<N; ++i) d[i][i] = 0; > 58 for(int i=0; i<x.size(); ++i) { > 59 d[i+1][x[i]] = 1; > 60 d[x[i]][i+1] = 1; > 61 } > 62 for(int k=0; k<N; ++k) > 63 for(int i=0; i<N; ++i) > 64 for(int j=0; j<N; ++j) > 65 d[i][j] = min(d[i][j], d[i][k]+d[k][j]); > 66 return d; > 67 } > 68 }; > 69 > 70 // BEGIN CUT HERE > 71 #include <ctime> > 72 double start_time; string timer() > 73 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 74 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 75 { os << "{ "; > 76 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 77 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 78 void verify_case(const double& Expected, const double& Received) { > 79 bool ok = (abs(Expected - Received) < 1e-9); > 80 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 81 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 82 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 83 #define END verify_case(_, TreeUnion().expectedCycles(tree1, tree2, K));} > 84 int main(){ > 85 > 86 CASE(0) > 87 string tree1_[] = {"0"}; > 88 vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); > 89 string tree2_[] = {"0"}; > 90 vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); > 91 int K = 4; > 92 double _ = 1.0; > 93 END > 94 CASE(1) > 95 string tree1_[] = {"0 1"}; > 96 vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); > 97 string tree2_[] = {"0 1"}; > 98 vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); > 99 int K = 4; > 100 double _ = 1.3333333333333333; > 101 END > 102 CASE(2) > 103 string tree1_[] = {"0 1"}; > 104 vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); > 105 string tree2_[] = {"0 1"}; > 106 vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); > 107 int K = 6; > 108 double _ = 0.3333333333333333; > 109 END > 110 CASE(3) > 111 string tree1_[] = {"0 ", "1 1 1"}; > 112 vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); > 113 string tree2_[] = {"0 1 0 ", "1"}; > 114 vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); > 115 int K = 5; > 116 double _ = 4.0; > 117 END > 118 CASE(4) > 119 string tree1_[] = {"0 1 2 0 1 2 0 1 2 5 6 1", "0 11", " 4"}; > 120 vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); > 121 string tree2_[] = {"0 1 1 0 2 3 4 3 4 6 6", " 10 12 12"}; > 122 vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); > 123 int K = 7; > 124 double _ = 13.314285714285713; > 125 END > 126 /* > 127 CASE(5) > 128 string tree1_[] = ; > 129 vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); > 130 string tree2_[] = ; > 131 vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); > 132 int K = ; > 133 double _ = ; > 134 END > 135 CASE(6) > 136 string tree1_[] = ; > 137 vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_)); > 138 string tree2_[] = ; > 139 vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_)); > 140 int K = ; > 141 double _ = ; > 142 END > 143 */ > 144 } > 145 // END CUT HERE
Added SRM/581-U/1C.cpp version [6e5343b52571efd5]
> 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<double> CMP; > 21 > 22 static const int INF = 0x1fffffff; > 23 > 24 int bitcnt(int x) > 25 { > 26 int c = 0; > 27 for(; x; x>>=1) > 28 c += x&1; > 29 return c; > 30 } > 31 > 32 class YetAnotherBoardGame { public: > 33 int g_best; > 34 int minimumMoves(vector <string> board) > 35 { > 36 int H = board.size(); > 37 int W = board[0].size(); > 38 vector<int> b(H); > 39 for(int y=0; y<H; ++y) > 40 for(int x=0; x<W; ++x) > 41 b[y] |= (board[y][x]=='W')<<x; > 42 b.push_back(0); // sentinel > 43 > 44 g_best = INF; > 45 for(int type=1; type<=2; ++type) > 46 for(int mask=0; mask<(1<<W); ++mask) > 47 { > 48 int cur = b[0]; > 49 int next = b[1]; > 50 flip(cur, next, mask, type, W); > 51 do_try(cur, next, b, 1, H, W, (type==1 ? mask : > 52 } > 53 return g_best==INF ? -1 : g_best; > 54 } > 55 > 56 void flip(int& cur, int& next, int mask, int type, int W) > 57 { > 58 int pat = (type==1 ? 5 : 7); > 59 for(int f=0; (1<<f)<=mask; ++f) > 60 if((1<<f) & mask) > 61 cur ^= (pat<<f>>1)&((1<<W)-1); > 62 next ^= mask; > 63 } > 64 > 65 void do_try(int prev, int cur, const vector<int>& b, int y, int H, int W > 66 { > 67 if(y==H) { > 68 int score = (prev==0 ? 0 : INF) + acc; > 69 g_best = min(g_best, score); > 70 return; > 71 } > 72 > 73 int mask = prev; > 74 int score = bitcnt(mask) + acc; > 75 if(score >= g_best) > 76 return; > 77 > 78 if(!(mask&must_t2)) { // try type 1 > 79 int curr = cur; > 80 int next = b[y+1]; > 81 flip(curr, next, mask, 1, W); > 82 do_try(curr, next, b, y+1, H, W, must_t1|mask, must_t2, > 83 } > 84 if(!(mask&must_t1)) { // try type 2 > 85 int curr = cur; > 86 int next = b[y+1]; > 87 flip(curr, next, mask, 2, W); > 88 do_try(curr, next, b, y+1, H, W, must_t1, must_t2|mask, > 89 } > 90 } > 91 }; > 92 > 93 // BEGIN CUT HERE > 94 #include <ctime> > 95 double start_time; string timer() > 96 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 97 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 98 { os << "{ "; > 99 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 100 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 101 void verify_case(const int& Expected, const int& Received) { > 102 bool ok = (Expected == Received); > 103 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 104 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 105 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 106 #define END verify_case(_, YetAnotherBoardGame().minimumMoves(board));} > 107 int main(){ > 108 > 109 CASE(0) > 110 string board_[] = {"BBBBBBBBB", > 111 "BBWBBBBBB", > 112 "BWWWBBBBB", > 113 "BBWBBBWBB", > 114 "BBBBBWBWB", > 115 "BBBBBBWBB"}; > 116 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 117 int _ = 2; > 118 END > 119 CASE(1) > 120 string board_[] = {"BBW", > 121 "WWW", > 122 "BWW"}; > 123 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 124 int _ = 2; > 125 END > 126 CASE(2) > 127 string board_[] = {"WBW", > 128 "BBW", > 129 "WBW"}; > 130 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 131 int _ = 4; > 132 END > 133 CASE(3) > 134 string board_[] = {"BBBB", > 135 "WBWB", > 136 "BBBB", > 137 "BBBB"}; > 138 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 139 int _ = -1; > 140 END > 141 CASE(4) > 142 string board_[] = {"WWWWWBW", > 143 "WBWBWBW", > 144 "BBWBBWW"}; > 145 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 146 int _ = 7; > 147 END > 148 CASE(5) > 149 string board_[] = {"WWWWWWWWWW", > 150 "WWWWWWWWWW", > 151 "WWWWWWWWWW", > 152 "WWWWWWWWWW", > 153 "WWWWWWWWWW", > 154 "WWWWWWWWWW", > 155 "WWWWWWWWWW", > 156 "WWWWWWWWWW", > 157 "WWWWWWWWWW", > 158 "WWWWWWWWWW"} > 159 ; > 160 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 161 int _ = 30; > 162 END > 163 /* > 164 CASE(6) > 165 string board_[] = ; > 166 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 167 int _ = ; > 168 END > 169 CASE(7) > 170 string board_[] = ; > 171 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 172 int _ = ; > 173 END > 174 */ > 175 } > 176 // END CUT HERE