Yet Another Contest 5 P4 - Nils++

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

Nils has developed a new programming language, Nils++!

A Nils++ program consists of multiple lines. Each line is either blank (in which case it will be ignored), or contains exactly one statement. Due to computing limitations, there cannot be more than 10^6 statements.

A Nils++ interpreter uses 10^5 cells, labelled from 1 to 10^5. Each cell contains an integer, which must be in the range [-2 \times 10^{18}, 2 \times 10^{18}] at all times.

There are only six different types of statements:

  • ADD A B C Compute the sum of the values in cells A and B, and store the result in cell C.
  • NEG A B Negate the value in cell A, and store the result in cell B.
  • ABS A B Calculate the absolute value of the value in cell A, and store the result in cell B.
  • SGN A B Calculate the sign function of the value in cell A, and store the result in cell B.
  • CLR A B If the value in cell A is nonzero, set the value in cell B to 0. Otherwise, if the value in cell A is 0, then do nothing.
  • OUT A Output the value in cell A.

Note that A, B and C represent integers between 1 and 10^5 (inclusive).

The output of the program is the sequence of values outputted using the OUT statement, in the order that they were outputted.

In order to demonstrate the versatility of his programming language, Nils wishes to create various Nils++ programs that solve different tasks. The seven tasks are listed below:

Task 1: EQUALS
  • Initially, cell 1 contains an integer X, and cell 2 contains an integer Y. All other cells contain the integer 0.
  • -10^9 \le X, Y \le 10^9.
  • At least one of X and Y is nonzero.
  • You should output a single integer, equal to 1 if X = Y, and 0 if X \ne Y.
Task 2: MAX
  • Initially, cell 1 contains an integer X, and cell 2 contains an integer Y. All other cells contain the integer 0.
  • -10^9 \le X, Y \le 10^9.
  • You should output a single integer, equal to \max(X, Y).
Task 3: PRODUCT
  • Initially, cell 1 contains an integer X, and cell 2 contains an integer Y. All other cells contain the integer 0.
  • -10^9 \le X, Y \le 10^9.
  • You should output a single integer, equal to X \times Y.
Task 4: GCD
  • Initially, cell 1 contains an integer X, and cell 2 contains an integer Y. All other cells contain the integer 0.
  • 1 \le X, Y \le 10^9.
  • You should output a single integer, equal to \gcd(X, Y).
Task 5: XOR
  • Initially, cell 1 contains an integer X, and cell 2 contains an integer Y. All other cells contain the integer 0.
  • 0 \le X, Y \le 10^9.
  • You should output a single integer, equal to X \oplus Y. Here, \oplus denotes the bitwise XOR operator.
Task 6: PRIMES
  • Initially, cell 1 contains an integer X. All other cells contain the integer 0.
  • 1 \le X \le 2 \times 10^6.
  • You should output a single integer, equal to number of primes which are less than or equal to X.
Task 7: SORT
  • Initially, cells 1 to 400 contain the integers a_1, a_2, \dots, a_{400} respectively. All other cells contain the integer 0.
  • -10^9 \le a_i \le 10^9.
  • You should output 400 integers. The output of the program should be the result when a_1, a_2, \dots, a_{400} is sorted.

Experimentation

You will be provided with a Nils++ interpreter for local testing purposes. There are two versions of the interpreter, one written in Python and one written in C++.

Both of the interpreters read from standard input and write to standard output.

The first line of input should contain a single integer, N, satisfying 0 \le N \le 10^5. This represents that the first N cells will be initialised to specified values, with all other cells being initialised to 0.

The second line should contain N space-separated integers, with each integer in the range [-2 \times 10^{18}, 2 \times 10^{18}]. These represent the initial values contained in cells 1, 2, \dots, N respectively.

The remaining lines of input should contain the Nils++ program.

Both interpreters will print out all values outputted using the OUT statement, in the order they were outputted, with one integer on each line.

Note that the interpreters are intended solely for testing purposes, and as such may not parse poorly-formatted input properly.

Subtasks

SubtaskPointsTaskAdditional Constraints
1101-
2102-
3103-10^5 \le X, Y \le 10^5
4103-
5204-
6155-
7156-
8107-

Input Specification

The only line contains a single integer between 1 and 7 (inclusive), representing the task number.

Output Specification

Output one or more lines. Each line should be blank, or contain exactly one statement in the described format. There should be at most 10^6 non-empty lines.

Sample Input

1

Sample Output

ADD 1 2 1
NEG 2 3
SGN 3 3
ABS 3 3
CLR 1 3
OUT 3

Explanation

This program is supposed to output whether two numbers are equal. This sample output would not be accepted, and is intended only as a clarification of the behaviour of each statement.

Let's assume that initially, cell 1 contains the integer 2, cell 2 contains the integer 2, and all other cells contain the integer 0. Denote v_i as the integer stored in cell i. Then, the interpreter would execute the following:

  • Calculate v_1 + v_2 = 2 + 2 = 4. Then, set v_1 to 4.
  • Calculate -v_2 = -2. Then, set v_3 to -2.
  • Calculate sgn(v_3) = sgn(-2) = -1. Then, set v_3 to -1.
  • Calculate |v_3| = |-1| = 1. Then, set v_3 to 1.
  • Since v_1 is nonzero, set v_3 to 0.
  • Output v_3 = 0.

The actual output of the program is 0, but the correct output is 1 since cells 1 and 2 initially contained the same integer. Hence, this program would receive a Wrong Answer verdict.


Comments

There are no comments at the moment.