18147번 - The Spectrum 다국어

Let X = (x₁, x₂, . . . , x_n) be an integer sequence whose elements are distinct. The spectrum of X, denoted by spec(X), is the multiset {|x_i−x_j| : 1 ≤ i < j ≤ n}. Notice that a multiset counts multiplicity but ignores order. For example, {1, 1, 2} and {2, 1, 1} are the same, but {1, 1, 2} and {1, 2} are different in multisets. For simplicity, we assume that sequence X is in the ascending order and x₁ = 0. For example, suppose X = (0, 1, 4, 5). Then spec(X) = {1, 1, 3, 4, 4, 5}. Given X, it is easy to compute spec(X). However, given spec(X), it is not an easy task to recover X from spec(X). In fact, it is possible that spec(X) = spec(Y ) for two different sequences X and Y . For example, spec(0, 7, 20) = {7, 13, 20} = spec(0, 13, 20). Your job is to recover all possible X’s such that spec(X) is equal to the specified spectrum in the input.

The first line in a test case gives you the number n, which is the size of the integer sequence X. The second line gives you the spectrum of X, which is a multiset and the numbers d₁, . . . , d_n(n−1)/2 are listed in nondescending order with a single space as the delimiter between two consecutive numbers.

First, output the total number of possible X’s (i.e. the number of solutions) in a line. Then dump all possible X’s in the lexicographic order (i.e. the dictionary order), one X per line. Let Y = (y₁, . . . , y_n) and Z = (z₁, . . . , z_n) be two such solutions. Then Y should precede Z if and only if there exists some index k where 1 ≤ k ≤ n such that y_k < z_k and y_j = z_j for all 1 ≤ j < k. For example, the sequence Y = (0, 7, 20) should precede Z = (0, 13, 20) in the lexicographic order because y₂ < z₂ (i.e. 7 < 13) and y₁ = z₁. For each X, print its elements in ascending order with a single space between two consecutive numbers.

• 2 ≤ n ≤ 62.
• 0 < d₁ ≤ d₂ ≤ · · · ≤ d_n(n−1)/2.
• Your output should satisfy: 0 ≤ x_i ≤ 999 for 1 ≤ i ≤ n and x₁ = 0.
• x_i < x_j for 1 ≤ i < j ≤ n.