시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 24 | 11 | 6 | 46.154% |
A pleasant headache that parents have every year is preparing Christmas gifts for their children. Because each child envies each other having seen what others received, the parents have to prepare gifts so that no child should envy any other child.
Before a husband and wife go for Christmas shopping, they announce to their children a fixed set of gift candidates and declare that each child will receive a subset of the candidates. The children then respond to the parents with conditions for them to be happy. Each child’s condition is relatively defined in terms of the gifts that other siblings would have. The goal of the parents is to satisfy all their children’s conditions with the smallest such gift set for each child.
Each child’s condition is always expressed as a conjunction:
where each αi is either
For example, for three children {X, Y, Z} and for three candidates {a, b, c} for gifts, let the condition for each child be:
Then the smallest gifts for each child that satisfy his/her condition are {a, b} for X, {b} for Y, and {a, b} for Z.
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Gift candidates are numbered from 1 to n (1 ≤ n ≤ 1000 ). Children are numbered from 1 to m(1 ≤ m ≤ 100) .
The input is a sequence of non-empty lines:
Each child’s condition is expressed as follows:
-1 2 1 2represents a set {1, 2} of gifts.
-2 2represents sibling 2’s gifts.
-3 -2 3 -1 2 2 3
-3 -2 2 -2 3represents the common-things-of sibling 2’s and 3’s gifts.
-4 -2 1 -1 1 3represents sibling 1’s gifts except-for {3}.
The output is the sequence of solutions for the given test cases. The solutions are printed in the order of the test cases. Each solution is the sequence of lines, one line per child, in the increasing order of children’s identification numbers. Each line starts with the child’s identification number followed by his/her gift identification numbers in the increasing order. For an empty gift, only the child number is printed.
3 2 2 1 1 -1 1 1 2 1 -4 -2 1 -1 1 1 1 1 1 1 -3 -1 1 1 -1 1 1 3 3 1 2 -1 2 1 2 -3 -2 2 -2 3 2 1 -3 -2 3 -1 2 2 3 3 2 -1 1 1 -4 -2 1 -1 1 3
1 1 2 1 1 1 1 2 2 2 3 1 2
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Taejon 2002 D번