33445번 - Majority 스페셜 저지다국어

문제

Little Cat learned Boolean circuits recently. Now he wants to construct a majority circuit.

A circuit over Boolean variables $x_1, \ldots, x_n$ is a directed acyclic graph where each node (logical gate) is either an input node labeled by a variable $x_i,ドル or an operation node labeled by a logical operation $\vee$ or $\wedge$. There are exactly $n$ input nodes, one for each of the input variables $x_1, \ldots, x_n$. Additionally, a single node is chosen as the output of the circuit.

Each node computes an output: the input nodes (labeled by a variable) output exactly the variable written on them, and nodes labeled by $\vee$ (respectively, $\wedge$) output the logical OR (respectively, AND) of all incoming nodes. Note that logical NOT nodes are forbidden. See the example and notes for better understanding.

The in-degree of an input node is 0ドル$. The in-degree of an operation node is at least 1ドル,ドル and can be arbitrarily large. The out-degrees are arbitrary (possibly 0ドル$).

For convenience, there are two special constant nodes $T$ (true) and $F$ (false), which always output 1ドル$ and 0ドル,ドル respectively.

The majority circuit $\mathit{Maj}_n$ has $n$ inputs $x_1, \ldots, x_n,ドル and it outputs 1ドル$ if at least half of inputs are 1ドル,ドル and outputs 0ドル$ otherwise. Formally, $\mathit{Maj}_n(x_1, \ldots, x_n) = \left[2 \sum_{i = 1}^n x_i \ge n\right]$.

Define the depth of a circuit as the length of the longest (directed) path in the circuit, that is, the number of edges of the longest path.

Could you help Little Cat to construct a majority circuit over $n$ inputs with depth at most 14ドル$?

입력

The input contains one line with an integer $n$ (2ドル \le n \le 64$) indicating the number of input nodes.

출력

The first line must contain an integer $m$ (1ドル \le m \le 5 \cdot 10^4$) representing the number of nodes labeled by $\vee$ or $\wedge,ドル so there are $n + m + 2$ nodes in the circuit in total. The input nodes $x_1, \ldots, x_n$ are numbered by 1,ドル \ldots, n$. The constant true node $T$ is numbered by $-1,ドル and the constant false node $F$ is numbered by $-2$.

A total of $m$ lines must follow. The $i$-th line must describe node $(n + i)$ in one of the following formats.

• "OR $k_i$ $a_1$ $a_2$ $\ldots$ $a_{k_i}$" (without quotes): node $(n + i)$ computes the logical OR of nodes $a_j$ where $-2 \le a_j < n + i$ and $a_j \neq 0$ for all 1ドル \le j \le k_i$.
• "AND $k_i$ $a_1$ $a_2$ $\ldots$ $a_{k_i}$" (without quotes): node $(n + i)$ computes the logical AND of nodes $a_j$ where $-2 \le a_j < n + i$ and $a_j \neq 0$ for all 1ドル \le j \le k_i$.

It is fine if $a_u = a_v$ for some $u \neq v$. You must guarantee that $\sum_{i = 1}^{m} k_i \le 2 \cdot 10^5$ and that the depth of the circuit does not exceed 14ドル$.

The output of the circuit is chosen as the output of node $n + m$.

To check the circuit you construct, Little Cat will test your circuit for 1500ドル$ rounds. In each round, Little Cat will generate an arbitrary input $x_1, \ldots, x_n$ (he won't say how exactly) and test your circuit with that input. You pass this round if your circuit outputs the majority of the input $x_1, \ldots, x_n$ correctly. You need to pass all the 1500ドル$ rounds.

제한

노트

The sample output prints a depth-2 circuit computing $\mathit{Maj}_4$. The circuit $\mathit{Maj}_4 (x_1,x_2,x_3,x_4)$ outputs 1ドル$ if and only if at least two input nodes are 1ドル$. Thus you can compute the logical AND of every pair of input nodes and output the logical OR of these ANDs.

Here are some notes on the circuit nodes:

• Nodes 1ドル,ドル 2ドル,ドル 3ドル,ドル and 4ドル$ are input nodes.
• Nodes 5ドル,ドル 6ドル,ドル 7ドル,ドル 8ドル,ドル 9ドル,ドル and 10ドル$ compute the logical AND of some input nodes.
• Nodes 11ドル$ and 12ドル$ are redundant.
• Node 13ドル$ is the output node.
• The constant nodes $T$ and $F$ are not drawn in the figure.

Here, the existence of redundant nodes will not affect the validity of the circuit as long as the constraints (1ドル \le m \le 5 \cdot 10^4,ドル $\sum k_i \le 2 \cdot 10^5,ドル $\mathit{depth} \le 14$) are satisfied.

During the test, the following shows a possible scenario:

The input nodes are set to $x_1 = 1,ドル $x_2 = 0,ドル $x_3 = 0,ドル $x_4 = 1$.

Therefore, the outputs of nodes $x_5, \ldots, x_{13}$ are:

• $x_5 = x_1 \text{ AND } x_2 = 1 \text{ AND } 0 = 0$
• $x_6 = x_1 \text{ AND } x_3 = 1 \text{ AND } 0 = 0$
• $x_7 = x_1 \text{ AND } x_4 = 1 \text{ AND } 1 = 1$
• $x_8 = x_2 \text{ AND } x_3 = 0 \text{ AND } 0 = 0$
• $x_9 = x_2 \text{ AND } x_4 = 0 \text{ AND } 1 = 0$
• $x_{10} = x_3 \text{ AND } x_4 = 0 \text{ AND } 1 = 0$
• $x_{11} = x_5 \text{ AND } x_5 \text{ AND } x_6 = 0 \text{ AND } 0 \text{ AND } 0 = 0$
• $x_{12} = x_7 = 1$
• $x_{13} = x_5 \text{ OR } x_6 \text{ OR } x_7 \text{ OR } x_8 \text{ OR } x_9 \text{ OR } x_{10} = 0 \text{ OR } 0 \text{ OR } 1 \text{ OR } 0 \text{ OR } 0 \text{ OR } 0 = 1$.

The output of the circuit is $x_{13} = 1,ドル which is the majority of $\{1, 0, 0, 1\}$.