Source code for submission s845

Go to diff to previous submission

fm.cpp

  1. /*
  2. 5 5 3 1
  3. .....
  4. .X...
  5. .XXX.
  6. .XXX.
  7. .XXX.
  8. 5 10 2 3
  9. .......XX.
  10. .X....XX..
  11. .XXX......
  12. .XXX......
  13. .XXX......
  14. 3 3 3 3
  15. XXX
  16. XXX
  17. XXX
  18. 3 3 2 2
  19. XXX
  20. XXX
  21. XXX
  22. 3 3 2 2
  23. XX.
  24. XXX
  25. XXX
  26. 17 32 5 9
  27. ........XXXXXXXX................
  28. ........XXXXXXXX................
  29. ........XXXXXXXX................
  30. ........XXXXXXXXX...............
  31. ........XXXXXXXXXXXXXXX.........
  32. ........XXXXXXXXXXXXXXXXXXXX....
  33. ........XXXXXXXXXXXXXXXXXXXXX...
  34. XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
  35. ..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
  36. ....XXXXXXXXXXXXXXXXXXXXXXXXXXX.
  37. ......XXXXXXXXXXXXXXXXXXXXXXXXX.
  38. ........XX..XXXXXXXXXXXXXXXXX...
  39. .............XXXXXXXXXXXXXX.....
  40. ...............XXXXXXXXX........
  41. ................XXXXXXX.........
  42. .................XXXXX..........
  43. ....................XXX.........
  44.  */
  45.  
  46. #include <cstdio>
  47. #include <cstdlib>
  48. #include <cmath>
  49. #include <algorithm>
  50. #include <utility>
  51. #include <string>
  52. #include <deque>
  53. #include <list>
  54. #include <map>
  55. #include <queue>
  56. #include <set>
  57. #include <stack>
  58. #include <vector>
  59. using namespace std;
  60.  
  61. #define debug printf
  62. //#define debug blackhole
  63. void blackhole(...) {}
  64.  
  65. #define MAXN 3000
  66.  
  67. int Ar,Ac,Tr,Tc;
  68. bool TAKEN[MAXN][MAXN]; // [Ar][Ac]
  69.  
  70. int P[MAXN][MAXN]; // !!! od -Tr, -Tc do Ar, Ac
  71. int Q[MAXN][MAXN];
  72.  
  73. inline int is_taken(int x, int y) {
  74. if (x < 0 || y < 0 || x >= Ar || y >= Ac) return 0;
  75. return TAKEN[x][y] ? 1 : 0;
  76. }
  77.  
  78. void build() {
  79. for (int i=0;i<MAXN;i++) {
  80. for (int j=0;j<MAXN;j++) {
  81. P[i][j] = 0; Q[i][j] = 0;
  82. }
  83. }
  84. for (int r = -Tr; r < Ar + Tr; r++){
  85. for (int c = -Tc; c < Ac + Tc; c++) {
  86. P[r+Tr][c+Tc+1] += P[r+Tr][c+Tc] + is_taken(r, c + Tc) - is_taken(r, c);
  87. }
  88. }
  89. for (int c = -Tc; c < Ac + Ac; c++) {
  90. for (int r = -Tr; r < Ar + Ar; r++) {
  91. Q[r+Tr+1][c+Tc] += Q[r+Tr][c+Tc] + P[r+Tr+Tr][c+Tc] - P[r+Tr][c+Tc];
  92. }
  93. }
  94. }
  95.  
  96. bool free_tile(int sx, int sy) {
  97. return Q[sx+Tr][sy+Tc] == 0;
  98. }
  99.  
  100. long tiles_needed_for(int dx, int dy) {
  101. long taken = 0;
  102. debug("dx=%d dy=%d => ", dx,dy);
  103. for (int qx = -dx; qx < Ar; qx+=Tr) {
  104. for (int qy = -dy; qy < Ac; qy+=Tc) {
  105. if (!free_tile(qx,qy)) {
  106. taken += 1;
  107. debug("(%d,%d) ", qx,qy);
  108. }
  109. }
  110. }
  111. debug(" ---> %ld\n", taken);
  112. return taken;
  113. }
  114.  
  115. void debug_R_Q() {
  116. debug("vstup: \n");
  117. for (int r=-Tr; r<Ar+Tr; r++) {
  118. for (int c = -Tc; c<Ac+Tc; c++) {
  119. debug(" %c ", is_taken(r,c) ? 'X' : '.');
  120. }
  121. debug("\n");
  122. }
  123. debug("\n");
  124.  
  125. debug("P: \n");
  126. for (int r=-Tr; r<Ar+Tr; r++) {
  127. for (int c = -Tc; c<Ac+Tc; c++) {
  128. if (!P[r+Tr][c+Tc]) {
  129. debug(" . ");
  130. } else {
  131. debug("%02d ", P[r+Tr][c+Tc]);
  132. }
  133. }
  134. debug("\n");
  135. }
  136. debug("\n");
  137.  
  138. debug("Q: \n");
  139. for (int r=-Tr; r<Ar+Tr; r++) {
  140. for (int c = -Tc; c<Ac+Tc; c++) {
  141. if (!Q[r+Tr][c+Tc]) {
  142. debug(" . ");
  143. } else {
  144. debug("%02d ", Q[r+Tr][c+Tc]);
  145. }
  146. }
  147. debug("\n");
  148. }
  149. debug("\n");
  150. }
  151.  
  152. void solve() {
  153. build();
  154. debug_R_Q();
  155. long best = -1;
  156. for (int dx = 0; dx < Tr; dx++) {
  157. for (int dy = 0; dy < Tc; dy++) {
  158. long tiles = tiles_needed_for(dx, dy);
  159. if (best == -1 || best > tiles) {
  160. best = tiles;
  161. }
  162. }
  163. }
  164. printf("%ld\n", best);
  165. }
  166.  
  167. int main() {
  168. while (true) {
  169. if (scanf("%d%d%d%d",&Ar,&Ac,&Tr,&Tc) != 4) break;
  170. for (int i = 0; i < Ar; i++) {
  171. char line[10000];
  172. scanf("%s", line);
  173. for (int j=0;j<Ac;j++) {
  174. TAKEN[i][j] = line[j] == 'X';
  175. }
  176. }
  177. solve();
  178. }
  179. return 0;
  180. }
  181.  

Diff to submission s825

fm.cpp

--- c5.s825.cteam032.fm.cpp.0.fm.cpp
+++ c5.s845.cteam032.fm.cpp.0.fm.cpp
@@ -1,2 +1,47 @@
+/*
+5 5 3 1
+.....
+.X...
+.XXX.
+.XXX.
+.XXX.
+5 10 2 3
+.......XX.
+.X....XX..
+.XXX......
+.XXX......
+.XXX......
+3 3 3 3
+XXX
+XXX
+XXX
+3 3 2 2
+XXX
+XXX
+XXX
+3 3 2 2
+XX.
+XXX
+XXX
+17 32 5 9
+........XXXXXXXX................
+........XXXXXXXX................
+........XXXXXXXX................
+........XXXXXXXXX...............
+........XXXXXXXXXXXXXXX.........
+........XXXXXXXXXXXXXXXXXXXX....
+........XXXXXXXXXXXXXXXXXXXXX...
+XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..
+..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX.
+....XXXXXXXXXXXXXXXXXXXXXXXXXXX.
+......XXXXXXXXXXXXXXXXXXXXXXXXX.
+........XX..XXXXXXXXXXXXXXXXX...
+.............XXXXXXXXXXXXXX.....
+...............XXXXXXXXX........
+................XXXXXXX.........
+.................XXXXX..........
+....................XXX.........
+ */
+
 #include <cstdio>
 #include <cstdlib>
@@ -14,13 +59,15 @@
 using namespace std;
 
-//#define debug printf
-#define debug blackhole
+#define debug printf
+//#define debug blackhole
 void blackhole(...) {}
 
+#define MAXN 3000
+
 int Ar,Ac,Tr,Tc;
-bool TAKEN[2000][2000]; // [Ar][Ac]
+bool TAKEN[MAXN][MAXN]; // [Ar][Ac]
 
-int P[2000][2000]; // !!! od -Tr, -Tc do Ar, Ac
-int Q[2000][2000];
+int P[MAXN][MAXN]; // !!! od -Tr, -Tc do Ar, Ac
+int Q[MAXN][MAXN];
 
 inline int is_taken(int x, int y) {
@@ -30,6 +77,6 @@
 
 void build() {
-        for (int i=0;i<2000;i++) {
-                for (int j=0;j<2000;j++) {
+        for (int i=0;i<MAXN;i++) {
+                for (int j=0;j<MAXN;j++) {
                         P[i][j] = 0; Q[i][j] = 0;
                 }