#P7827. Stack Machine Assembly Tasks
Stack Machine Assembly Tasks
Stack Machine Assembly Tasks
This problem simulates an antique computer which uses two stacks, \(S_0\) and \(S_1\), each initially containing \(10^{10^{10}}\) zeros. The top element of stack \(S_i\) is denoted as \(T_i\). The computer supports 8 assembly instructions defined below (unless otherwise stated, all parameters are integers):
| Name | Parameters | Description | Pseudocode |
|---|---|---|---|
| and i | \(i \in \{0,1\}\) | Set \(T_i = T_i \mathbin{\And} T_{i \oplus 1}\). | \(T_i \gets T_i \mathbin{\And} T_{i \oplus 1}\) |
| or i | \(i \in \{0,1\}\) | Set \(T_i = T_i \mid T_{i \oplus 1}\). | \(T_i \gets T_i \mid T_{i \oplus 1}\) |
| xor i | \(i \in \{0,1\}\) | Set \(T_i = T_i \oplus T_{i \oplus 1}\). | \(T_i \gets T_i \oplus T_{i \oplus 1}\) |
| lsh i j | \(i \in \{0,1\},\; j \in [0,64]\) | Set \(T_i = T_i \times 2^j \bmod 2^{64}\) (left shift with natural overflow). | \(T_i \gets T_i \times 2^j \bmod 2^{64}\) |
| rsh i j | \(i \in \{0,1\},\; j \in [0,64]\) | Set \(T_i = \lfloor T_i / 2^j \rfloor\) (right shift with natural overflow). | \(T_i \gets \lfloor T_i / 2^j \rfloor\) |
| not i | \(i \in \{0,1\}\) | Set \(T_i = (2^{64}-1)-T_i\) (bitwise NOT). | \(T_i \gets (2^{64}-1)-T_i\) |
| pop i | \(i \in \{0,1\}\) | Pop the top element of stack \(S_i\). | Remove top element of \(S_i\) |
| mov i | \(i \in \{0,1\}\) | Move the top element \(T_i\) from \(S_i\) to the other stack \(S_{i\oplus 1}\) (i.e. push \(T_i\) onto \(S_{i\oplus 1}\) and then pop it from \(S_i\)). | Push \(T_i\) to \(S_{i\oplus 1}\); then pop from \(S_i\) |
Using these instructions, eight different computation tasks have been designed. In each task, the input is provided by pushing the given integers one by one onto stack \(S_0\) (the bottom zero remains unchanged), and the output is produced by sequentially popping some numbers from stack \(S_1\). Unless specified otherwise, all input integers are in the range \([0, 2^{64}-1]\).
The eight tasks are as follows:
- Swap: Input two numbers \(a, b\); output \(b, a\).
- Subtraction with Overflow: Input two numbers \(a, b\); output \((a-b+2^{64}) \bmod 2^{64}\).
- Reverse and Convert: Input nine integers \(a_1, a_2, \dots, a_9\) each in the range \([48,57]\) (i.e. ASCII codes for digits). Interpret them as a 9-digit string, reverse the string, then convert the reversed string into a decimal integer and output it. Note that the string may contain leading zeros.
- Parity of Bit Count: Input an integer \(a\); output \((\operatorname{popcnt}(a)) \bmod 2\), where \(\operatorname{popcnt}(a)\) is the number of \(1\)s in the binary representation of \(a\).
- Minimum: Input two numbers \(a, b\); output \(\min\{a,b\}\).
- Modular Multiplication: Input three numbers \(a, b, p\), where \(p\) is either 0 or a nonnegative power of 2. Output \((a\times b) \bmod p\), with the peculiarity that if \(p = 0\) then output 0.
- Integer Square Root: Input an integer \(a\) (which is 0 or a nonnegative power of 2) and output \(\sqrt{a}\). The answer is guaranteed to be a nonnegative power of 2 (or 0).
- Greatest Common Divisor (GCD): Input two numbers \(a, b\) (with \(1 \le a,b \le 63\)); output \(\gcd(a,b)\).
Input format note: In each test file, an extra first integer \(t\) (\(1 \le t \le 8\)) is provided which indicates the task to be performed. The rest of the input follows the specification of the corresponding task.
inputFormat
The first integer is \(t\) (\(1 \le t \le 8\)), representing the task id. The following input tokens are as specified for each task:
- If \(t=1\): Two integers \(a, b\).
- If \(t=2\): Two integers \(a, b\).
- If \(t=3\): Nine integers \(a_1, a_2, \dots, a_9\) (each in \([48,57]\)).
- If \(t=4\): One integer \(a\).
- If \(t=5\): Two integers \(a, b\).
- If \(t=6\): Three integers \(a, b, p\), where \(p=0\) or \(p=2^k\) for some nonnegative integer \(k\).
- If \(t=7\): One integer \(a\) (\(a\) is 0 or a power of 2).
- If \(t=8\): Two integers \(a, b\) (with \(1 \le a,b \le 63\)).
outputFormat
Output the result of the computation for the specified task. For tasks that require multiple outputs, print them in order separated by a space or newline as per your convenience.
sample
1
123 456456 123