fork download
copy 
  1. // Errichto - med
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define FOR(i,a,n) for(int i = (a); i <= (n); ++i)
  5. #define FORD(i,a,n) for(int i = (a); i >= (n); --i)
  6. #define REP(i,n) FOR(i,0,(n)-1)
  7. #define RI(i,n) FOR(i,1,(n))
  8. #define pb push_back
  9. #define mp make_pair
  10. #define st first
  11. #define nd second
  12. #define mini(a,b) a=min(a,(b))
  13. #define maxi(a,b) a=max(a,(b))
  14. #define sz(w) (int)w.size()
  15. typedef vector<int> vi;
  16. typedef long long ll;
  17. typedef long double ld;
  18. typedef pair<int,int> pii;
  19. const int inf = 1e9 + 5;
  20. const int nax = 305;
  21.  
  22. // from UW2015's library
  23. namespace MinCost{ // 0 .. n
  24.   struct Edge{
  25.     int w,c,v,rev;
  26.     Edge(int _w, int _c, int _v, int _rev) :
  27.       w(_w), c(_c), v(_v), rev(_rev)
  28.     {}
  29.   };
  30.  
  31.   int odl[nax], pot[nax], pop[nax], pop_kraw[nax];
  32.   int q[nax], qbeg, qend;
  33.   vector<Edge> v[nax];
  34.   bool bylo[nax];
  35.   queue<int> kolej;
  36.  
  37.   void init(int n) {
  38.     FOR(i,0,n) v[i].clear();
  39.   }
  40.  
  41.   void AddEdge(int a, int b, int cap, int cost) {
  42.     v[a].pb(Edge(b,cap,cost,int(v[b].size()) + (a == b)));
  43.     v[b].pb(Edge(a,0,-cost,int(v[a].size()-1)));
  44.   }
  45.  
  46.   pair<int,int> MinCostMaxFlow(int s, int t, int n) {
  47.     int flow = 0, cost = 0;
  48.  
  49.     while (true) {
  50.       FOR(i,0,n) {
  51.         odl[i] = inf;
  52.         bylo[i] = false;
  53.       }
  54.       bylo[s] = true;
  55.       odl[s] = 0;
  56.       kolej.push(s);
  57.  
  58.       //djikstra, mozna napisac na kolejce
  59.       while(!kolej.empty()) {
  60.         int x = kolej.front();
  61.         kolej.pop();
  62.         bylo[x] = false;
  63.         int dl = v[x].size();
  64.         REP(i,dl) if (v[x][i].c > 0 && 
  65.           odl[v[x][i].w] > 
  66.             odl[x] + pot[x] - pot[v[x][i].w] + v[x][i].v) {
  67.           odl[v[x][i].w] = 
  68.             odl[x] + pot[x] - pot[v[x][i].w] + v[x][i].v;
  69.           if (!bylo[v[x][i].w]) {
  70.             kolej.push(v[x][i].w);
  71.             bylo[v[x][i].w] = true;
  72.           }
  73.           pop[v[x][i].w] = x; pop_kraw[v[x][i].w] = i; 
  74.         } 
  75.       }
  76.  
  77.       if (odl[t] == inf)
  78.         break;
  79.  
  80.       int x = t;
  81.       int cap = inf;
  82.       while (x != s) {
  83.         cap = min(cap, v[pop[x]][pop_kraw[x]].c);
  84.         x = pop[x];
  85.       }
  86.  
  87.       flow += cap;
  88.       x = t;
  89.       while (x != s) {
  90.         cost += v[pop[x]][pop_kraw[x]].v*cap;
  91.         v[pop[x]][pop_kraw[x]].c -= cap;
  92.         v[x][v[pop[x]][pop_kraw[x]].rev].c += cap;
  93.         x = pop[x];
  94.       }
  95.     }
  96.  
  97.     return mp(flow, cost);
  98.   }
  99. };
  100.  
  101. bool isLucky(int a) { return a==44||a==47||a==74||a==77||a==444||a==447; }
  102.  
  103. int row4[nax], col4[nax], row7[nax], col7[nax];
  104.  
  105. int solve11(vector<string> grid) {
  106. 	int n = sz(grid); assert(n == 11);
  107. 	// only 4s
  108. 	bool ok = true;
  109. 	REP(i, n) if(row7[i] > 1 || col7[i] > 1) ok = false;
  110. 	if(ok) {
  111. 		int a = 0;
  112. 		REP(i, n) a += row7[i];
  113. 		// printf("only fours = %d\n", a);
  114. 		return n*n*4+a*3;
  115. 	}
  116. 	int alot = 4, mi = 7;
  117. 	int RES = inf;
  118. 	REP(_, 2) {
  119. 		swap(alot, mi);
  120. 		REP(X, 12) REP(Y, 12) {
  121. 			REP(xx, 12) REP(yy, 12) if(xx != X && yy != Y) REP(kind, 2) {
  122. 				// kind == 0 - holes in lines
  123. 				// kind == 1 - extra cell
  124. 				bool ok = true;
  125. 				int cnt7 = 0;
  126. 				REP(y, n) REP(x, n) {
  127. 					int good = alot;
  128. 					if(x == X && y != yy) good = mi;
  129. 					if(y == Y && x != xx) good = mi;
  130. 					if(kind) if(x == xx && y == yy) good = mi;
  131. 					if(grid[y][x] != '.' && grid[y][x] != '0' + good)
  132. 						ok = false;
  133. 					if(good == 7) cnt7++;
  134. 				}
  135. 				if(ok) mini(RES, cnt7);
  136. 			}
  137. 		}
  138. 	}
  139. 	ok = true;
  140. 	REP(i, n) if(row4[i] > 1 || col4[i] > 1) ok = false;
  141. 	if(ok) {
  142. 		REP(y, n) if(row4[y] == 0)
  143. 			REP(x, n) if(col4[x] == 0)
  144. 				if(grid[y][x] == '.')
  145. 					MinCost :: AddEdge(x+1, n+y+1, 1, 0);
  146. 		REP(x, n) MinCost :: AddEdge(0, x+1, 1, 0);
  147. 		REP(y, n) MinCost :: AddEdge(n+y+1, 2*n+1, 1, 0);
  148. 		int match = MinCost :: MinCostMaxFlow(0, 2*n+1, 2*n+1).st;
  149. 		// printf("match = %d\n", match);
  150. 		REP(i, n) match += row4[i];
  151. 		mini(RES, n * n - match);
  152. 	}
  153. 	if(RES == inf) return -1;
  154. 	return n*n*4 + RES * 3;
  155. }
  156.  
  157. class LuckyGrid {
  158. 	public : int findMinimumSum(vector<string> grid) {
  159. 		int n = sz(grid);
  160. 		if(n == 1) {
  161. 			if(grid[0][0] == '7') return 7;
  162. 			return 4;
  163. 		}
  164. 		int goal = -1;
  165. 		FOR(x, 0, n) if(isLucky(x * 4 + (n-x) * 7)) {
  166. 			goal = x;
  167. 			break;
  168. 		}
  169. 		if(goal == -1) return -1;
  170. 		assert(isLucky((goal+1)*4 + (n-(goal+1))*7));
  171. 		assert(goal+1 <= n);
  172. 		// goal or goal+1 or n=11
  173. 		REP(y, n) REP(x, n) {
  174. 			if(grid[y][x] == '4') {
  175. 				row4[y]++;
  176. 				col4[x]++;
  177. 			}
  178. 			else if(grid[y][x] == '7') {
  179. 				row7[y]++;
  180. 				col7[x]++;
  181. 			}
  182. 		}
  183. 		if(n == 11) return solve11(grid);
  184. 		REP(y, n) REP(x, n)
  185. 			if(grid[y][x] == '.')
  186. 				MinCost :: AddEdge(x+1, n+y+1, 1, 1);
  187. 		const int C = 100 * 1000;
  188. 		int wanted = 0;
  189. 		REP(x, n) {
  190. 			if(col4[x] > goal+1) return -1;
  191. 			if(col4[x] == goal+1) {}
  192. 			else {
  193. 				wanted += goal - col4[x];
  194. 				MinCost :: AddEdge(0, x+1, goal-col4[x], 0);
  195. 				MinCost :: AddEdge(0, x+1, 1, C);
  196. 			}
  197.  
  198. 		}
  199. 		REP(y, n) {
  200. 			if(row4[y] > goal+1) return -1;
  201. 			if(row4[y] == goal+1) {}
  202. 			else {
  203. 				wanted += goal - row4[y];
  204. 				MinCost :: AddEdge(n+1+y, 2*n+1, goal-row4[y], 0);
  205. 				MinCost :: AddEdge(n+1+y, 2*n+1, 1, C);
  206. 			}
  207. 		}
  208. 		pair<int,int> flow = MinCost :: MinCostMaxFlow(0, 2*n+1, 2*n+1);
  209. 		// printf("%d\n", wanted); // 18
  210. 		// printf("%d %d\n", flow.st, flow.nd); // 25 1400025
  211. 		if(flow.nd/C + wanted != 2*flow.st) return -1;
  212. 		int fours = flow.st;
  213. 		REP(x, n) fours += col4[x];
  214. 		return fours * 4 + (n * n - fours) * 7;
  215. 	}
  216. };
  217.  
  218. int main(int argc, char * argv[]) {
  219. 	LuckyGrid a;
  220. 	vector<string> in = {"774777..", "..4.....", "..7774..", "..7..7..", "..7..7..", "..7..74.", "..4..4..", "........"};
  221. 	vector<string> in11 = {".4......7..", "...........", ".....7.....", "...........", ".7......7..", "...........", ".....4.....", "...........", "........4..", "...........", "..........."};
  222. 	vector<string> in3 = {"77744477", "44747777", "74747477", "47747477", "........", "........", "........", "........"};
  223. 	printf("%d\n", a.findMinimumSum(in));
  224. 	return 0;
  225. }
  226.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
355
https://ideone.com/RM1YrR
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!