fork download
  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
stdin
Standard input is empty
stdout
355