NOI '16 P6 - Computation - Olympiads Online Judge

NOI '16 P6 - Computation

View as PDF

Submit solution

All submissions

Best submissions

Points: 30 (partial)

Time limit: 30.0s

Memory limit: 1G

Problem types

Attention: In NOI 2016, this problem is an output-only problem. Since DMOJ does not directly support output-only problems, you should treat this problem as a traditional problem where the input is the task to solve. You should produce the output by a program (hardcoding is fine). The time limit is extremely generous, so please be reasonable when attempting the problem at DMOJ.

Given a task, you should write a program that solves the task using the instructions below. Let $x_t$ $x_{t}$ denote the result of the $t$ $t$ -th instruction. The permitted instructions, the syntax, and the result $x_t$ $x_{t}$ are given below:

Name	Operator	Parameters	Effects
Input	`I`	N/A	Read a real number from the terminal and make the number $x_t$ $x_{t}$
Output	`O`	$i$ $i$	Print $x_i$ $x_{i}$ to the terminal, and $x_t = x_i$ $x_{t} = x_{i}$
Addition	`+`	$i \quad j$ $i j$	$x_t = x_i+x_j$ $x_{t} = x_{i} + x_{j}$
Adding constant	`C`	$i \quad c$ $i c$	$x_t = x_i+c$ $x_{t} = x_{i} + c$
Negate	`-`	$i$ $i$	$x_t = -x_i$ $x_{t} = - x_{i}$
Left shift	`<`	$i \quad k$ $i k$	$x_t = x_i \cdot 2^k$ $x_{t} = x_{i} \cdot 2^{k}$
Right shift	`>`	$i \quad k$ $i k$	$x_t = x_i \cdot 2^{-k}$ $x_{t} = x_{i} \cdot 2^{- k}$
S	`S`	$i$ $i$	$x_t = s(x_i)$ $x_{t} = s (x_{i})$
Comparison	`P`	$i \quad j$ $i j$	$x_t = \begin{cases}-1 & x_i < x_j \\ 0 & x_i = x_j \\ 1 & x_i > x_j\end{cases}$ $x_{t} = {\begin{cases} - 1 & x_{i} < x_{j} \\ 0 & x_{i} = x_{j} \\ 1 & x_{i} > x_{j} \end{cases}$
Max	`M`	$i \quad j$ $i j$	$x_t = \begin{cases}x_i & x_i > x_j \\ x_j & x_i \le x_j\end{cases}$ $x_{t} = {\begin{cases} x_{i} & x_{i} > x_{j} \\ x_{j} & x_{i} \leq x_{j} \end{cases}$
Multiplication	`*`	$i \quad j$ $i j$	$x_i = x_i \cdot x_j$ $x_{i} = x_{i} \cdot x_{j}$

Here, the definition of $s(x)$ $s (x)$ is given below where $e = 2.718281828459045\dots$ $e = 2.718281828459045 \dots$ is the base of natural logarithm:

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

Notice there is a penalty for using the P, M, and * operators. See details below in the "grading" section.

For each instruction, the parameters $i$ $i$ and $j$ $j$ must be smaller than the current instruction number $t$ $t$ . The instructions are executed in the order, one by one.

The operations have finite precision: in particular, the results are only accurate up to 90 digits after the decimal point and the rest will be rounded. Similarly, the argument $c$ $c$ to the adding constant instruction can have at most 90 digits in its decimal part.

For left shift and right shift instructions, $k$ $k$ must be a non-negative integer not exceeding $10\,000$ $10 000$ .

The ten tasks are given below:

Task 1: Given $a,b$ $a, b$ where $|a|, |b| \le 10^9$ $| a |, | b | \leq 10^{9}$ and $a,b$ $a, b$ have at most 9 digits in their decimal parts, compute $-2a-2b$ $- 2 a - 2 b$ .
Task 2: Given $a$ $a$ where $|a| \le 10^9$ $| a | \leq 10^{9}$ and $a$ $a$ has at most 9 digits in its decimal part, compute $\frac{1}{1+e^{17a}}$ $\frac{1}{1 + e^{17 a}}$ .
Task 3: Given $a$ $a$ where $|a| \le 10^9$ $| a | \leq 10^{9}$ and $a$ $a$ has at most 9 digits in its decimal part, compute $\begin{cases}-1 & a < 0 \\ 0 & a = 0 \\ 1 & a > 0\end{cases}$ ${\begin{cases} - 1 & a < 0 \\ 0 & a = 0 \\ 1 & a > 0 \end{cases}$ .
Task 4: Given $a$ $a$ where $|a| \le 10^9$ $| a | \leq 10^{9}$ and $a$ $a$ has at most 9 digits in its decimal part, compute the absolute value of $a$ $a$ , $|a|$ $| a |$ .
Task 5: Given $a_1, \dots, a_{32}$ $a_{1}, \dots, a_{32}$ where $a_1, \dots, a_{32} \in \{0,1\}$ $a_{1}, \dots, a_{32} \in {0, 1}$ , treat $a_1 a_2 \dots a_{32}$ $a_{1} a_{2} \dots a_{32}$ as a binary number where $a_1$ $a_{1}$ is the most significant bit and $a_{32}$ $a_{32}$ is the least significant bit, compute the corresponding value (in base 10).
Task 6: Given integer $a$ $a$ where $0 \le a < 2^{32}$ $0 \leq a < 2^{32}$ , output 32 integers denoting $a$ $a$ in base 2 representation. The most significant bit should be printed first and the least significant bit should be printed last. If $a$ $a$ has less than 32 bits in its binary representation, add leading 0s.
Task 7: Given integers $a,b$ $a, b$ where $0 \le a,b < 2^{32}$ $0 \leq a, b < 2^{32}$ , compute the bitwise XOR of $a$ $a$ and $b$ $b$ .
Task 8: Given $a$ $a$ where $|a| \le 10^9$ $| a | \leq 10^{9}$ and $a$ $a$ has at most 9 digits in its decimal part, output $\frac{a}{10}$ $\frac{a}{10}$ .
Task 9: Given $a_1, \dots, a_{16}$ $a_{1}, \dots, a_{16}$ where $|a_i| \le 10^9$ $| a_{i} | \leq 10^{9}$ and $a_i$ $a_{i}$ has at most 9 digits in its decimal part, print 16 real numbers representing the result of sorting $a_1, \dots, a_{16}$ $a_{1}, \dots, a_{16}$ in ascending order.
Task 10: Given integers $a,b,m$ $a, b, m$ where $0 \le a,b < 2^{32}$ $0 \leq a, b < 2^{32}$ , $1 \le m < 2^{32}$ $1 \leq m < 2^{32}$ , compute the remainder after dividing $a \times b$ $a \times b$ by $m$ $m$ (i.e. compute $a \times b \bmod m$ $a \times b mod m$ ).

Input Specification

The input consists of an integer denoting the task to solve.

Output Specification

For each output, you need to output several lines. The $i$ $i$ -th line describes the $i$ $i$ -th instruction: first, you should output a letter denoting the operation. Then output several (or zero) integers denoting the parameters to the operation. The operator and the parameters (and between parameters) should be separated by a single space.

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

Sample Input

Copy

Sample Output

Copy

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

Explanation for Sample

This program solves the first task. It has 10 instructions, which should give you 3 points on the task.

Grading

You are given nodes1.ans to nodes10.ans as well as example checkers. Each file corresponds to the grading parameters of the given task.

The test cases and the checker are available here.

Each file consists of 10 lines. The $i$ $i$ -th line consists of a parameter $w_i$ $w_{i}$ . The perfect score for a task is 10 points, and the tasks are graded independently.

If your output is not well-formatted or does not comply with the restrictions outlined in the problem, you will get 0 points on the task.

Otherwise, the checker will generate several test cases and run your program over the test cases.

If at some intermediate step during execution, the result $x_t$ $x_{t}$ has an absolute value exceeding $10^{1000}$ $10^{1000}$ , you will get 0 points on the subtask.

If one of the numbers printed (by an $O$ $O$ instruction) by your program differs with the expected output by at least $10^{-9}$ $10^{- 9}$ , you will get 0 points on the subtask.

If your program passes the test cases, the number of points you get on the task, $i$ $i$ , is the maximum $i$ $i$ such that $n \le w_i$ $n \leq w_{i}$ where $n$ $n$ is the number of instructions in your program. If $n > w_1$ $n > w_{1}$ , you will receive 0 points.

In particular, if you use comparison P, max M, or multiplication * instructions, for each type of instruction used, you will receive a penalty of 4 points for the task. Notice here the number of times you use each of the instructions is not relevant - what matters is the type of instructions used. For example, if you only use the comparison instruction but use it multiple times, you will receive a 4 point deduction for the task. If you use both comparison and multiplication once, you will receive an 8 point deduction for the task.

You can at least receive 0 points on a task: you won't receive a negative point on any task.

If you receive WA (Presentation Error) at DMOJ, it is likely that the program you wrote has syntax errors. If your program tries to read additional numbers from the terminal, contains too many instructions, has invalid parameters, overflows at some intermediate steps, or produces wrong outputs over a test case for your program, you shall receive WA.

Testing your output

First, please switch to the folder for the problem in the terminal using cd nodes: this assumes the nodes folder contains the inputs, outputs, and the checker for the problem.

Next, if you are using 64-bit Linux, run ./checker_linux64 <case_no> where <case_no> is the number of the task. For example, ./checker_linux64 3 grades nodes3.out.

If you are using Windows, run ./checker_win32 3.

If you are using 32-bit Linux, run ./checker_linux32 3.

If you are using Linux and you cannot run the checker, try executing chmod +x checker_linux64 or chmod +x checker_linux32 in the terminal and retry.

Finally, in the terminal you can use the command ./checker -f <file_name> to run the program given by <file_name> and interact with the terminal.

Warning: The checker provided does not necessarily run the same set of test cases as the checker for final evaluation!

Comments

There are no comments at the moment.