#include #include #include #include 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"))); }