Overview
| SHA1 Hash: | c9008fc6676a002f549bec8c719d746b57276c46 |
|---|---|
| Date: | 2012-08-08 11:48:59 |
| User: | kinaba |
| Comment: | 549 1C done. |
| 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
Deleted 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 <int> bottomHeight, vector <int> bottomRadius) 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[k], bottomRadius[k]) ) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 86 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 87 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 88 -#define END verify_case(_, PointyWizardHats().getNumHats(topHeight, topRadius, bottomHeight, bottomRadius));} 89 -int main(){ 90 - 91 -CASE(0) 92 - int topHeight_[] = {30}; 93 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 94 - int topRadius_[] = {3}; 95 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 96 - int bottomHeight_[] = {3}; 97 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 98 - int bottomRadius_[] = {30}; 99 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 100 - int _ = 1; 101 -END 102 -CASE(1) 103 - int topHeight_[] = {4,4}; 104 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 105 - int topRadius_[] = {4,3}; 106 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 107 - int bottomHeight_[] = {5,12}; 108 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 109 - int bottomRadius_[] = {5,4}; 110 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 111 - int _ = 1; 112 -END 113 -CASE(2) 114 - int topHeight_[] = {3}; 115 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 116 - int topRadius_[] = {3}; 117 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 118 - int bottomHeight_[] = {1,1}; 119 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 120 - int bottomRadius_[] = {2,4}; 121 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 122 - int _ = 1; 123 -END 124 -CASE(3) 125 - int topHeight_[] = {10,10}; 126 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 127 - int topRadius_[] = {2,5}; 128 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 129 - int bottomHeight_[] = {2,9}; 130 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 131 - int bottomRadius_[] = {3,6}; 132 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 133 - int _ = 2; 134 -END 135 -CASE(4) 136 - int topHeight_[] = {3,4,5}; 137 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 138 - int topRadius_[] = {5,4,3}; 139 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 140 - int bottomHeight_[] = {3,4,5}; 141 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 142 - int bottomRadius_[] = {3,8,5}; 143 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 144 - int _ = 2; 145 -END 146 -CASE(5) 147 - int topHeight_[] = {1,2,3,4,5}; 148 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 149 - int topRadius_[] = {2,3,4,5,6}; 150 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 151 - int bottomHeight_[] = {2,3,4,5,6}; 152 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 153 - int bottomRadius_[] = {1,2,3,4,5}; 154 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 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_)/sizeof(*topHeight_)); 160 - int topRadius_[] = {123,123,232,123,323,434}; 161 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 162 - int bottomHeight_[] = {545,322,123,545,777,999}; 163 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 164 - int bottomRadius_[] = {323,443,123,656,767,888}; 165 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 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_)/sizeof(*topHeight_)); 171 - int topRadius_[] = {10000,10000,10000,1,2,3}; 172 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 173 - int bottomHeight_[] = {2324,2323,234,5454,323,232}; 174 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 175 - int bottomRadius_[] = {1,2,3222,434,5454,23}; 176 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 177 - int _ = 3; 178 -END 179 -/* 180 -CASE(8) 181 - int topHeight_[] = ; 182 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 183 - int topRadius_[] = ; 184 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 185 - int bottomHeight_[] = ; 186 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 187 - int bottomRadius_[] = ; 188 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 189 - int _ = ; 190 -END 191 -CASE(9) 192 - int topHeight_[] = ; 193 - vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_)); 194 - int topRadius_[] = ; 195 - vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_)); 196 - int bottomHeight_[] = ; 197 - vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_)); 198 - int bottomRadius_[] = ; 199 - vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_)); 200 - int _ = ; 201 -END 202 -*/ 203 -} 204 -// END CUT HERE
Deleted 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 numGuesses) 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_possible(s[1]) ); 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-1)); 123 - if( is_possible(s[1]) ) 124 - score = min<char>(score, best_num(s[1], guess-1)+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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 143 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 144 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 145 -#define END verify_case(_, MagicalHats().findMaximumReward(board, coins, numGuesses));} 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
Name change from from SRM/549-U/1A.cpp to SRM/549/1A.cpp.
Name change from from SRM/549-U/1B.cpp to SRM/549/1B.cpp.
Added SRM/549/1C.cpp version [fede1c18ad40c4e3]
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 +template<typename Vert, typename Flow, int NV=16> 23 +class MaxFlow 24 +{ 25 + vector<int> G[NV]; 26 + Flow F[NV][NV]; 27 + 28 +public: 29 + void addEdge( Vert s, Vert t, Flow f ) 30 + { 31 + G[s].push_back(t); 32 + G[t].push_back(s); 33 + F[s][t] = f; 34 + F[t][s] = 0; 35 + } 36 + 37 + Flow calc( Vert S, Vert D ) 38 + { 39 + for( Flow total=0 ;; ) { 40 + // Do BFS and compute the level for each node. 41 + int LV[NV] = {0}; 42 + vector<int> Q(1, S); 43 + for(int lv=1; !Q.empty(); ++lv) { 44 + vector<int> Q2; 45 + for(size_t i=0; i!=Q.size(); ++i) { 46 + const vector<int>& ne = G[Q[i]]; 47 + for(size_t j=0; j!=ne.size(); ++j) 48 + if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S ) 49 + LV[ne[j]]=lv, Q2.push_back(ne[j]); 50 + } 51 + Q.swap(Q2); 52 + } 53 + 54 + // Destination is now unreachable. Done. 55 + if( !LV[D] ) 56 + return total; 57 + 58 + // Iterating DFS. 59 + bool blocked[NV] = {}; 60 + total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); 61 + } 62 + } 63 + 64 +private: 65 + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) 66 + { 67 + Flow flow_out = 0; 68 + for(size_t i=0; i!=G[v].size(); ++i) { 69 + int u = G[v][i]; 70 + if( LV[v]+1==LV[u] && F[v][u] ) { 71 + Flow f = min(flow_in-flow_out, F[v][u]); 72 + if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) { 73 + F[v][u] -= f; 74 + F[u][v] += f; 75 + flow_out += f; 76 + if( flow_in == flow_out ) return flow_out; 77 + } 78 + } 79 + } 80 + blocked[v] = (flow_out==0); 81 + return flow_out; 82 + } 83 +}; 84 + 85 +class CosmicBlocks { public: 86 + vector<int> blockTypes; 87 + int N, minWays, maxWays; 88 + 89 + int getNumOrders(vector <int> blockTypes_, int minWays_, int maxWays_) 90 + { 91 + N = blockTypes_.size(); 92 + blockTypes = blockTypes_; 93 + minWays = minWays_; 94 + maxWays = maxWays_; 95 + return try_all_latitude(); 96 + } 97 + 98 + int try_all_latitude() 99 + { 100 + vector<int> lat; 101 + return rec_assign_latitude(&lat, (1<<N)-1, 0x7fffffff); 102 + } 103 + 104 + int rec_assign_latitude(vector<int>* lat, int mask, int prev_lat_blocks) 105 + { 106 + if( mask == 0 ) 107 + return try_all_touching_releation(*lat); 108 + 109 + int total = 0; 110 + for(int m=1; m<=mask; ++m) if( (m&mask)==m ) { 111 + int sum = 0; 112 + for(int i=0; (1<<i)<=m; ++i) if(1<<i & m) 113 + sum+=blockTypes[i]; 114 + if( prev_lat_blocks >= sum ) { 115 + lat->push_back(m); 116 + total += rec_assign_latitude(lat, mask&~m, sum); 117 + lat->pop_back(); 118 + } 119 + } 120 + return total; 121 + } 122 + 123 + int try_all_touching_releation(const vector<int>& lat) 124 + { 125 + int total = 0; 126 + 127 + vector<int> fst = elements(lat[0]); 128 + vector< pair<int,int> > adj = adjacent_blocks(lat); 129 + for(int m=0; m<(1<<adj.size()); ++m) 130 + { 131 + vector< vector<int> > up(N); 132 + up.push_back(fst); 133 + for(int i=0; (1<<i)<=m; ++i) if(1<<i & m) 134 + up[adj[i].first].push_back(adj[i].second); 135 + 136 + if( !possible(up) ) 137 + continue; 138 + int ways = calc_ways(up); 139 + if( minWays<=ways && ways<=maxWays ) 140 + ++total; 141 + } 142 + return total; 143 + } 144 + 145 + vector<int> elements(int mask) 146 + { 147 + vector<int> result; 148 + for(int i=0; (1<<i)<=mask; ++i) if(1<<i & mask) 149 + result.push_back(i); 150 + return result; 151 + } 152 + 153 + vector< pair<int,int> > adjacent_blocks(const vector<int>& lat) 154 + { 155 + vector< pair<int,int> > result; 156 + for(int i=1; i<lat.size(); ++i) 157 + for(int a=0; (1<<a)<=lat[i-1]; ++a) if(1<<a & lat[i-1]) 158 + for(int b=0; (1<<b)<=lat[i]; ++b) if(1<<b & lat[i]) 159 + result.push_back(make_pair(a,b)); 160 + return result; 161 + } 162 + 163 + int calc_ways(const vector< vector<int> >& up) 164 + { 165 + vector<int> governed(N); 166 + for(int i=0; i<up.size(); ++i) 167 + for(int k=0; k<up[i].size(); ++k) 168 + governed[up[i][k]] ++; 169 + 170 + // trivial check 2 171 + for(int i=0; i<governed.size(); ++i) 172 + if(governed[i] == 0) 173 + return 0; 174 + 175 + vector<int> memo(1<<N, -1); 176 + return calc_ways_rec(N, (1<<N)-1, up, governed, memo); 177 + } 178 + 179 + int calc_ways_rec(int i, int mask, const vector< vector<int> >& up, vector<int>& governed, 180 + vector<int>& memo) 181 + { 182 + if(mask == 0) 183 + return 1; 184 + if(memo[mask] != -1) 185 + return memo[mask]; 186 + 187 + int sum = 0; 188 + 189 + for(int k=0; k<up[i].size(); ++k) governed[up[i][k]]--; 190 + { 191 + for(int k=0; k<governed.size(); ++k) 192 + if(!governed[k] && (mask & 1<<k)) 193 + sum += calc_ways_rec(k, mask &~ (1<<k), up, governed, memo); 194 + } 195 + for(int k=0; k<up[i].size(); ++k) governed[up[i][k]]++; 196 + 197 + return memo[mask] = sum; 198 + } 199 + 200 + bool possible(const vector< vector<int> >& up) 201 + { 202 + static const int INF = 0x3fffffff; 203 + 204 + int total = accumulate(blockTypes.begin(), blockTypes.end(), 0); 205 + 206 + MaxFlow<int, int> mf; 207 + vector<int> out = blockTypes, in = blockTypes; 208 + for(int v=0; v<=N; ++v) { 209 + for(int i=0; i<up[v].size(); ++i) { 210 + int u = up[v][i]; 211 + mf.addEdge(v, N+1+u, INF); 212 + if(v<N) {in[v] -= 1; if(in[v]<0) return false; } 213 + out[u] -= 1; if(out[u]<0) return false; 214 + total -= 1; 215 + } 216 + } 217 + for(int v=0; v<=N; ++v) 218 + if(v == N) { 219 + mf.addEdge(N+1+N, v, INF); 220 + } else { 221 + mf.addEdge(N+1+N, v, in[v]); 222 + mf.addEdge(N+1+v, N+1+N+1, out[v]); 223 + } 224 + return mf.calc(N+1+N, N+1+N+1) == total; 225 + } 226 +}; 227 + 228 +// BEGIN CUT HERE 229 +#include <ctime> 230 +double start_time; string timer() 231 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 232 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 233 + { os << "{ "; 234 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 235 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 236 +void verify_case(const int& Expected, const int& Received) { 237 + bool ok = (Expected == Received); 238 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 239 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 240 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 241 +#define END verify_case(_, CosmicBlocks().getNumOrders(blockTypes, minWays, maxWays));} 242 +int main(){ 243 + 244 +CASE(0) 245 + int blockTypes_[] = {2,2,2}; 246 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 247 + int minWays = 1; 248 + int maxWays = 1; 249 + int _ = 6; 250 +END 251 +CASE(1) 252 + int blockTypes_[] = {1,1,1,1,1,1}; 253 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 254 + int minWays = 720; 255 + int maxWays = 720; 256 + int _ = 1; 257 +END 258 +CASE(2) 259 + int blockTypes_[] = {2,2}; 260 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 261 + int minWays = 1; 262 + int maxWays = 2; 263 + int _ = 3; 264 +END 265 +CASE(3) 266 + int blockTypes_[] = {1,2}; 267 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 268 + int minWays = 1; 269 + int maxWays = 2; 270 + int _ = 2; 271 +END 272 +CASE(4) 273 + int blockTypes_[] = {1}; 274 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 275 + int minWays = 1; 276 + int maxWays = 1; 277 + int _ = 1; 278 +END 279 +CASE(5) 280 + int blockTypes_[] = {1,2,4,8}; 281 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 282 + int minWays = 5; 283 + int maxWays = 30; 284 + int _ = 27; 285 +END 286 +CASE(6) 287 + int blockTypes_[] = {1,2,3,4,5,6}; 288 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 289 + int minWays = 1; 290 + int maxWays = 720; 291 + int _ = 4445; 292 +END 293 +CASE(7) 294 + int blockTypes_[] = {7500,1000,7500,1000,7500}; 295 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 296 + int minWays = 8; 297 + int maxWays = 88; 298 + int _ = 448; 299 +END 300 +/* 301 +CASE(8) 302 + int blockTypes_[] = ; 303 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 304 + int minWays = ; 305 + int maxWays = ; 306 + int _ = ; 307 +END 308 +CASE(9) 309 + int blockTypes_[] = ; 310 + vector <int> blockTypes(blockTypes_, blockTypes_+sizeof(blockTypes_)/sizeof(*blockTypes_)); 311 + int minWays = ; 312 + int maxWays = ; 313 + int _ = ; 314 +END 315 +*/ 316 +} 317 +// END CUT HERE