Overview
| SHA1 Hash: | 29d1d6cd263ca71cc3de824d8126df4469b47bc8 |
|---|---|
| Date: | 2012-07-21 14:43:06 |
| User: | kinaba |
| Comment: | 549 |
| 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/549-U/1A.cpp version [9fc4b0d6d011b0bd]
> 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 typedef int vert; > 23 typedef vert edge; > 24 typedef vector<edge> edges; > 25 typedef vector<edges> graph; > 26 > 27 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) > 28 { > 29 for(int i=0; i<G[v].size(); ++i) { > 30 vert u = G[v][i]; > 31 if( visited[u] ) continue; > 32 visited[u] = true; > 33 > 34 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) > 35 { matchTo[v]=u, matchTo[u]=v; return true; } > 36 } > 37 return false; > 38 } > 39 > 40 template<int NV> > 41 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right > 42 { > 43 vector<vert> matchTo(G.size(), -1); > 44 int ans = 0; > 45 for(vert v=0; v<L; ++v) { > 46 bool visited[NV] = {}; > 47 if( augment(G, v, matchTo, visited) ) > 48 ++ans; > 49 } > 50 return ans; > 51 } > 52 > 53 class PointyWizardHats { public: > 54 int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <i > 55 { > 56 int L = topHeight.size(); > 57 int R = bottomHeight.size(); > 58 graph G(L+R); > 59 for(int i=0; i<L; ++i) > 60 for(int k=0; k<R; ++k) > 61 if( ok(topHeight[i], topRadius[i], bottomHeight[ > 62 G[i].push_back(L+k); > 63 return biMatch<100>(G, L); > 64 } > 65 > 66 bool ok(int th, int tr, int bh, int br) > 67 { > 68 if( th*br > bh*tr ) { > 69 return br > tr; > 70 } > 71 return false; > 72 } > 73 }; > 74 > 75 // BEGIN CUT HERE > 76 #include <ctime> > 77 double start_time; string timer() > 78 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 79 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 80 { os << "{ "; > 81 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 82 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 83 void verify_case(const int& Expected, const int& Received) { > 84 bool ok = (Expected == Received); > 85 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 86 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 87 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 88 #define END verify_case(_, PointyWizardHats().getNumHats(topHeight, topRadi > 89 int main(){ > 90 > 91 CASE(0) > 92 int topHeight_[] = {30}; > 93 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 94 int topRadius_[] = {3}; > 95 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 96 int bottomHeight_[] = {3}; > 97 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 98 int bottomRadius_[] = {30}; > 99 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 100 int _ = 1; > 101 END > 102 CASE(1) > 103 int topHeight_[] = {4,4}; > 104 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 105 int topRadius_[] = {4,3}; > 106 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 107 int bottomHeight_[] = {5,12}; > 108 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 109 int bottomRadius_[] = {5,4}; > 110 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 111 int _ = 1; > 112 END > 113 CASE(2) > 114 int topHeight_[] = {3}; > 115 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 116 int topRadius_[] = {3}; > 117 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 118 int bottomHeight_[] = {1,1}; > 119 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 120 int bottomRadius_[] = {2,4}; > 121 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 122 int _ = 1; > 123 END > 124 CASE(3) > 125 int topHeight_[] = {10,10}; > 126 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 127 int topRadius_[] = {2,5}; > 128 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 129 int bottomHeight_[] = {2,9}; > 130 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 131 int bottomRadius_[] = {3,6}; > 132 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 133 int _ = 2; > 134 END > 135 CASE(4) > 136 int topHeight_[] = {3,4,5}; > 137 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 138 int topRadius_[] = {5,4,3}; > 139 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 140 int bottomHeight_[] = {3,4,5}; > 141 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 142 int bottomRadius_[] = {3,8,5}; > 143 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 144 int _ = 2; > 145 END > 146 CASE(5) > 147 int topHeight_[] = {1,2,3,4,5}; > 148 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 149 int topRadius_[] = {2,3,4,5,6}; > 150 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 151 int bottomHeight_[] = {2,3,4,5,6}; > 152 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 153 int bottomRadius_[] = {1,2,3,4,5}; > 154 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 155 int _ = 0; > 156 END > 157 CASE(6) > 158 int topHeight_[] = {123,214,232,323,342,343}; > 159 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 160 int topRadius_[] = {123,123,232,123,323,434}; > 161 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 162 int bottomHeight_[] = {545,322,123,545,777,999}; > 163 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 164 int bottomRadius_[] = {323,443,123,656,767,888}; > 165 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 166 int _ = 5; > 167 END > 168 CASE(7) > 169 int topHeight_[] = {999,999,999,10000,10000,10000}; > 170 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 171 int topRadius_[] = {10000,10000,10000,1,2,3}; > 172 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 173 int bottomHeight_[] = {2324,2323,234,5454,323,232}; > 174 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 175 int bottomRadius_[] = {1,2,3222,434,5454,23}; > 176 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 177 int _ = 3; > 178 END > 179 /* > 180 CASE(8) > 181 int topHeight_[] = ; > 182 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 183 int topRadius_[] = ; > 184 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 185 int bottomHeight_[] = ; > 186 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 187 int bottomRadius_[] = ; > 188 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 189 int _ = ; > 190 END > 191 CASE(9) > 192 int topHeight_[] = ; > 193 vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeo > 194 int topRadius_[] = ; > 195 vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeo > 196 int bottomHeight_[] = ; > 197 vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHe > 198 int bottomRadius_[] = ; > 199 vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRa > 200 int _ = ; > 201 END > 202 */ > 203 } > 204 // END CUT HERE
Added SRM/549-U/1B.cpp version [124cec5a706621e0]
> 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 MagicalHats { public: > 23 int NC, NH, H, W, NG; > 24 vector<int> gain; > 25 vector< pair<int,int> > hats; > 26 vector<int> tate_base, yoko_base; > 27 > 28 int findMaximumReward(vector <string> board, vector <int> coins, int num > 29 { > 30 NC = coins.size(); > 31 sort(coins.begin(), coins.end()); > 32 gain.assign(NC+1, 0); > 33 partial_sum(coins.begin(), coins.end(), gain.begin()+1); > 34 > 35 H = board.size(); > 36 W = board[0].size(); > 37 hats.clear(); > 38 tate_base.resize(W); > 39 yoko_base.resize(H); > 40 for(int y=0; y<H; ++y) > 41 for(int x=0; x<W; ++x) > 42 if(board[y][x] == 'H') { > 43 hats.push_back( make_pair(y,x) ); > 44 tate_base[x]++; > 45 yoko_base[y]++; > 46 } > 47 NH = hats.size(); > 48 NG = numGuesses; > 49 > 50 int m = 0; > 51 for(int i=0; i<NH; ++i) > 52 m = m*3 + 2; > 53 p_memo.resize(m+1); > 54 p_memo_set.resize(m+1); > 55 b_memo.resize(m+1); > 56 b_memo_set.resize(m+1); > 57 return is_possible(m) ? gain[best_num(m, NG)] : -1; > 58 } > 59 > 60 vector<bool> p_memo; > 61 vector<bool> p_memo_set; > 62 bool is_possible(int state) > 63 { > 64 if(p_memo_set[state]) > 65 return p_memo[state]; > 66 p_memo_set[state] = true; > 67 > 68 vector<int> yoko = yoko_base, tate = tate_base, next; > 69 int cnt = 0; > 70 for(int i=0,m=1; i<NH; ++i,m*=3) > 71 { > 72 int v = (state/m)%3; > 73 if( v == 1 ) { > 74 int y = hats[i].first; > 75 int x = hats[i].second; > 76 yoko[y]++; > 77 tate[x]++; > 78 ++cnt; > 79 } else if( v == 2 ) { > 80 next.push_back(m); > 81 } > 82 } > 83 if( next.empty() ) > 84 { > 85 if( cnt != NC ) > 86 return false; > 87 for(int y=0; y<yoko.size(); ++y) > 88 if(yoko[y]%2 != 0) > 89 return p_memo[state] = false; > 90 for(int x=0; x<tate.size(); ++x) > 91 if(tate[x]%2 != 0) > 92 return p_memo[state] = false; > 93 return p_memo[state] = true; > 94 } > 95 else > 96 { > 97 int m = next[0]; > 98 int s[] = {state-2*m, state-m}; > 99 return p_memo[state] = ( is_possible(s[0]) || is_possibl > 100 } > 101 } > 102 > 103 vector<char> b_memo; > 104 vector<bool> b_memo_set; > 105 char best_num(int state, int guess) > 106 { > 107 if( guess==0 ) > 108 return 0; > 109 if(b_memo_set[state]) > 110 return b_memo[state]; > 111 b_memo_set[state] = true; > 112 > 113 char best = 0; > 114 for(int i=0,m=1; i<NH; ++i,m*=3) > 115 { > 116 int v = (state/m)%3; > 117 if( v == 2 ) > 118 { > 119 int s[] = {state-2*m, state-m}; > 120 char score = 13; > 121 if( is_possible(s[0]) ) > 122 score = min(score, best_num(s[0], guess- > 123 if( is_possible(s[1]) ) > 124 score = min<char>(score, best_num(s[1], > 125 best = max(best, score); > 126 } > 127 } > 128 return b_memo[state] = best; > 129 } > 130 }; > 131 > 132 // BEGIN CUT HERE > 133 #include <ctime> > 134 double start_time; string timer() > 135 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 136 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 137 { os << "{ "; > 138 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 139 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 140 void verify_case(const int& Expected, const int& Received) { > 141 bool ok = (Expected == Received); > 142 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 143 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 144 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 145 #define END verify_case(_, MagicalHats().findMaximumReward(board, coins, nu > 146 int main(){ > 147 > 148 CASE(0) > 149 string board_[] = {"H"}; > 150 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 151 int coins_[] = {1}; > 152 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 153 int numGuesses = 1; > 154 int _ = 1; > 155 END > 156 CASE(1) > 157 string board_[] = {"HHH", > 158 "H.H", > 159 "HH."}; > 160 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 161 int coins_[] = {9}; > 162 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 163 int numGuesses = 1; > 164 int _ = 9; > 165 END > 166 CASE(2) > 167 string board_[] = {"HH", > 168 "HH"}; > 169 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 170 int coins_[] = {1,2,3,4}; > 171 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 172 int numGuesses = 3; > 173 int _ = 6; > 174 END > 175 CASE(3) > 176 string board_[] = {"HHH", > 177 "HHH", > 178 "H.H"}; > 179 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 180 int coins_[] = {13,13,13,13}; > 181 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 182 int numGuesses = 2; > 183 int _ = 13; > 184 END > 185 CASE(4) > 186 string board_[] = {"HHH", > 187 "HHH", > 188 "H.H"}; > 189 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 190 int coins_[] = {13,13,13,13}; > 191 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 192 int numGuesses = 3; > 193 int _ = 26; > 194 END > 195 CASE(5) > 196 string board_[] = {"H.H.", > 197 ".H.H", > 198 "H.H."}; > 199 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 200 int coins_[] = {17}; > 201 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 202 int numGuesses = 6; > 203 int _ = -1; > 204 END > 205 CASE(6) > 206 string board_[] = {"HHH..........", > 207 "H.H..........", > 208 "HHH..........", > 209 "H.H..........", > 210 "HHH.........." > 211 ".............", > 212 ".............", > 213 ".............", > 214 ".............", > 215 ".............", > 216 ".............", > 217 ".............", > 218 ".............", > 219 }; > 220 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 221 int coins_[] = {33,337,1007,2403,5601,6003,9999}; > 222 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 223 int numGuesses = 5; > 224 int _ = 1377; > 225 END > 226 CASE(7) > 227 string board_[] = {".............", > 228 ".............", > 229 ".............", > 230 ".............", > 231 ".............", > 232 ".............", > 233 ".....H.H.....", > 234 "......H......", > 235 ".....H.H.....", > 236 ".............", > 237 ".............", > 238 ".............", > 239 "............."}; > 240 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 241 int coins_[] = {22}; > 242 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 243 int numGuesses = 3; > 244 int _ = 22; > 245 END > 246 /* > 247 CASE(8) > 248 string board_[] = ; > 249 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 250 int coins_[] = ; > 251 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 252 int numGuesses = ; > 253 int _ = ; > 254 END > 255 CASE(9) > 256 string board_[] = ; > 257 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 258 int coins_[] = ; > 259 vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_)); > 260 int numGuesses = ; > 261 int _ = ; > 262 END > 263 */ > 264 } > 265 // END CUT HERE