#include #include #include #include static struct Rule { char name[32]; int a[2]; int b[2]; } rules[32]; static int nrules; struct Ticket { int fields[32]; }; static bool parse(struct Ticket *ticket) { for (int i = 0; i < nrules; ++i) { if (scanf("%d,", &ticket->fields[i]) < 1) return false; } scanf("\n"); return true; } static bool check(const struct Rule *rule, int field) { return (field >= rule->a[0] && field <= rule->a[1]) || (field >= rule->b[0] && field <= rule->b[1]); } int main(void) { for (;;) { struct Rule rule; scanf("%[^:]: ", rule.name); if (!strcmp(rule.name, "your ticket")) break; scanf( "%d-%d or %d-%d\n", &rule.a[0], &rule.a[1], &rule.b[0], &rule.b[1] ); rules[nrules++] = rule; } struct Ticket mine; parse(&mine); scanf("nearby tickets:\n"); struct Ticket nearby[256]; int len; for (len = 0; parse(&nearby[len]); ++len); int error = 0; struct Ticket valids[256]; int vlen = 0; for (int i = 0; i < len; ++i) { bool ticket = true; for (int j = 0; j < nrules; ++j) { bool field = false; for (int r = 0; r < nrules; ++r) { if (!check(&rules[r], nearby[i].fields[j])) continue; field = true; break; } if (!field) { error += nearby[i].fields[j]; ticket = false; } } if (ticket) valids[vlen++] = nearby[i]; } printf("%d\n", error); int map[32] = {0}; for (int r = 0; r < nrules; ++r) { for (int f = 0; f < nrules; ++f) { bool valid = true; for (int i = 0; i < vlen; ++i) { if (check(&rules[r], valids[i].fields[f])) continue; valid = false; break; } if (valid) map[r] |= 1 << f; } } for (bool done = false; !done;) { for (int i = 0; i < nrules; ++i) { if (__builtin_popcount(map[i]) > 1) continue; for (int j = 0; j < nrules; ++j) { if (j != i) map[j] &= ~map[i]; } } done = true; for (int i = 0; i < nrules; ++i) { if (__builtin_popcount(map[i]) > 1) done = false; } } for (int i = 0; i < nrules; ++i) { map[i] = __builtin_ctz(map[i]); } long departure = 1; for (int i = 0; i < nrules; ++i) { if (strncmp(rules[i].name, "departure", 9)) continue; departure *= mine.fields[map[i]]; } printf("%ld\n", departure); }