1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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);
}
|