Canadian Informatics Workshop: 2025 Day 2, Problem 2

Election time is coming up in Kitchener! After having retired from her mayoral duties, this year Alanna is serving as the Chief Electoral Officer for the city. Things have been going well, but there is still one major issue—the polling stations have no software!

Thus, she's had to quickly assemble a team of programmers to program the polling stations before election day. You've been selected to be one of the programmers on the team, and have been tasked with writing a part of the polling software. Your goal is to write a program to multiply 2 numbers.

However, don't be fooled by the simplicity of this task! The polling stations are ancient, and so are only programmable in an archaic, obscure language called APL (Advanced Polling Language). APL only supports binary variables, along with the 4 binary operations AND, OR, NOT, and XOR (which can be applied on said variables). Are you up for the challenge?

Formally, you are given the constraints ~N~ and ~M~, and your goal is to output an APL program that inputs an ~N~-bit binary number ~x~ and an ~M~-bit binary number ~y~, and outputs their product ~x \times y~ as an ~(N+M)~-bit binary number. Moreover, as the polling station computers are very slow, your program may also only contain up to ~C~ instructions in total.

For the full output specification, please see the Output Specification section below.

Note on grading: The APL program that your code outputs will be graded on multiple test cases. Each test case in turn will simulate its execution on multiple pairs ~(x, y)~ of inputs. If the APL program does not compute the correct result on any input pair, it will be considered incorrect for that test case. Unfortunately, the electoral committee does not have the resources to test your program on a real polling station.

Input Specification

The first and only line of input contains ~3~ integers, ~N~, ~M~, and ~C~.

The following table shows how the available 25 marks are distributed:

Marks Awarded	Bounds on ~N~	Bounds on ~M~	Bounds on ~C~
2 marks	~N = 2~	~M = 1~	~C = 2 \cdot 10^6~
4 marks	~N \le 200~	~M \le 2~	~C = 2 \cdot 10^6~
4 marks	~N \le 200~	~M \le 6~	~C = 2 \cdot 10^6~
9 marks	~N \le 200~	~M \le 200~	~C = 2 \cdot 10^6~
3 marks	~N \le 200~	~M \le 200~	~C = 500\,000~
3 marks	~N \le 200~	~M \le 200~	~C = 300\,000~

Output Specification

Output a valid APL program. The language specification for APL is as follows:

On the first line, output an integer ~c~ (~1 \le c \le C~), the number of instructions in the program.

The next ~c~ lines should each contain one gate. Each gate should be a line in one of the following 4 forms:

• AND <in1> <in2>
• OR <in1> <in2>
• XOR <in1> <in2>
• NOT <in1>

The parameters and are variable identifiers that correspond to the input of each gate. APL supports only binary variables, each of which are identified by an integer.

Moreover, note that the instructions in your program will be executed in a sequential order. This means that the parameters and must use existing variables declared as the output in previous instructions. How variables are defined/interpreted is described below.

The first ~N~ variables (variables ~0~ to ~N-1~) correspond to the bits of the first input number ~x~ from the least to most significant bit, and the next ~M~ variables (variables ~N~ to ~N+M-1~) correspond to the bits of the second input number ~y~ in the same order.

Next, the output of every gate will each create a new variable starting from the variable ~N+M~ (e.g. the first gate outputs to the variable ~N+M~, the second gate outputs to ~N+M+1~, etc.).

Finally, the last ~N+M~ variables (which are the outputs of the last ~N+M~ gates) will be interpreted as the binary representation of the product ~z~ (where ~z = x \times y~) in order from least significant bit to most significant bit. Consequently, if your program has less than ~N+M~ gates, then it will be judged as incorrect.

Sample Input

1 1 2000000

Output for Sample Input

5
OR 0 1
NOT 2
AND 3 3
NOT 4
XOR 4 4

Explanation for Sample Output

The outputted APL program computes the bitwise OR of the input numbers ~x~ and ~y~ and stores it in the output number ~z~. Note that this program incorrectly computes ~x \times y~ and is for demonstration purposes only.

Additionally, note that since ~x~ and ~y~ are both ~1~-bit numbers, the output number ~z~ is expected to be ~1+1=2~ bits long, including any leading zeroes.