uppgb.c (2462B)
1 #include "common.h" 2 3 static uint64_t backmap(uint64_t x, range_t *ranges, size_t *nranges, size_t i, 4 size_t nlines) { 5 size_t j; 6 range_t ran; 7 8 for (j = 0; j < nranges[i]; j++) { 9 ran = ranges[i * nlines + j]; 10 11 if (ran.lb + ran.delta <= x && x <= ran.ub + ran.delta) { 12 return x - ran.delta; 13 } 14 } 15 16 return x; 17 } 18 19 static uint64_t compute_value(uint64_t x, range_t *ranges, size_t *nranges, 20 size_t nlines, size_t np) { 21 size_t i, j; 22 range_t ran; 23 uint64_t cv = x; 24 25 for (i = 0; i < np; i++) { 26 for (j = 0; j < nranges[i]; j++) { 27 ran = ranges[i * nlines + j]; 28 if (ran.lb <= cv && cv <= ran.ub) { 29 cv += ran.delta; 30 break; 31 } 32 } 33 } 34 35 return cv; 36 } 37 38 static int is_in_ranges(uint64_t x, stack_u64 *lbs, stack_u64 *ubs) { 39 size_t i; 40 41 for (i = 0; i < lbs->nmemb; i++) { 42 if (lbs->data[i] <= x && x <= ubs->data[i]) 43 return 1; 44 } 45 46 return 0; 47 } 48 49 int main(int argc, char **argv) { 50 char **lines; 51 size_t nlines = readlines(&lines, "input"); 52 size_t i, j; 53 int u; 54 uint64_t val; 55 uint64_t minval = UINT64_MAX; 56 57 size_t nranges[nlines]; 58 range_t ranges[nlines * nlines]; 59 60 uint64_t np = read_ranges(nranges, ranges, lines, nlines); 61 62 stack_u64 starts = read_starts(lines); 63 stack_u64 lbs, ubs; 64 stack_u64_init(&lbs); 65 stack_u64_init(&ubs); 66 for (i = 0; i < starts.nmemb; i += 2) { 67 stack_u64_push(&lbs, starts.data[i]); 68 stack_u64_push(&ubs, starts.data[i] + starts.data[i + 1] - 1); 69 } 70 71 stack_u64 lowpoints[np]; 72 for (i = 0; i < np; i++) { 73 stack_u64_init(&lowpoints[i]); 74 } 75 76 stack_u64_push(&lowpoints[np - 1], 0); 77 78 u = np - 2; 79 while (u >= 0) { 80 for (j = 0; j < nranges[u]; j++) { 81 stack_u64_push(&lowpoints[u], ranges[u * nlines + j].lb); 82 stack_u64_push(&lowpoints[u], ranges[u * nlines + j].ub + 1); 83 } 84 85 for (j = 0; j < lowpoints[u + 1].nmemb; j++) { 86 stack_u64_push(&lowpoints[u], backmap(lowpoints[u + 1].data[j], ranges, 87 nranges, u, nlines)); 88 } 89 90 u--; 91 } 92 93 for (i = 0; i < lbs.nmemb; i++) { 94 stack_u64_push(&lowpoints[0], lbs.data[i]); 95 } 96 97 for (j = 0; j < lowpoints[0].nmemb; j++) { 98 if (is_in_ranges(lowpoints[0].data[j], &lbs, &ubs)) { 99 val = compute_value(lowpoints[0].data[j], ranges, nranges, nlines, np); 100 if (val < minval) 101 minval = val; 102 } 103 } 104 105 printf("%llu\n", minval); 106 107 return 0; 108 }