possible values that are returned on the measurement (in number of coins). You are interested only if gcd=1 because (2,2,2) is not distinguishable from (1, 1,1). Note that they are actually from -k to k

The set we built is equal to itself multiplied by -1, so the sum in every coordinate is zero, which is necessary and sufficient.

In $$$i$$$-th weighting, for each sequence we can put $$$p_i$$$ coins on the left side of scale if $$$p_i > 0$$$ and $$$-p_i$$$ coins on the right side if $$$p_i < 0$$$.

Now consider sequence of results for weightings as $$$a_1, a_2, \ldots, a_m$$$. For conveniece we can assume $$$a_i \ge 0$$$. Let's denote $$$x$$$ as a difference of weight between one false coin and one normal coin.

If $$$a_1 = a_2 = \dots = a_m = 0$$$ then we know that only sequence $$$p_1 = p_2 = \ldots = p_m = 0$$$ satisfy requirements.

Otherwise there exists $$$a_i > 0$$$. Let's assume we know that $$$a_i = t \cdot x$$$ for some integer $$$t$$$ between $$$1$$$ and $$$k$$$. Then we can uniquely determine answer. But because we picked only sequences with $$$GCD$$$ equal to $$$1$$$ then we can iterate over all possible $$$t$$$ and pick the smallest one for which all $$$\frac{a_i}{x}$$$ are integers — this is answer to our problem.

Buiding a trie is a very smart move. I think in this case, we should try our best to prevent using STL stuffs.

I also made my program quit when the answer reaches N and it got stuck in Test 24.