1761C.md (2474B)
1 Source: https://codeforces.com/problemset/problem/1761/C 2 3 C. Set Construction 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a binary matrix $b$ (all elements of the matrix are $0$ or $1$) of $n$ rows and $n$ columns. 22 23 You need to construct a $n$ sets $A_1, A_2, \ldots, A_n$, for which the following conditions are satisfied: 24 25 * Each set is nonempty and consists of distinct integers between $1$ and $n$ inclusive. 26 * All sets are distinct. 27 * For all pairs $(i,j)$ satisfying $1\leq i, j\leq n$, $b_{i,j}=1$ if and only if $A_i\subsetneq A_j$. In other words, $b_{i, j}$ is $1$ if $A_i$ is a proper subset of $A_j$ and $0$ otherwise. 28 29 Set $X$ is a proper subset of set $Y$, if $X$ is a nonempty subset of $Y$, and $X \neq Y$. 30 31 It's guaranteed that for all test cases in this problem, such $n$ sets exist. Note that it doesn't mean that such $n$ sets exist for all possible inputs. 32 33 If there are multiple solutions, you can output any of them. 34 35 Input 36 37 Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. The description of test cases follows. 38 39 The first line contains a single integer $n$ ($1\le n\le 100$). 40 41 The following $n$ lines contain a binary matrix $b$, the $j$-th character of $i$-th line denotes $b_{i,j}$. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$. 44 45 It's guaranteed that for all test cases in this problem, such $n$ sets exist. 46 47 Output 48 49 For each test case, output $n$ lines. 50 51 For the $i$-th line, first output $s_i$ $(1 \le s_i \le n)$ — the size of the set $A_i$. Then, output $s_i$ distinct integers from $1$ to $n$ — the elements of the set $A_i$. 52 53 If there are multiple solutions, you can output any of them. 54 55 It's guaranteed that for all test cases in this problem, such $n$ sets exist. 56 57 Example 58 59 Input 60 61 ``` 62 2 63 4 64 0001 65 1001 66 0001 67 0000 68 3 69 011 70 001 71 000 72 ``` 73 74 Output 75 76 ``` 77 3 1 2 3 78 2 1 3 79 2 2 4 80 4 1 2 3 4 81 1 1 82 2 1 2 83 3 1 2 3 84 ``` 85 86 Note 87 88 In the first test case, we have $A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$. Sets $A_1, A_2, A_3$ are proper subsets of $A_4$, and also set $A_2$ is a proper subset of $A_1$. No other set is a proper subset of any other set. 89 90 In the second test case, we have $A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$. $A_1$ is a proper subset of $A_2$ and $A_3$, and $A_2$ is a proper subset of $A_3$.