Hadron Collider (Editorial)

The key thing to notice is how small this problem actually is: at most 4 particle types, and never more than 2 particles of any type to begin with. Particles can only be destroyed, never created, so the count of each type only goes down over time, and it starts at 1 or 2 — meaning each type has at most three possible values (0, 1, or 2) at any point. That puts a hard cap of 3^4 = 81 on the number of distinct states the experiment can ever be in. That's small enough that we don't need any clever counting or physics reasoning: we can just simulate every possible sequence of collisions and see where it leads.

Picture every possible particle-count vector as a node in a graph, and every possible collision as an edge to another node. From a state $s$, for every pair of types $i,j$ (including i = j), if there's at least one particle of each type present (or at least two of the same type when i = j), and the matrix says a type-$i$ particle destroys a type-$j$ particle on collision, then a transition exists: subtract one from s_j. That may lead to a state we haven't seen yet, in which case we add it to the graph and keep exploring from there.

We keep this up — starting from the initial counts, following every collision that could possibly happen next — until we reach a state where no collision applies anymore. Those states are the actual answers: the final, stable configurations of the experiment. Since we explore every direction, not just one, we naturally find every possible outcome the experiment could end in, not just some of them.

A breadth-first search over this small state graph does exactly that: keep a set of states already seen, a queue of states still to process, and for each one popped from the queue, try every collision. If nothing fires, record it as a terminal state. Once the queue is empty, print all the terminal states found (sorted, so the output is in a stable order), with the usual TEST n: header.

That's the whole trick — realize the state space is tiny, then let brute-force graph exploration do the rest.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int test = 1;
    while (cin >> n && n != 0) {
        vector<int> start(n);
        for (auto &x : start) cin >> x;
        vector<vector<int>> mat(n, vector<int>(n));
        for (auto &row : mat)
            for (auto &x : row) cin >> x;

        set<vector<int>> visited, terminal;
        queue<vector<int>> todo;

        visited.insert(start);
        todo.push(start);

        while (!todo.empty()) {
            vector<int> s = todo.front(); todo.pop();
            bool reacted = false;

            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++) {
                    bool canCollide = (i != j) ? (s[i] > 0 && s[j] > 0) : (s[i] >= 2);
                    if (canCollide && mat[i][j] != 0) {
                        vector<int> next = s;
                        next[j]--;
                        reacted = true;
                        if (visited.insert(next).second)
                            todo.push(next);
                    }
                }

            if (!reacted) terminal.insert(s);
        }

        cout << "TEST " << test++ << ":\n";
        for (auto &s : terminal) {
            for (int i = 0; i < n; i++)
                cout << s[i] << " \n"[i + 1 == n];
        }
    }
}