uppgb.c (6141B)
1 #include "common.h" 2 3 #define PRECALCULATE_LEVELS 8 4 5 #define MAX(x, y) (x < y ? y : x) 6 7 static inline void printopt(uint8_t *opt, size_t nopt) { 8 size_t i; 9 for (i = 0; i < nopt; i++) { 10 printf("%hhu ", opt[i]); 11 } 12 printf("\n"); 13 } 14 15 static inline int affordable(size_t rtype, const blueprint *bp, state *s) { 16 size_t i; 17 for (i = 0; i < MTYPES; i++) { 18 if (s->nmin[i] < bp->c[rtype][i]) 19 return 0; 20 } 21 return 1; 22 } 23 24 size_t try_opt(uint64_t *score, uint8_t *opt, size_t nopt, const blueprint *bp, 25 uint64_t *pc, size_t npc) { 26 size_t i, j; 27 state s = start_state(); 28 for (i = 0; i < nopt - PRECALCULATE_LEVELS; i++) { 29 switch (opt[i]) { 30 case DONOTHING: 31 for (j = 0; j < MTYPES; j++) 32 s.nmin[j] += s.nrob[j]; 33 break; 34 case BUILDORE: 35 if (affordable(ORE, bp, &s) == 0) 36 return i; 37 for (j = 0; j < MTYPES; j++) { 38 s.nmin[j] += s.nrob[j]; 39 s.nmin[j] -= bp->c[ORE][j]; 40 } 41 s.nrob[ORE]++; 42 break; 43 case BUILDCLA: 44 if (affordable(CLA, bp, &s) == 0) 45 return i; 46 for (j = 0; j < MTYPES; j++) { 47 s.nmin[j] += s.nrob[j]; 48 s.nmin[j] -= bp->c[CLA][j]; 49 } 50 s.nrob[CLA]++; 51 break; 52 case BUILDOBS: 53 if (affordable(OBS, bp, &s) == 0) 54 return i; 55 for (j = 0; j < MTYPES; j++) { 56 s.nmin[j] += s.nrob[j]; 57 s.nmin[j] -= bp->c[OBS][j]; 58 } 59 s.nrob[OBS]++; 60 break; 61 case BUILDGEO: 62 if (affordable(GEO, bp, &s) == 0) 63 return i; 64 for (j = 0; j < MTYPES; j++) { 65 s.nmin[j] += s.nrob[j]; 66 s.nmin[j] -= bp->c[GEO][j]; 67 } 68 s.nrob[GEO]++; 69 break; 70 default: 71 printopt(opt, nopt); 72 assert(1 == 2); 73 } 74 } 75 76 uint64_t lmax = 0; 77 for (i = 0; i < npc; i++) { 78 if (pc[i * (MTYPES + 1) + 0] <= s.nmin[0] && 79 pc[i * (MTYPES + 1) + 1] <= s.nmin[1] && 80 pc[i * (MTYPES + 1) + 2] <= s.nmin[2]) { 81 lmax = MAX(lmax, 82 pc[i * (MTYPES + 1) + 4] + s.nrob[GEO] * PRECALCULATE_LEVELS); 83 } 84 } 85 86 *score = lmax; 87 // printf("*score = %llu\n", *score); 88 return nopt - PRECALCULATE_LEVELS - 1; 89 } 90 91 size_t try_min(uint8_t *opt, size_t nopt, const blueprint *bp, size_t type, 92 uint64_t v) { 93 size_t i, j; 94 state s = empty_state(); 95 for (i = 0; i < MTYPES; i++) 96 s.nmin[i] = 10000000000L; 97 s.nmin[type] = v; 98 99 for (i = 0; i < nopt; i++) { 100 switch (opt[i]) { 101 case DONOTHING: 102 for (j = 0; j < MTYPES; j++) 103 s.nmin[j] += s.nrob[j]; 104 break; 105 case BUILDORE: 106 if (affordable(ORE, bp, &s) == 0) 107 return i; 108 for (j = 0; j < MTYPES; j++) { 109 s.nmin[j] += s.nrob[j]; 110 s.nmin[j] -= bp->c[ORE][j]; 111 } 112 s.nrob[ORE]++; 113 break; 114 case BUILDCLA: 115 if (affordable(CLA, bp, &s) == 0) 116 return i; 117 for (j = 0; j < MTYPES; j++) { 118 s.nmin[j] += s.nrob[j]; 119 s.nmin[j] -= bp->c[CLA][j]; 120 } 121 s.nrob[CLA]++; 122 break; 123 case BUILDOBS: 124 if (affordable(OBS, bp, &s) == 0) 125 return i; 126 for (j = 0; j < MTYPES; j++) { 127 s.nmin[j] += s.nrob[j]; 128 s.nmin[j] -= bp->c[OBS][j]; 129 } 130 s.nrob[OBS]++; 131 break; 132 case BUILDGEO: 133 if (affordable(GEO, bp, &s) == 0) 134 return i; 135 for (j = 0; j < MTYPES; j++) { 136 s.nmin[j] += s.nrob[j]; 137 s.nmin[j] -= bp->c[GEO][j]; 138 } 139 s.nrob[GEO]++; 140 break; 141 default: 142 printopt(opt, nopt); 143 assert(1 == 2); 144 } 145 } 146 147 return i; 148 } 149 150 uint64_t minimum_needed(uint8_t *opt, size_t nopt, const blueprint *bp, 151 size_t type) { 152 uint64_t nd = 0; 153 while (try_min(opt, nopt, bp, type, nd) < nopt) { 154 nd++; 155 } 156 return nd; 157 } 158 159 void precalculate(uint64_t *pc, uint8_t *opt, size_t nopt, 160 const blueprint *bp) { 161 size_t i, j; 162 163 for (i = 0; i < MTYPES; i++) { 164 pc[i] = minimum_needed(opt, nopt, bp, i); 165 } 166 167 pc[MTYPES] = 0; 168 for (i = 0; i < nopt; i++) { 169 if (opt[i] == BUILDGEO) { 170 pc[MTYPES] += nopt - 1 - i; 171 } 172 } 173 } 174 175 uint64_t wouldbescore(uint8_t *opt, size_t nopt) { 176 uint64_t r = 0; 177 uint64_t i; 178 for (i = 0; i < nopt; i++) { 179 if (opt[i] == BUILDGEO) { 180 r += (nopt - 1 - i); 181 } 182 } 183 return r; 184 } 185 186 static inline int decrement(uint8_t *opt, size_t nopt, size_t i, uint64_t max) { 187 do { 188 int j = i; 189 if (j == nopt) 190 j--; 191 192 while (j >= 0 && opt[j] == 0) 193 j--; 194 if (j < 0) 195 return -1; 196 197 opt[j]--; 198 memset(&opt[j + 1], NOPT - 1, nopt - j - 1); 199 } while (wouldbescore(opt, nopt) <= max); 200 201 return 0; 202 } 203 204 int main(int argc, char **argv) { 205 char **lines; 206 size_t nlines = readlines(&lines, "input"); 207 printf("#lines: %lu\n", nlines); 208 209 blueprint *bps = parse(lines, nlines); 210 211 size_t i, j; 212 for (i = 0; i < 3; i++) { 213 printf("--- %zu ---\n", i); 214 print_blueprint(&bps[i]); 215 } 216 217 uint64_t tot = 1; 218 219 size_t precalculate_size = 1; 220 for (i = 0; i < PRECALCULATE_LEVELS; i++) 221 precalculate_size *= NOPT; 222 printf("precalculate size = %zu\n", precalculate_size); 223 uint64_t pc[precalculate_size * (MTYPES + 1)]; 224 for (i = 0; i < precalculate_size; i++) { 225 uint64_t ti = i; 226 uint8_t opt[PRECALCULATE_LEVELS]; 227 printf("precalculate\n"); 228 for (j = 0; j < PRECALCULATE_LEVELS; j++) { 229 opt[j] = ti % NOPT; 230 ti /= NOPT; 231 } 232 printopt(opt, PRECALCULATE_LEVELS); 233 precalculate(&pc[i * (MTYPES + 1)], opt, PRECALCULATE_LEVELS, &bps[0]); 234 printf(">> %llu %llu %llu %llu %llu\n", pc[i * (MTYPES + 1)], 235 pc[i * (MTYPES + 1) + 1], pc[i * (MTYPES + 1) + 2], 236 pc[i * (MTYPES + 1) + 3], pc[i * (MTYPES + 1) + 4]); 237 } 238 239 for (i = 0; i < 3; i++) { 240 uint8_t opt[32]; 241 memset(opt, NOPT - 1, 32); 242 size_t sk = 0; 243 uint64_t max = 0; 244 uint64_t tmp = 0; 245 do { 246 // printopt(opt, 24); 247 sk = try_opt(&tmp, opt, 32, &bps[i], pc, precalculate_size); 248 if (tmp > max) { 249 max = tmp; 250 printf("new max = %llu\n", max); 251 } 252 } while (decrement(opt, 32, sk, max) != -1); 253 254 printf("(%zu) max = %llu\n", i, max); 255 tot *= max; 256 } 257 258 printf("tot = %llu\n", tot); 259 }