Computation - Task 6

Time limit1sMemory limit1024 MB

Summary

Write an instruction-set program for ten fixed tasks, including XOR, a*b mod m, and sorting 16 reals, using only the listed operators.

Level: Medium6 of 10
Topics: Implementation, Bit manipulation, Sorting
Solved: No attempts yet

Problem

You need to write a program that solves the task using the instructions below. Let $x_t$ denote the result of the $t$ -th instruction. The permitted instructions, the syntax, and the result $x_t$ are given below.

Name	Operator	Parameters	Effect
Input	`I`	N/A	Reads a real number from the terminal and sets $x_t$ to that number
Output	`O`	$i$	Prints $x_i$ to the terminal, and $x_t = x_i$
Addition	`+`	$i \quad j$	$x_t = x_i + x_j$
Adding constant	`C`	$i \quad c$	$x_t = x_i + c$
Negate	`-`	$i$	$x_t = -x_i$
Left shift	`<`	$i \quad k$	$x_t = x_i \cdot 2^k$
Right shift	`>`	$i \quad k$	$x_t = x_i \cdot 2^{-k}$
S	`S`	$i$	$x_t = s(x_i)$
Comparison	`P`	$i \quad j$	$x_t = -1$ if $x_i < x_j$ , $0$ if $x_i = x_j$ , $1$ if $x_i > x_j$
Max	`M`	$i \quad j$	$x_t = x_i$ if $x_i > x_j$ , otherwise $x_t = x_j$
Multiplication	`*`	$i \quad j$	$x_i = x_i \cdot x_j$

The function $s(x)$ is defined below, where $e = 2.718281828459045\ldots$ is the base of the natural logarithm.

$s(x) = \frac{1}{1 + e^{-x}}.$

The P, M, and * operators incur a penalty. See the "grading" section below for details.

Instructions run in order, one at a time. For each instruction, the parameters $i$ and $j$ must be smaller than the current instruction number $t$ . Operations have finite precision. Results are accurate only up to 90 digits after the decimal point, and the rest is rounded. The argument $c$ of the adding constant instruction has at most 90 digits in its decimal part. For the left and right shift instructions, $k$ must be a non-negative integer not exceeding 10000.

Tasks

Task 1: Given $a, b$ where $|a|, |b| \leq 10^9$ and $a, b$ have at most 9 digits in their decimal parts, compute $-2a-2b$ .
Task 2: Given $a$ where $|a| \leq 10^9$ and $a$ has at most 9 digits in its decimal part, compute $\frac{1}{1+e^{17a}}$ .
Task 3: Given $a$ where $|a| \leq 10^9$ and $a$ has at most 9 digits in its decimal part, compute $-1$ if $a < 0$ , $0$ if $a = 0$ , and $1$ if $a > 0$ .
Task 4: Given $a$ where $|a| \leq 10^9$ and $a$ has at most 9 digits in its decimal part, compute the absolute value $|a|$ .
Task 5: Given $a_1, \ldots, a_{32}$ where each $a_i \in \{0,1\}$ , treat $a_1a_2 \cdots a_{32}$ as a binary number where $a_1$ is the most significant bit and $a_{32}$ is the least significant bit. Compute its value in base 10.
Task 6: Given an integer $a$ where $0 \leq a < 2^{32}$ , output 32 integers giving $a$ in base 2. Print the most significant bit first and the least significant bit last. If $a$ has fewer than 32 bits, add leading 0s.
Task 7: Given integers $a, b$ where $0 \leq a, b < 2^{32}$ , compute the bitwise XOR of $a$ and $b$ .
Task 8: Given $a$ where $|a| \leq 10^9$ and $a$ has at most 9 digits in its decimal part, output $\frac{a}{10}$ .
Task 9: Given $a_1, \ldots, a_{16}$ where $|a_i| \leq 10^9$ and each $a_i$ has at most 9 digits in its decimal part, print 16 real numbers that are $a_1, \ldots, a_{16}$ sorted in ascending order.
Task 10: Given integers $a, b, m$ where $0 \leq a, b < 2^{32}$ and $1 \leq m < 2^{32}$ , compute the remainder when $a \times b$ is divided by $m$ , that is, $a \times b \bmod m$ .

Output

The $i$ -th line describes the $i$ -th instruction. First, output a letter for the operation. Then output zero or more integers for its parameters. Separate the operator and the parameters, and separate the parameters from each other, with a single space.

You can output at most $10^4$ lines.

Examples1

Example 1

Input

Expected output

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