[NOI2016] 旷野大计算

ID: 699

远端评测题

1000ms

512MiB

尝试: 0

已通过: 0

难度: 9

上传者:

root

标签>

数学

2016

NOI 系列

提交答案

Special Judge

Description

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$
Right 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`		$x_t=\begin{cases}x_i &x_i>x_j\\x_j &x_i \leq x_j\end{cases}$
Multiplication node	`*`		$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$			$\begin{cases}-1 & a \lt 0 \\ 0 & a = 0 \\ 1 & a \gt 0\end{cases}$
$4$			$\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.

Input Format

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.

Output Format

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$ .

I
+ 1 1
- 2
I
+ 4 4
- 5
+ 3 6
- 7
- 8
O 9

Hint

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

#P1737. [NOI2016] 旷野大计算

Description

Input Format

Output Format

Hint

还没有账户？

登录