P16642 [GKS 2018 #B] Sherlock and the Bit Strings

Sherlock and Watson are playing a game involving bit strings, i.e., strings consisting only of the digits $0$ and $1$. Watson has challenged Sherlock to generate a bit string $S$ of $N$ characters $S_1$, $S_2$, ..., $S_N$. The string must obey each of $K$ different constraints; each of these constraints is specified via three integers $A_i$, $B_i$, and $C_i$. The number of $1$s in the substring $S_{A_i}, S_{A_i+1}, \dots, S_{B_i}$ must be equal to $C_i$. Watson chooses the constraints in a way that guarantees that there is at least one string of the right length that obeys all of the constraints. However, since there could be multiple such strings, Watson wants Sherlock to choose the string from this set that is ${P}$-th in lexicographic order, with ${P}$ counted starting from $1$.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with one line containing three integers $N$, $K$, and $P$, as described above. Then, there are $K$ more lines; the $i$-th of these contains three integers $A_i$, $B_i$ and $C_i$, representing the parameters of the $i$-th constraint, as described above.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the ${P}$th lexicographically smallest bit string among all possible strings following the ${K}$ specified constraints.

In Sample Case #1, the bit strings that obey the only constraint in lexicographically increasing order are $[010, 011, 110, 111]$. In Sample Case #2, the bit strings that obey the only constraint in lexicographically increasing order are $[000, 001, 100, 101]$. ### Limits $1 \le T \le 100$. $1 \le N \le 100$. $1 \le K \le 100$. $1 \le P \le \min(10^{18}, \text{the number of bit strings that obey all of the constraints})$. $1 \le A_i \le B_i \le N$ for all $1 \le i \le K$. $0 \le C_i \le N$, for all $1 \le i \le K$. $(A_i, B_i) \neq (A_j, B_j)$, for all $1 \le i < j \le K$. **Small dataset (Test set 1 - Visible)** $A_i = B_i$ for all $1 \le i \le K$. **Large dataset (Test set 2 - hidden)** $B_i - A_i \le 15$ for all $1 \le i \le K$.