P1737 [NOI2016] Grand Computation in the Wilderness

Tip: If you submit by “submit code,” the judge will give your program a single number (1, 2, 3, ..., 10) indicating the test point ID during evaluation. Please print the answer corresponding to that test point directly in your program.

With the development of human computer technology, computers keep getting more powerful, which makes the Flea King very envious. One day, the Flea King issued a decree: vigorously develop the Flea Kingdom’s computer industry! However, the Flea Kingdom has not undergone an industrial revolution and cannot manufacture the components needed for electronic computers. But the Flea King came up with a brilliant idea: treat each flea as a computing node, and each flea only performs a specific small task. The Flea King led $n$ fleas to a wilderness, arranged them as computing nodes, and numbered them from $1$ to $n$. Each computing node takes the results of some (possibly $0$) other computing nodes as input and computes an output. In addition, the Flea King has a giant terminal that can input and output data. This terminal and all the computing nodes together form a computer. Let the output of the $t$-th computing node be $x_t$. The operation of this node can be one of the following types: ::cute-table{tuack} | Name | Operator (Type) | Operands | Result | |-|-|-|-| | Input node | `I` | None | Read a real number from the terminal as $x_t$ | | Output node | `O` | $i$ | $x_t = x_i$, and output $x_t$ to the terminal | | Addition node | `+` | $i, j$ | $x_t = x_i + x_j$ | | Offset node | `C` | $i, c$ | $x_t = x_i + c$ | | Negation node | `-` | $i$ | $x_t = -x_i$ | | Left shift node | `` | $i, k$ | $x_t = x_i \cdot 2^{-k}$ | | S-type node | `S` | $i$ | $x_t = s(x_i)$ | | Comparison node | `P` | $i, j$ | $x_t=\begin{cases}-1 &x_ix_j\\\end{cases}$ | | Max node | `M` | $i, j$ | $x_t=\begin{cases}x_i &x_i>x_j\\x_j &x_i \leq x_j\end{cases}$ | | Multiplication node | `*` | $i, j$ | $x_t = x_i \cdot x_j$ | Here, $s(x)$ is defined as follows ($e$ is the base of the natural logarithm, approximately $2.718281828459045\ldots$): $$s\left ( x \right )=\frac{1}{1+e^{-x}}$$ The graph of $s(x)$ is shown below:  In the table above, the operand indices $i, j$ must both be less than the current node index $t$. Thus, when the Flea King gives the order, the fleas can obtain inputs and compute outputs in order from small index to large. Each flea’s computational precision is limited: they can only be accurate to $90$ digits after the decimal point, and any excess is rounded. Similarly, the fractional part of the operand $c$ in the table above cannot exceed $90$ digits. Moreover, in left shift and right shift nodes, the operand $k$ must be a non-negative integer and cannot exceed $10^4$. After arranging the fleas, the ambitious Flea King decided to test the computational capability of this flea-based computer. The Grasshopper Minister (guoguo, pinyin) presented 10 computational tasks to the Flea King. Each task requires reading input from the terminal, performing intermediate computations, and then outputting the result using an output node. The specific tasks are as follows: ::cute-table{tuack} | ID | Input | Input constraints | Output | |-|-|-|-| | $1$ | $a, b$ | $\lvert a \rvert, \lvert b \rvert \le 10^9$, fractional part no more than $9$ digits | $-2a - 2b$ | | $2$ | $a$ | $\lvert a \rvert \le 10^9$, fractional part no more than $9$ digits | $\dfrac{1}{1+e^{17a}}$ | | $3$ | $a$ | $\lvert a \rvert \le 10^9$, fractional part no more than $9$ digits | $\begin{cases}-1 & a \lt 0 \\ 0 & a = 0 \\ 1 & a \gt 0\end{cases}$ | | $4$ | $a$ | $\lvert a \rvert \le 10^9$, fractional part no more than $9$ digits | $\lvert a \rvert$, i.e., the absolute value of $a$ | | $5$ | $a_1, \dots, a_{32}$ | $a_1, \dots, a_{32} \in \{0, 1\}$ | Read $a_1, \dots, a_{32}$ from left to right as a binary integer, with most significant bit on the left and least significant bit on the right, and output its value | | $6$ | $a$ | $0 \le a \lt 2^{32}$, $a$ is an integer | Output $32$ integers: the binary representation of $a$ from most significant bit to least significant bit (pad with leading zeros to length $32$ if necessary) | | $7$ | $a, b$ | $0 \le a, b \lt 2^{32}$, $a, b$ are integers | The bitwise XOR of $a$ and $b$ | | $8$ | $a$ | $\lvert a \rvert \le 10^9$, fractional part no more than $9$ digits | $\dfrac{a}{10}$ | | $9$ | $a_1, \dots, a_{16}$ | $\lvert a_1 \rvert, \dots, \lvert a_{16} \rvert \le 10^9$, fractional part no more than $9$ digits | Output $16$ real numbers: the result of sorting $a_1, \dots, a_{16}$ in nondecreasing order | | $10$ | $a, b, m$ | $0 \le a, b \lt 2^{32}$, $1 \le m \lt 2^{32}$, $a, b, m$ are integers | The remainder of $a \cdot b$ divided by $m$ | The Flea King found that he did not have enough ability to design such a computer. So he turned to you, a contestant at NOI. Please design the type and operands of each computing node in order to complete the 10 tasks given by the Grasshopper Minister, while using as few computing nodes as possible.

All input testdata `nodes1.in` $\sim$ `nodes10.in` correspond to the 10 computational tasks respectively. Each input file contains a single integer indicating the ID of the computational task to solve. Since they are only for internal judge use, Luogu does not provide downloads for the testdata of this problem. Generate them yourself if needed.

The output files are `nodes1.out` $\sim$ `nodes10.out`, corresponding to the respective input files. For each input file, output several lines; the $i$-th line describes the $i$-th computing node. To describe each computing node, first output one character indicating the node type, followed by its built-in parameters in order. Use a single space between the character and numbers, and between numbers. The number of output lines must not exceed $10^4$.

The sample output is one possible construction for the first task. It uses $10$ computing nodes and earns $3$ points. We provide ten scoring files `nodes1.ans` $\sim$ `nodes10.ans`, corresponding to each computational task. Each scoring file contains $10$ lines. The $i$-th line contains one scoring parameter $w_i$, whose meaning is given below. Each test point is scored independently, with $10$ points per test point. If your output format is invalid or parameters do not meet the problem’s requirements, you get $0$ points. Otherwise, the judge determines correctness as follows: - The judge will generate several groups of inputs and feed them into your constructed computer. - If for any input group, during computation on your constructed computer, the absolute value of some node’s result exceeds $10^{1000}$, you get $0$ points. - If any value in your output differs from the expected output by more than $10^{-9}$, your output is considered incorrect and you get $0$ points. - Otherwise, we consider your computer able to complete the given task, and your score is determined as follows. For each test point, we set $10$ scoring parameters $w_1, w_2, w_3, \ldots, w_9, w_{10}$. Suppose you used $n$ computing nodes. Your score is given by the table below: ::cute-table{tuack} | Score | Condition | Score | Condition | | :----------: | :----------: | :----------: | :----------: | | 10 | $n \le w_{10}$ | 5 | $n \le w_5$ | | 9 | $n \le w_9$ | 4 | $n \le w_4$ | | 8 | $n \le w_8$ | 3 | $n \le w_3$ | | 7 | $n \le w_7$ | 2 | $n \le w_2$ | | 6 | $n \le w_6$ | 1 | $n \le w_1$ | If none of the conditions in the table are met, you get $0$ points. If multiple conditions are met, take the highest score. In addition, the cost of using the Comparison node, Max node, and Multiplication node is extremely expensive. Therefore, for each type among these three that you use, $4$ points will be deducted from your score on that test point. Note that the deduction is by the number of node types used, not by usage count. For example, using the Comparison node multiple times only deducts $4$ points. If you used both the Comparison node and the Multiplication node, even if each is used once, $8$ points will be deducted. A test point’s score will be deducted to at most $0$; even if the available score is insufficient, the score will not go negative. Translated by ChatGPT 5