uppga.c (3734B)
1 #include "common.h" 2 3 static inline void printopt(uint8_t *opt, size_t nopt) { 4 size_t i; 5 for (i = 0; i < nopt; i++) { 6 printf("%hhu ", opt[i]); 7 } 8 printf("\n"); 9 } 10 11 static inline int affordable(size_t rtype, const blueprint *bp, state *s) { 12 size_t i; 13 for (i = 0; i < MTYPES; i++) { 14 if (s->nmin[i] < bp->c[rtype][i]) 15 return 0; 16 } 17 return 1; 18 } 19 20 static inline int verbose_affordable(size_t rtype, const blueprint *bp, 21 state *s) { 22 size_t i; 23 for (i = 0; i < MTYPES; i++) { 24 printf("%llu ?< %llu\n", s->nmin[i], bp->c[rtype][i]); 25 if (s->nmin[i] < bp->c[rtype][i]) 26 return 0; 27 } 28 return 1; 29 } 30 31 size_t try_opt(uint64_t *score, uint8_t *opt, size_t nopt, 32 const blueprint *bp) { 33 size_t i, j; 34 state s = start_state(); 35 for (i = 0; i < nopt; i++) { 36 switch (opt[i]) { 37 case DONOTHING: 38 for (j = 0; j < MTYPES; j++) 39 s.nmin[j] += s.nrob[j]; 40 break; 41 case BUILDORE: 42 if (affordable(ORE, bp, &s) == 0) 43 return i; 44 for (j = 0; j < MTYPES; j++) { 45 s.nmin[j] += s.nrob[j]; 46 s.nmin[j] -= bp->c[ORE][j]; 47 } 48 s.nrob[ORE]++; 49 break; 50 case BUILDCLA: 51 if (affordable(CLA, bp, &s) == 0) { 52 return i; 53 } 54 for (j = 0; j < MTYPES; j++) { 55 s.nmin[j] += s.nrob[j]; 56 s.nmin[j] -= bp->c[CLA][j]; 57 } 58 s.nrob[CLA]++; 59 break; 60 case BUILDOBS: 61 if (affordable(OBS, bp, &s) == 0) 62 return i; 63 for (j = 0; j < MTYPES; j++) { 64 s.nmin[j] += s.nrob[j]; 65 s.nmin[j] -= bp->c[OBS][j]; 66 } 67 s.nrob[OBS]++; 68 break; 69 case BUILDGEO: 70 if (affordable(GEO, bp, &s) == 0) 71 return i; 72 for (j = 0; j < MTYPES; j++) { 73 s.nmin[j] += s.nrob[j]; 74 s.nmin[j] -= bp->c[GEO][j]; 75 } 76 s.nrob[GEO]++; 77 break; 78 default: 79 printopt(opt, nopt); 80 assert(1 == 2); 81 } 82 } 83 84 *score = s.nmin[GEO]; 85 // printf("*score = %llu\n", *score); 86 return i; 87 } 88 89 static inline int increment(uint8_t *opt, size_t nopt) { 90 int i = nopt - 1; 91 while (i >= 0 && opt[i] == NOPT - 1) { 92 opt[i] = 0; 93 i--; 94 } 95 96 if (i < 0) { 97 return -1; 98 } 99 100 opt[i]++; 101 return (0); 102 } 103 104 uint64_t wouldbescore(uint8_t *opt, size_t nopt) { 105 uint64_t r = 0; 106 uint64_t i; 107 for (i = 0; i < nopt; i++) { 108 if (opt[i] == BUILDGEO) { 109 r += (nopt - 1 - i); 110 } 111 } 112 return r; 113 } 114 115 static inline int decrement(uint8_t *opt, size_t nopt, size_t i, uint64_t max) { 116 do { 117 int j = i; 118 if (j == nopt) 119 j--; 120 121 while (j >= 0 && opt[j] == 0) 122 j--; 123 if (j < 0) 124 return -1; 125 126 opt[j]--; 127 memset(&opt[j + 1], NOPT - 1, nopt - j - 1); 128 } while (wouldbescore(opt, nopt) <= max); 129 130 return 0; 131 } 132 133 int main(int argc, char **argv) { 134 char **lines; 135 size_t nlines = readlines(&lines, "input"); 136 printf("#lines: %lu\n", nlines); 137 138 blueprint *bps = parse(lines, nlines); 139 140 size_t i; 141 for (i = 0; i < nlines; i++) { 142 printf("--- %zu ---\n", i); 143 print_blueprint(&bps[i]); 144 } 145 146 uint64_t tot = 0; 147 148 for (i = 0; i < nlines; i++) { 149 uint8_t opt[24]; 150 memset(opt, NOPT - 1, 24); 151 size_t sk = 0; 152 uint64_t max = 0; 153 uint64_t tmp = 0; 154 do { 155 // printopt(opt, 24); 156 sk = try_opt(&tmp, opt, 24, &bps[i]); 157 if (tmp > max) { 158 max = tmp; 159 } 160 // printf("sk = %zu\n", sk); 161 // if(sk < 13) { 162 // printopt(opt, 24); 163 // printf("max = %llu\n", max); 164 // printf("sk = %zu\n", sk); 165 // } 166 // for(i = sk+1; i < 24; i++) opt[i] = NOPT-1; 167 } while (decrement(opt, 24, sk, max) != -1); 168 169 printf("(%zu) max = %llu\n", i, max); 170 tot += (i + 1) * max; 171 } 172 173 printf("tot = %llu\n", tot); 174 }