#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


enum worry_op {
	WO_NONE,
	WO_ADD,
	WO_MUL,
	WO_SQR,
};


struct monkey {
	int * items;
	int nitems;
	enum worry_op wo;
	int wparam;
	int test_div;
	int test_true;
	int test_false;
	int inspections;
};


void
monkey_init(struct monkey * m)
{
	m->items = NULL;
	m->nitems = 0;
	m->wo = WO_NONE;
	m->wparam = 0;
	m->test_div = 0;
	m->test_true = 0;
	m->test_false = 0;
	m->inspections = 0;
}


void
monkey_dtor(struct monkey * m)
{
	free(m->items);
}


int
monkey_isvalid(struct monkey const * m, int max)
{
	return m->wo != WO_NONE
		&& m->test_div != 0
		&& m->test_true >= 0 && m->test_true < max
		&& m->test_false >= 0 && m->test_false < max;
}


int
monkey_additem(struct monkey * m, int worry)
{
	void * p;

	++m->nitems;
	p = realloc(m->items, m->nitems * sizeof(int));
	if (!p)
		return 0;
	m->items = p;
	m->items[m->nitems - 1] = worry;
	return 1;
}


void
monkey_dump(struct monkey const * m, int n)
{
	int * i;

	fprintf(stderr, "Monkey %d: %d/%d/%d/%d/%d/%d: ",
			n, m->wo, m->wparam, m->test_div, m->test_true, m->test_false, m->inspections);
	for (i = m->items; i < m->items + m->nitems; ++i) {
		fprintf(stderr, "%s%d", i == m->items ? "" : ", ", *i);
	}
	fprintf(stderr, "\n");
}


int
main()
{
	char buf[BUFSIZ];
	struct monkey * monkeys = NULL, * m = NULL;
	int nmonkeys = 0;
	int i, j;

	// Read monkey data
	while (fgets(buf, sizeof(buf), stdin)) {
		if (buf[0] == '\n') {
			// Ignore blank line
		}
		else if (strncmp(buf, "Monkey ", 7) == 0 && isdigit(buf[7])) {
			void * p;

			++nmonkeys;

			if ((i = atoi(buf + 7)) != nmonkeys - 1) {
				fprintf(stderr, "Bad monkey %d/%d!\n", i, nmonkeys);
				free(monkeys);
				return -1;
			}
			p = realloc(monkeys, nmonkeys * sizeof(struct monkey));
			if (!p) {
				fprintf(stderr, "realloc(%zd) fail\n", nmonkeys * sizeof(struct monkey));
				free(monkeys);
				return -1;
			}
			monkeys = p;
			m = monkeys + nmonkeys - 1;
			monkey_init(m);
		}
		else if (strncmp(buf, "  Starting items: ", 18) == 0 && isdigit(buf[18])) {
			char * cur, * next;
			int worry;

			cur = buf + 18;
			worry = strtol(cur, &next, 10);
			while (next != cur) {
				monkey_additem(m, worry);
				cur = next + 1;
				worry = strtol(cur, &next, 10);
			}
		}
		else if (strncmp(buf, "  Operation: new = old ", 23) == 0) {
			switch (buf[23]) {
			case '+': m->wo = WO_ADD; break;
			case '*': m->wo = WO_MUL; break;
			default:
				  fprintf(stderr, "Unexpected op %c\n", buf[23]);
				  free(monkeys);
				  return -1;
			}
			if (strncmp(buf + 25, "old", 3) == 0 && m->wo == WO_MUL) {
				m->wo = WO_SQR;
			}
			else {
				m->wparam = atoi(buf + 25);
			}
		}
		else if (strncmp(buf, "  Test: divisible by ", 21) == 0 && isdigit(buf[21])) {
			m->test_div = atoi(buf + 21);
		}
		else if (strncmp(buf, "    If true: throw to monkey ", 29) == 0 && isdigit(buf[29])) {
			m->test_true = atoi(buf + 29);
		}
		else if (strncmp(buf, "    If false: throw to monkey ", 30) == 0 && isdigit(buf[30])) {
			m->test_false = atoi(buf + 30);
		}
		else {
			fprintf(stderr, "Unexpected monkey: %s\n", buf);
			free(monkeys);
			return -1;
		}
	}

	// Check monkeys are valid
	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
#if 0
		monkey_dump(m, m - monkeys);
#endif
		if (!monkey_isvalid(m, nmonkeys)) {
			fprintf(stderr, "Bad monkey %d\n", (int) (m - monkeys));
			monkey_dump(m, m - monkeys);
			free(monkeys);
			return -1;
		}
	}

	// Perform monkey inspection rounds
	for (i = 0; i < 20; ++i) {
		for (m = monkeys; m < monkeys + nmonkeys; ++m) {
			int * item;

			for (item = m->items; item < m->items + m->nitems; ++item) {
				int catcher;

				switch (m->wo) {
				case WO_NONE: break; /* shouldn't happen */
				case WO_ADD: *item += m->wparam; break;
				case WO_MUL: *item *= m->wparam; break;
				case WO_SQR: *item *= *item; break;
				}
				*item /= 3;

				catcher = *item % m->test_div ? m->test_false : m->test_true;
				monkey_additem(monkeys + catcher, *item);

				++m->inspections;
			}
			m->nitems = 0;
		}

#if 0
		for (m = monkeys; m < monkeys + nmonkeys; ++m) {
			monkey_dump(m, m - monkeys);
		}
#endif
	}

	// Calculate monkey business
	i = j = 0;
	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
		if (m->inspections > i) {
			j = i;
			i = m->inspections;
		}
		else if (m->inspections > j) {
			j = m->inspections;
		}
	}
	printf("Monkey business: %d (%d * %d)\n", i * j, i, j);

	// Done.
	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
		monkey_dtor(m);
	}
	free(monkeys);

	return 0;
}