PROBLEM STATEMENT
Fox Ciel is creating a new binary operation.
The operation will be denoted $ and it will be defined on the finite set S = {0, 1, 2, ..., n-1}.
I.e., for each ordered pair (i, j) of elements of S the operation (i $ j) will return some element
of S.
For example, we can have S = {0, 1}, and we can define that (0 $ 0) = 0, (0 $ 1) = 1, (1 $ 0) = 0,
and (1 $ 1) = 0.
Note that Ciel's operation is not necessarily symmetric. In other words, it is possible that for
some i and j the operations (i $ j) and (j $ i) return two different values.
A subset T of S is called good if it has the following property: for any two elements i and j in
T, (i $ j) is also in T.
You are given an int x.
Construct a binary operation $ with the following properties:
The number n (i.e., the size of the set S) must be between 1 and 20, inclusive.
The number of good subsets of the set S must be exactly x.
Return a vector containing the "multiplication table" of your operation $.
More precisely, the return value should consist of n*n elements.
For each i and j from the set S, element (i*n+j) of the return value should be the value (i $ j).
If there are multiple solutions, you may return any of them.
You may assume that there is always at least one valid solution.
DEFINITION
Class:MultiplicationTable3
Method:construct
Parameters:int
Returns:vector
Method signature:vector construct(int x)
CONSTRAINTS
-x will be between 1 and 1,000, inclusive.
EXAMPLES
0)
2
Returns: {1, 1, 1, 1 }
We have chosen n = 2.
Regardless of the inputs, our binary operation $ always returns 1.
For this operation we have exactly x = 2 good subsets of S: the subset {1} and the subset {0,1}.
1)
3
Returns: {0, 1, 0, 1 }
The length of the return value is 4, hence it describes an operation with n = 2.
This particular return value describes the following operation:
0 $ 0 = 0
0 $ 1 = 1
1 $ 0 = 0
1 $ 1 = 1
This operation has exactly 3 good subsets: {0}, {1}, and {0,1}.
2)
6
Returns: {0, 1, 1, 0, 1, 2, 0, 1, 2 }
3)
31
Returns: {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 }
All non-empty subsets of S are good.
4)
1
Returns: {0 }
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.