P3005 [USACO10DEC] The Trough Game S

Farmer John and Bessie are playing games again. This one has to do with troughs of water. Farmer John has hidden N (1 1 trough is filled. From question 1, we know trough 1 is filled. From question 3, we then know trough 4 is empty. From question 4, we then know that trough 3 is filled. From question 2, we then know that trough 2 is empty. Farmer John and Bessie are playing a game. Farmer John has prepared $n$ troughs ($1 \le n \le 20$), and some of them contain food. To figure out which troughs contain food, Bessie asks $m$ questions of the form “How many of the troughs numbered $x_1 \cdots x_k$ are filled?” ($1 \le m \le 100$, $1 \le k \le n$). Please determine which troughs contain food.

- Line 1: Two space-separated integers: N and M. - Lines 2..M+1: A subset of troughs, specified as a sequence of contiguous N 0's and 1's, followed by a single integer that is the number of troughs in the specified subset that are filled. The first line contains two integers $n, m$, denoting the number of troughs and the number of questions, respectively. Each of the next $m$ lines contains a $01$ string of length $n$ and an integer $t$, where a $1$ in the $01$ string indicates the trough at that position is included in the query, and $t$ is the number of included troughs that are filled.

- Line 1: A single line with: - The string 'IMPOSSIBLE' if there is no possible set of filled troughs compatible with Farmer John's answers. - The string 'NOT UNIQUE' if Bessie cannot determine from the given data exactly what troughs are filled. - Otherwise, a sequence of contiguous N 0's and 1's specifying which troughs are filled. If there is no solution, print `IMPOSSIBLE`. If there is more than one solution, print `NOT UNIQUE`. If there is a unique solution, print a $01$ string in which a $1$ indicates the trough at that position contains food.

Sample explanation: The four sequences correspond to the following dialogue: 1. Q: How many of the first troughs contain food? — A: $1$. 2. Q: How many of the second and third troughs contain food? — A: $1$. 3. Q: How many of the first and fourth troughs contain food? — A: $1$. 4. Q: How many of the third and fourth troughs contain food? — A: $1$. From the first question, we can tell the first trough contains food. From the third question, we can tell the fourth trough does not contain food. From the fourth question, we can tell the third trough contains food. From the second question, we can tell the second trough does not contain food. Translated by ChatGPT 5