Description

Belle is a professional Proxy, which means she's also very good at hacking computers. Right now, she's trying to hack into a machine, but she has to explore what can the machine's processor do first.

A processor executes machine instructions. Assembly language is a human-readable way to describe those instructions. In this problem, you will help Belle run a small, RISC-V-inspired instruction set.

The program has exactly 10 registers, numbered from $0 to $9, all initially set to 0, and all of them can be modified. The program also has memory, which is separate from the registers and stores values at integer addresses. There is no specified limit on memory, so there can be 1 or 10,000 entries in the memory.

Instructions are numbered from 1 to n, and execution starts at instruction 1. Normally, execution continues with the next instruction. A jump changes which instruction executes next. Execution terminates when there are no more instructions to execute.

In the instruction examples below, register names such as $1 and $2 can be replaced by any register from $0 through $9.

Hint: All n instructions should be read and stored before execution begins, since jumps may refer to instructions that appear later in the input

Instructions

1. Load a value

li $1, c

Set $1 to the integer constant c.

2. Add

add $1, $2, $3

Add the values in $2 and $3, then store the result in $1: $1 = $2 + $3.

3. Multiply

mul $1, $2, $3

Multiply the values in $2 and $3, then store the result in $1: $1 = $2 × $3.

4. Copy a value

mv $1, $2

Copy the value in $2 into $1: $1 = $2. The value in $2 does not change.

5. Store in memory

sw $1, c($2)

Compute the memory address by adding c to the value stored in $2. Store the value in $1 at that address:

memory[$2 + c] = $1

An existing value at that address is overwritten. The registers do not change.

6. Load from memory

lw $1, c($2)

Compute the memory address by adding c to the value stored in $2. Load the value at that address into $1:

$1 = memory[$2 + c]

For both lw and sw, the offset c is an integer from 0 to 9, inclusive. This limit applies to the offset, not to the resulting memory address. For example, if $2 contains 1000, then 4($2) refers to memory address 1004.

7. Jump

j c

Continue execution at instruction c. The target c is an absolute instruction number, not an offset from the current instruction. For example, j 1 goes to the first instruction, regardless of where the jump occurs.

After the jump, execution continues from instruction c. It does not automatically return to the instruction after j.

8. Jump if equal

beq $1, $2, c

If $1 and $2 contain the same value, continue at instruction c. Otherwise, continue at the next instruction.

9. Jump if not equal

bne $1, $2, c

If $1 and $2 contain different values, continue at instruction c. Otherwise, continue at the next instruction.

For j, beq, and bne, c is an absolute, 1-based instruction number.

10. Print a character

print $1

Print the ASCII character whose code is the value in $1. For example, if $1 contains 65, print A.

Input

The first line contains an integer n, the number of instructions. Each of the next n lines contains one instruction.

All instructions are valid. Every lw reads a memory address that has already been written, and every program eventually terminates.

Output

• Test cases 1–4 contain only instructions 1–4.
• Test cases 5–6 contain only instructions 1–6.
• Test case 7 contains only instructions 1–7.
• Test case 8 and 9 contains only instructions 1–9.
• Test case 10 contains all instruction types.

Each print instruction outputs its ASCII character on a separate line.

After the program finishes, print a Python-style list containing the final values of registers $0 through $9, in that order.

Sample Input  Download

Sample Output  Download

Discuss

Description

Wise found out that Belle is not doing her job managing their video store Random Play, and instead she's doing something else. Turned out Belle is actually playing a brain game called Counting Queen, but with a special twist.

You are given an N×N chessboard that already has some queens on it. The already placed queens are in different rows. Place exactly one queen in every row that does not yet contain a queen, so that no two queens on the board attack each other. Two queens attack each other if they share a row, a column, or a diagonal. We guarantee that all the initally placed queens are valid

Your mission is to help Belle count how many different ways there are to do this, so she can go back to work and stop procrastinating. Two ways are different if at least one queen is placed in a different column.

To recall, a queen in chess can move horizontally, vertically, and diagonally. We want to count all possible number of ways to place the queens on the chessboard given that there is already some pre-placed queens

In the sample, we start with a 4×4 board and a pre-placed queen at (0,1), using zero-based coordinates. In row 1, the only safe position is (1,3). With these two queens in place, the only safe position in row 2 is (2,0). Finally, the queen in row 3 must be placed at (3,2).

This arrangement places exactly one queen in each row, with no two queens sharing a column or diagonal. It is the only valid completion that preserves the pre-placed queen, so the answer is 1.

Input

• The first line contains an integer N, the size of the grid. (1 ≤ N ≤ 12)
• The second line contains an integer K, the number of pre-placed queens. (0 ≤ K ≤ N)
• Each of the next K lines contains two integers r and c, the row and column of a pre-placed queen. (0 ≤ r, c < N)

Output

Print a single integer: the number of valid ways to place a queen in each remaining row.

Sample Input  Download

Sample Output  Download

Discuss

Description

 Credit: KKOMDASTRO

Aria is an idol, but she's also a robot in disguise, so she don't know whether the audience is cheering for her or not. In order to do that, she need to use a Finite State Machine. Can you help her build one?

Finite State Machine

A finite state machine (FSM) is a simple model of computation that reads a sequence of inputs one at a time and moves between a fixed set of “states” based on what it reads. FSMs are used in linguistics, in regular expressions, and in many other areas to check whether a string follows a given pattern. You can think of it as a flowchart: you stand on one box (a state), read one symbol, and follow the arrow labeled with that symbol to the next box.

Components of the machine

• Initial state: The single state where the machine always begins, before any input is read.
• Accepting state: A state that signals “success.” If the machine finishes reading all of its input and is sitting on the accepting state, the input string is considered valid (matches the pattern). In this problem, there is exactly one accepting state.
• Intermediate states: All the remaining states that are neither the initial state nor the accepting state. They are “stepping stones”: the machine passes through them while reading input, but ending on one of them means the input was not accepted.
• Transitions: Each state has an alphanumeric ID and exactly 2 next states: one to move to when the input is 0, and one to move to when the input is 1.

Note: the initial state may also be the accepting state, and a state can be its own next state (a “loop”).

How the machine runs

1. Start at the initial state.
2. For each input symbol (0 or 1) in order, move to the next state corresponding to that symbol.
3. After the last input, check which state you are on:
   • If it is the accepting state, output 1.
   • Otherwise, output 0.

Visualization: https://www.automataaa.com/

Example input 1

Example input 2

Input

• First line: The number of states $n$
• Next $n$ line: Each line will contain $3$ parts, splitted by a whitespace:
  • 1st part: The state ID
  • 2nd part: Next state ID if input is 0
  • 3rd part: Next state ID if input is 1
• Next line: Contain 2 parts, splitted by a whitespace:
  • 1st part: The initial state ID
  • 2nd part: The accepting state ID
• Last line: The input string for the machine.

Output

• First line: The result of the machine
  • 1 if after all the input, the machine ends on a accepting state.
  • 0 if otherwise.
• Second line: The state after the final input.

Sample Input  Download

Sample Output  Download

Discuss

Description

Credit: KKOMDASTRO

Nangong Yu's business is booming. Tickets for her idol group's next concert were over the moon. But she has a problem sorting the ticket, and she would like you to help her.

Nangong's given you a template code with the input and output already handled. Complete the two functions merge(left, right) and merge_sort(arr). merge_sort should return a new sorted list.

Do NOT modify the code under #---- Do not modify below ---- or use Python's built-in sorting functions, otherwise Nangong won't accept your solution and will fire you.

To help you further, Nangong also gave you this link: https://www.geeksforgeeks.org/dsa/merge-sort/

Template code

Input

• The first line contains an integer $n$ ($1 \le n \le 100000$).
• The second line contains n integers $a_1$, $a_2$, $...$, $a_n$ ($-10^9 \le a_i \le 10^9$), separated by spaces.

Output

Print the sorted sequence on one line, in ascending order, separated by single spaces.

Sample Input  Download

Sample Output  Download

Discuss

Description

Credit: KKOMDASTRO

After the ticket sorting, Nangong gave Sunna the total ticket sales for her to calculate. But since Nangong loves to mess with Sunna, she gave her a weird equation instead of just the final ticket sales. Your mission now is to write a simple calculator to help Sunna calculate the weird equation.

In fact, the equation Nangong gave was written in Prefix Notation.

In everyday math, we write expressions in infix notation, where the operator sits between its two operands:

$5 + 6$
$(5 * 6) - 7$

 This is natural for humans to read, but awkward for a computer to parse — it has to worry about operator precedence (does * happen before -?) and parentheses to disambiguate grouping.

Prefix notation solves this by placing the operator before its operands:

$+$ $5$ $6$ → $5 + 6$
$-$ $*$ $5$ $6$ $7$→ $(5 * 6) - 7$

An expression is either a number or an operator followed by two expressions.

For example, in $-$ $+$ $1$ $2$ $/$ $*$ $3$ $6$ $2$, the operator $-$ takes $(+$ $1$ $2)$ and $(/$ $*$ $3$ $6$ $2)$, so the value is $(1 + 2) - ((3 * 6) / 2) = -6$. The four operators are always binary.

Because the operator always comes first and each operator takes a fixed number of operands (two, for the basic arithmetic operators), there is never any ambiguity about order of operations, and no parentheses are ever needed.

Input

A single line containing a valid prefix-notation arithmetic expression. Tokens (operators and numbers) are separated by whitespace. You may assume:

• The supported operators are $+$, $-$, $*$, and $/$.
• All operands are non-negative integers. The result and intermediate values may be negative.
• No need to handle malformed input.
• Every division in the input is exact, and the divisor is never $0$.

Output

Print the result as a single integer

Sample Input  Download

Sample Output  Download

Discuss

Description

Roscaelifer is a bustling city in the sky, populated mostly by robots. Being in the sky, it's safe from most disasters on the ground, but it can also be very hard to find. But luckily, the city also shine bright like a star. Equipped with this information, your job now is to help us find it!

You are given an N × N matrix of integers and T queries, each query specifies a point (X, Y).

For each query, calculate the brightness of the point by summing:

1. All elements in row X.

2. All elements in column Y.

3. All elements on the top-left to bottom-right diagonal passing through (X, Y).

4. All elements on the top-right to bottom-left diagonal passing through (X, Y).

Note: The center element A[X][Y] must only be counted once.

To better illustrate, we will show to calculate the brightness for a given matrix at a point (3,3)

Hint.

If you cannot pass all the testcases, you can try to use extra arrays to record some information when you read the input data.

By doing so, you can immediately determine whether a point is a star.

Input

• An integer T, representing the number of queries (1 ≤ T ≤ 10000).

• An integer N, representing the matrix size (1 ≤ N ≤ 250).

• An N × N matrix of integers (0 ≤ A[i][j] ≤ N).

• T pairs of integers (X, Y), representing the queried positions.

Output

For each query, output a single integer representing the brightness of the specified point, followed by a newline.

Sample Input  Download

Sample Output  Download

Discuss