#include #include #include #include using namespace std; enum Material { Ore, Clay, Obs, Geode, MatAmt }; const Material Mats[] = {Ore, Clay, Obs, Geode}; // Material Matrix. // heh typedef int MatMat[MatAmt][MatAmt]; struct State { int amts[MatAmt] = {0}; int robots[MatAmt] = {1, 0, 0, 0}; int rem = 0; State idle(int t) const { State s = *this; for (auto m : Mats) { s.amts[m] += s.robots[m] * t; } s.rem -= t; return s; } int timeUntil(const int reqs[MatAmt]) const { int worst = 0; for (auto m : Mats) { if (amts[m] < reqs[m]) { if (robots[m] == 0) return -1; worst = max(worst, (reqs[m] - amts[m] + robots[m] - 1) / robots[m]); } if (rem < worst) return -1; } return worst + 1; // +1 to account for robot build } optional buyRobot(MatMat const& costs, Material robot) const { int t = timeUntil(costs[robot]); if (t < 0 || rem <= t) return {}; State s = idle(t); for (auto m : Mats) { s.amts[m] -= costs[robot][m]; } s.robots[robot]++; return s; } int best(MatMat const& costs) const { if (rem <= 0) return 0; int r = 0; bool wanted[MatAmt] = {0}; wanted[Geode] = true; for (auto m : {Geode, Obs, Clay, Ore}) { if (!wanted[m]) continue; for (auto m2 : Mats) { if (robots[m2] < costs[m][m2]) { wanted[m2] = true; } } auto s = buyRobot(costs, m); if (s) { r = max(r, s->best(costs)); } } State s = idle(rem); r = max(r, s.amts[Geode]); return r; } }; int main() { const char *fmt = "Blueprint %d: " "Each ore robot costs %d ore. " "Each clay robot costs %d ore. " "Each obsidian robot costs %d ore and %d clay. " "Each geode robot costs %d ore and %d obsidian. "; int id; MatMat costs = {0}; int total = 0; while (scanf(fmt, &id, &costs[Ore][Ore], &costs[Clay][Ore], &costs[Obs][Ore], &costs[Obs][Clay], &costs[Geode][Ore], &costs[Geode][Obs]) == 7) { total += id * State{.rem=24}.best(costs); } printf("%d\n", total); }