clean.cpp (6426B)
1 #include <algorithm> 2 #include <cstdio> 3 #include <vector> 4 5 using namespace std; 6 7 #define MAXR 77 8 #define MAXC 302 9 #define MAXL 2252 10 #define MAXA 11 11 #define MAXT 402 12 #define MAXB 54 13 14 int R, C, A, L, V, B, T, rs, cs; 15 16 struct Pt{ 17 int r, c; 18 Pt(int r=0, int c=0) : r(r), c(c) {} 19 }; 20 21 // global variables: no need to initalize, can be larger than what fits in stack 22 vector<int> cov[MAXR][MAXC]; // which targets are covered by a loon at (r, c) 23 Pt dest[MAXA][MAXR][MAXC]; // where a loon at (a, r, c) is moved; (-1, -1) = out 24 Pt target[MAXL]; // position of target cells 25 bool covered[MAXT][MAXL]; // at time t, is target cell l covered yet? 26 // dynamic programming: best score at (t, a, r, c) and best direction 27 int best[MAXT][MAXA][MAXR][MAXC], dir[MAXT][MAXA][MAXR][MAXC]; 28 int left[MAXT][MAXR][MAXC]; // number of new cells covered at (r, c) at time t 29 // solution: at time t, altitude adjustment for loon b 30 int solution[MAXT][MAXB]; 31 32 // given by problem statement 33 int columndist(int c1, int c2) { return min(abs(c1 - c2), C - abs(c1 - c2)); } 34 // does a loon at (r, c) cover target cell l? 35 int iscovered(int l, int r, int c) { 36 int u = target[l].r, v = target[l].c; 37 return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V); 38 } 39 40 // return next move for loon b at time t when at position (a, r, c)... 41 // ... using the results of dynamic programming 42 int decide_dyn(int b, int t, int a, int r, int c) { return dir[t][a][r][c]; } 43 // ... using the computed solution 44 int decide_sol(int b, int t, int a, int r, int c) { return solution[t][b]; } 45 46 int simulate(int b, int (*decide)(int, int, int, int, int)) { 47 // compute the run of loon b using decision function decide 48 // return the score improvement 49 int score = 0; 50 int r = rs, c = cs, a = 0; 51 for (int t = 0; t < T; t++) { 52 int bestda = (*decide)(b, t, a, r, c); 53 // store the move 54 solution[t][b] = bestda; 55 // apply it 56 a += bestda; 57 Pt next = dest[a][r][c]; 58 r = next.r; 59 c = next.c; 60 if (r < 0) 61 break; // loon exited 62 if (a > 0) { 63 // update covered target cells 64 for (unsigned int i = 0; i < cov[r][c].size(); i++) { 65 int l = cov[r][c][i]; 66 // score improved if target cell not already covered 67 score += covered[t+1][l] ? 0 : 1; 68 covered[t+1][l] = true; 69 } 70 } 71 } 72 return score; 73 } 74 75 void route(int b) { 76 // route loon b given the already covered targets (in covered) 77 78 // gain a factor A: precompute the number of uncovered targets for each cell 79 for (int t = 0; t <= T; t++) 80 for (int r = 0; r < R; r++) 81 for (int c = 0; c < C; c++) { 82 int score = 0; 83 for (unsigned int i = 0; i < cov[r][c].size(); i++) { 84 int l = cov[r][c][i]; 85 score += covered[t][l] ? 0 : 1; 86 } 87 left[t][r][c] = score; 88 } 89 90 // dynamic programming, t == T is a sentinel value 91 for (int t = T-1; t >= 0; t--) 92 for (int a = 0; a <= A; a++) 93 for (int r = 0; r < R; r++) 94 for (int c = 0; c < C; c++) { 95 int bestda = 0, bestv = 0; // best altitude adjustment, best value 96 for (int da = -1; da <= 1; da++) { 97 if (a <= 1 && da == -1) 98 continue; // can't go down when on ground, or back on ground 99 if (a + da > A) 100 continue; // can't go above max altitude 101 // pretend we moved b by da at time t 102 Pt next = dest[a + da][r][c]; 103 if (next.r < 0) 104 break; // loon goes out, so score remains 0 105 // score if going at these new coordinates, computed dynamically 106 int rscore = best[t+1][a+da][next.r][next.c]; 107 // if above ground, score increased by number of covered targets 108 if ((a + da) > 0) 109 rscore += left[t+1][next.r][next.c]; 110 // break ties at random 111 if (rscore > bestv || (rscore == bestv && (rand() % 2))) { 112 // da is the best altitude adjustment 113 bestv = rscore; 114 bestda = da; 115 } 116 } 117 // store best altitude adjustment, best value 118 best[t][a][r][c] = bestv; 119 dir[t][a][r][c] = bestda; 120 } 121 } 122 123 void print_sol() { 124 FILE *f = fopen("output", "w"); 125 for (int t = 0; t < T; t++) { 126 for (int b = 0; b < B; b++) 127 fprintf(f, "%d ", solution[t][b]); 128 fprintf(f, "\n"); 129 } 130 fclose(f); 131 } 132 133 int main(int argc, char **argv) { 134 srand(42); // make it deterministic 135 scanf("%d%d%d", &R, &C, &A); 136 scanf("%d%d%d%d", &L, &V, &B, &T); 137 scanf("%d%d", &rs, &cs); 138 for (int l = 0; l < L; l++) { 139 int r, c; 140 scanf("%d%d", &r, &c); 141 target[l] = Pt(r, c); 142 } 143 for (int r = 0; r < R; r++) 144 for (int c = 0; c < C; c++) { 145 } 146 for (int a = 0; a <= A; a++) 147 for (int r = 0; r < R; r++) 148 for (int c = 0; c < C; c++) 149 if (!a) { 150 // wind at altitude 0 does not move loons 151 dest[a][r][c] = Pt(r, c); 152 } else { 153 int dr, dc; 154 scanf("%d%d", &dr, &dc); 155 // populate dest with the coordinates where the wind takes the loon 156 int destr, destc; 157 destr = r + dr; 158 destc = (c + dc + C) % C; 159 if (destr < 0 || destr >= R) 160 destr = destc = -1; // loon goes out 161 dest[a][r][c] = Pt(destr, destc); 162 } 163 164 // compute for each cell the list of targets covered by a loon at this cell 165 for (int r = 0; r < R; r++) 166 for (int c = 0; c < C; c++) 167 for (int l = 0; l < L; l++) 168 if (iscovered(l, r, c)) 169 cov[r][c].push_back(l); 170 171 int orig_score = 0; 172 // iteratively compute a route for each loon given other routes 173 while (true) { 174 for (int br = 0; br < B; br++) { 175 // route br given the routes of the other loons 176 // first, forget about which cells are covered 177 for (int t = 0; t <= T; t++) 178 for (int l = 0; l < L; l++) 179 covered[t][l] = false; 180 // then, simulate the other loons (default routes are 0 ... 0) 181 int score = 0; 182 for (int b = 0; b < B; b++) 183 if (b != br) 184 score += simulate(b, &decide_sol); 185 // now, compute the route of br with dynamic programming 186 route(br); 187 score += simulate(br, &decide_dyn); 188 fprintf(stderr, "route %d\n", br); 189 if (score > orig_score) { 190 fprintf(stderr, "score was %d is %d\n", orig_score, score); 191 orig_score = score; 192 print_sol(); 193 } 194 } 195 } 196 197 return 0; 198 } 199