Background
One day, while browsing an OJ, you discovered some interesting problems. You also noticed a new language available on the OJ: HackVM. You decide to solve these problems using HackVM.
Description
In the HackVM language, a character is an operation, and a program is a string. The program starts running from the first character of the string, moves to the next character after execution, and continues until it reaches the end of the string, terminates due to a runtime error, or executes a specific program termination operation. To prevent infinite loops, a maximum of $10^7$ operations are executed unless otherwise specified. The current execution position is called the $PC$. This language possesses an operand stack, a memory, and a call stack, all of which use long long ($64$-bit signed integers) as the unit—that is, one basic block can store one long long. All operations are based on long long (if your calculations involve numbers exceeding the range of long long, the correctness of the answer is not guaranteed, and the validator may detect this and report an error). The memory contains $2097152$ basic blocks, indexed starting from $0$.
Initially, the operand stack and the call stack are empty, and all memory blocks are initialized to $0$.
Operation Description
Assume $S_i$ is the content of the $(i+1)$-th block from the top of the operand stack before the operation is executed.
| Operation | Description |
|---|---|
| ' ' | Do nothing (counts towards code length) |
| 'p' | Pop $S_0$ and output $S_0$ as a long long |
| 'P' | Pop $S_0$ and output $S_0$ as a character |
| 'r' | Input an integer and push it onto the operand stack |
| 'R' | Input a character and push it onto the operand stack |
| '0' | Push the number $0$ onto the operand stack |
| '1' | Push the number $1$ onto the operand stack |
| '2' | Push the number $2$ onto the operand stack |
| '3' | Push the number $3$ onto the operand stack |
| '4' | Push the number $4$ onto the operand stack |
| '5' | Push the number $5$ onto the operand stack |
| '6' | Push the number $6$ onto the operand stack |
| '7' | Push the number $7$ onto the operand stack |
| '8' | Push the number $8$ onto the operand stack |
| '9' | Push the number $9$ onto the operand stack |
| '+' | Pop $S_0, S_1$ and push $S_1+S_0$ onto the operand stack |
| '-' | Pop $S_0, S_1$ and push $S_1-S_0$ onto the operand stack |
| '*' | Pop $S_0, S_1$ and push $S_1*S_0$ onto the operand stack |
| '/' | Pop $S_0, S_1$ and push $S_1/S_0$ onto the operand stack |
| ':' | Pop $S_0, S_1$; if $S_1 < S_0$ push $-1$, if $S_1 = S_0$ push $0$, if $S_1 > S_0$ push $1$ |
| 'g' | Pop $S_0$ and add $S_0$ to $PC$ |
| '?' | Pop $S_0, S_1$; if $S_1 = 0$ add $S_0$ to $PC$ |
| 'c' | Push current $PC$ onto the call stack, pop $S_0$, and set $PC$ to $S_0$ |
| '$' | Set $PC$ to the top of the call stack and pop the call stack |
| '<' | Pop $S_0$ and push the content of memory at index $S_0$ onto the operand stack |
| '>' | Pop $S_0, S_1$ and store $S_1$ in memory at index $S_0$ |
| '^' | Pop $S_0$ and push $S_{S_0+1}$ onto the operand stack (e.g., code 0^ copies the previous $S_0$) |
| 'v' | Pop $S_0$ and $S_{S_0+1}$, then push the latter back onto the operand stack (e.g., code 1v swaps the previous $S_0$ and $S_1$) |
| 'd' | Pop $S_0$ |
| '!' | Terminate the program |
For examples, specific implementation details, and executable code, refer to the interpreter hackvm.cpp.
Tasks
Test Case 1 (3 points)
Input two integers $a, b$, output $a+b$.
Test Case 2 (5 points)
Input two positive integers $a, b$, output $a \mod b$.
Test Case 3 (8 points)
Input three integers $a, b, c (1 \le a, b, c < 2^{31})$, output $a^b \mod c$.
Test Cases 4, 5 (7 points each)
The first line contains an odd integer $n (1 \le n \le 100)$. The next line contains $n$ integers. Output the median of these $n$ numbers.
Test Cases 6, 7 (9 points each)
Given an undirected graph, find the shortest path from node $1$ to every other node.
The first line contains $n, m (1 \le n \le 40, 1 \le m \le 500)$, representing the number of nodes and edges.
The next $m$ lines each contain three integers $u, v, w$, representing an edge between $u$ and $v$ with weight $w (0 \le w \le 10^9)$.
Output the sum of the shortest paths from node $1$ to all nodes (the result may exceed int).
It is guaranteed that there are no multiple edges or self-loops, and nodes are indexed starting from $1$.
Test Cases 8, 9 (13 points each)
Given a directed graph, find the number of strongly connected components. The first line contains $n, m (1 \le n \le 100, 1 \le m \le 3000)$, representing the number of nodes and edges. The next $m$ lines each contain two integers $u, v$, representing a directed edge from $u$ to $v$. Output the answer. It is guaranteed that there are no multiple edges or self-loops, and nodes are indexed starting from $1$.
Test Case 10 (12 points)
You need to output the program itself (i.e., implement a Quine program). Note that the code length cannot be 0.
Test Case 11 (14 points)
Given a piece of HackVM code, you need to run this code and output its result.
It is guaranteed that there are no r, R, or P operations, and p will be called exactly once. It is guaranteed that ! will be called to exit.
It is guaranteed that the program uses no more than 60000 operands and no more than 65536 memory blocks. There are no trailing newlines; you must read until EOF (-1).
Note
Your programs should be in the corresponding data*.out files, where * is the test case number. Each program should consist of only one line. The program and its output must not contain trailing newlines or extra spaces (spaces are no-ops but count towards code length).
For test cases other than test case 10, you cannot use the P operation (you only need to output an integer). For test case 10, you cannot use the p operation, and your output must not contain extra newlines or spaces.
All program code lengths should be between 1B and 50KB. It is guaranteed that all input numbers are within the int range. Each test case contains only one set of data. Test cases grouped together above are not bundled.
Download
This interpreter is undoubtedly a selfless gift from the kind problem setter. It covers the implementation of all operations in HackVM. You can use this interpreter to perform a comprehensive check of your programs. A sufficient number of operation groups and various error messages will ensure that errors in your program have nowhere to hide. The problem setter believes that this wonderful interpreter can provide powerful assistance on your journey to AC this problem.