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
|
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static struct Bag {
char adj[16];
char col[16];
struct {
int cnt;
char adj[16];
char col[16];
} cons[4];
} bags[600];
static int len;
static int compar(const void *_a, const void *_b) {
const struct Bag *a = _a;
const struct Bag *b = _b;
int ret = strcmp(a->adj, b->adj);
if (ret) return ret;
return strcmp(a->col, b->col);
}
static struct Bag *findBag(const char *adj, const char *col) {
struct Bag needle = {0};
strcpy(needle.adj, adj);
strcpy(needle.col, col);
return bsearch(&needle, bags, len, sizeof(bags[0]), compar);
}
static bool canContain(struct Bag *bag, const char *adj, const char *col) {
for (int i = 0; i < 4; ++i) {
if (!bag->cons[i].cnt) break;
if (!strcmp(bag->cons[i].adj, adj) && !strcmp(bag->cons[i].col, col)) {
return true;
}
if (canContain(findBag(bag->cons[i].adj, bag->cons[i].col), adj, col)) {
return true;
}
}
return false;
}
static int containsCount(struct Bag *bag) {
int count = 0;
for (int i = 0; i < 4; ++i) {
if (!bag->cons[i].cnt) break;
count += bag->cons[i].cnt;
count += bag->cons[i].cnt
* containsCount(findBag(bag->cons[i].adj, bag->cons[i].col));
}
return count;
}
int main(void) {
while (EOF != scanf("%s %s bags contain", bags[len].adj, bags[len].col)) {
for (
int i = 0;
0 < scanf(
"%d %s %s bag%*[s,.]",
&bags[len].cons[i].cnt,
bags[len].cons[i].adj, bags[len].cons[i].col
);
++i
);
scanf("no other bags.");
len++;
}
qsort(bags, len, sizeof(bags[0]), compar);
int count = 0;
for (int i = 0; i < len; ++i) {
if (canContain(&bags[i], "shiny", "gold")) count++;
}
printf("%d\n", count);
printf("%d\n", containsCount(findBag("shiny", "gold")));
}
|