## NOI '16 P6 - Computation

View as PDF

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 denote the result of the -th instruction. The permitted instructions, the syntax, and the result are given below:

NameOperatorParametersEffects
InputIN/ARead a real number from the terminal and make the number
OutputOPrint to the terminal, and
Addition+
Adding constantC
Negate-
Left shift<
Right shift>
SS
ComparisonP
MaxM
Multiplication*

Here, the definition of is given below where is the base of natural logarithm:

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

For each instruction, the parameters and must be smaller than the current instruction number . 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 to the adding constant instruction can have at most 90 digits in its decimal part.

For left shift and right shift instructions, must be a non-negative integer not exceeding .

The ten tasks are given below:

• Task 1: Given where and have at most 9 digits in their decimal parts, compute .
• Task 2: Given where and has at most 9 digits in its decimal part, compute .
• Task 3: Given where and has at most 9 digits in its decimal part, compute .
• Task 4: Given where and has at most 9 digits in its decimal part, compute the absolute value of , .
• Task 5: Given where , treat as a binary number where is the most significant bit and is the least significant bit, compute the corresponding value (in base 10).
• Task 6: Given integer where , output 32 integers denoting in base 2 representation. The most significant bit should be printed first and the least significant bit should be printed last. If has less than 32 bits in its binary representation, add leading 0s.
• Task 7: Given integers where , compute the bitwise XOR of and .
• Task 8: Given where and has at most 9 digits in its decimal part, output .
• Task 9: Given where and has at most 9 digits in its decimal part, print 16 real numbers representing the result of sorting in ascending order.
• Task 10: Given integers where , , compute the remainder after dividing by (i.e. compute ).

#### 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 -th line describes the -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 lines.

#### Sample Input

1

#### Sample Output

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.

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 -th line consists of a parameter . 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 has an absolute value exceeding , you will get 0 points on the subtask.

If one of the numbers printed (by an instruction) by your program differs with the expected output by at least , you will get 0 points on the subtask.

If your program passes the test cases, the number of points you get on the task, , is the maximum such that where is the number of instructions in your program. If , 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.

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.

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!