No.3278 Avoid Division
タグ : / 解いたユーザー数 38
作問者 :
とりゐ
/ テスター :
👑 Problem Statement
There are a prime $P$ and a programming language that can perform addition, multiplication, and division in $\mathrm{mod}\ P$. $P$ is not given in the input and satisfies $10^8\lt P\lt 10^9$. ($P$ is determined in advance.)
Using this language, create a program that finds the answer to the following problem by performing at most $100$ additions, at most $100$ multiplications, and at most $1$ division.
There are $N$ operation instructions and a variable $x$. Initially, $x=0$. Now, the following operation is performed in order for $i=1,2,\ldots,N$.Find the value of $x$ after these operations.
- If $op_i=$
+:
Replace $x$ with $x + A_i\pmod P$ $(1\leq A_i\lt 10^8)$- If $op_i=$
*:
Replace $x$ with $x \times A_i\pmod P$ $(1\leq A_i\lt 10^8)$- If $op_i=$
/:
Replace $x$ with $x / A_i\pmod P$ $(1\leq A_i\lt 10^8)$
- Here, $a/b\pmod P\ (0\leq a\lt P, 1\leq b\lt P)$ is the unique integer $c\ (0\leq c\lt P)$ satisfying $a\equiv bc\pmod P$.
Program Specification
This program can use $26$ variables $a,b,\ldots,z$, represented by lowercase English letters.Each variable can hold an integer value at least $0$ and less than $P$.
When the program starts executing, $0$ is assigned to all variables.
Also, when the program starts, an array $A$ of length $N$ is given, and the program can refer to this array. (The values of the array cannot be changed.)
When the program finishes executing, the variable $a$ must hold the value of the answer.
Program Format
Line $1$ of the program contains an integer $M(\geq 0)$ representing the number of instructions in the program. Lines $2$ through $M+1$ of the program contain $M$ instructions. The instructions are executed sequentially from top to bottom.Each instruction is one of the following $3$ types.
-
add X Y Z- Assign $Y+Z \pmod P$ to $X$. Here, $X$ is a variable, and each of $Y,Z$ is a variable or an element of the array $A$.
-
mul X Y Z- Assign $Y\times Z \pmod P$ to $X$. Here, $X$ is a variable, and each of $Y,Z$ is a variable or an element of the array $A$.
-
div X Y Z- Assign $Y/Z \pmod P$ to $X$. Here, $X$ is a variable, each of $Y,Z$ is a variable or an element of the array $A$, and $Z\neq 0$ must hold.
A[i].
Program Execution Code
The program described above can be run on the code test and similar tools with the following code. Please make use of it.Program Execution Code (about 130 lines)
P = 998244353
import re
import sys
pattern = re.compile(r"A\[(\-?\d+)\]$")
def parse_A(s: str):
m = pattern.fullmatch(s)
if m:
return True, int(m.group(1))
else:
return False, None
def is_lowercase_letter(s: str) -> bool:
return len(s) == 1 and "a" <= s <= "z"
def add(x, y):
return (x + y) % P
def mul(x, y):
return x * y % P
def div(x, y):
if y == 0:
assert False, "Division by zero is not allowed"
return x * pow(y, P - 2, P) % P
n = int(input())
op = [""] * (n + 1)
A = [0] * (n + 1)
for i in range(1, n + 1):
op[i], A[i] = input().split()
A[i] = int(A[i])
x = 0
for i in range(1, n + 1):
if op[i] == "+":
x = add(x, A[i])
elif op[i] == "*":
x = mul(x, A[i])
elif op[i] == "/":
x = div(x, A[i])
else:
print("op[{}] is not '+', '*' and '/'".format(i))
assert 0
vals = {}
for i in range(26):
vals[chr(97 + i)] = 0
m = int(input())
if m < 0:
print("M must be 0 or positive.")
assert 0
add_count = 0
mul_count = 0
div_count = 0
for i in range(1, m + 1):
OP, X, Y, Z = input().split()
Yval = 0
if not is_lowercase_letter(X):
print("X[{}] is invalid format.".format(i))
assert 0
if is_lowercase_letter(Y):
Yval = vals[Y]
else:
valid, val = parse_A(Y)
if not valid:
print("Y[{}] is invalid format.".format(i))
assert 0
else:
if not 1 <= val <= n:
print("Y[{}] is invalid format.".format(i))
assert 0
Yval = A[val]
Zval = 0
if is_lowercase_letter(Z):
Zval = vals[Z]
else:
valid, val = parse_A(Z)
if not valid:
print("Z[{}] is invalid format.".format(i))
assert 0
else:
if not 1 <= val <= n:
print("Z[{}] is invalid format.".format(i))
assert 0
Zval = A[val]
if OP == "add":
vals[X] = add(Yval, Zval)
add_count += 1
elif OP == "mul":
vals[X] = mul(Yval, Zval)
mul_count += 1
elif OP == "div":
vals[X] = div(Yval, Zval)
div_count += 1
else:
print("OP[{}] is invalid format.".format(i))
assert 0
rest = sys.stdin.read().strip()
if rest:
print("Unexpected extra input")
assert 0
if add_count > 100:
print("number of add is greater than 100")
assert 0
if mul_count > 100:
print("number of mul is greater than 100")
assert 0
if div_count > 1:
print("number of div is greater than 1")
assert 0
print("Problem answer : {}".format(x))
print("Program 'a' : {}".format(vals["a"]))
Usage
The code runs in Python. Concatenate the problem's input and the program's instructions in this order, and pass the result to the Python code as input. The $P$ at the beginning of the Python code can be replaced with any prime you like.
Example using the sample
4 + 1 * 2 / 3 + 4 4 add b A[1] b mul c A[2] b div d c A[3] add a A[4] d
Input
$N$ $op_1\ A_1$ $\vdots$ $op_N\ A_N$
- $1\leq N\leq 100$
- $op_i$ is one of
+,*,/ - $1\leq A_i\lt 10^8$
- $N,A_i$ are integers
Output
Output a program that follows the specification and format described in the problem statement.
Sample
Sample 1
Input
4 + 1 * 2 / 3 + 4
Output
4 add b A[1] b mul c A[2] b div d c A[3] add a A[4] d
Consider the case $P=998244353$.
The answer to the problem is obtained as follows.
- Initially, $x=0$.
- For $i=1$, $x$ becomes $x+A_1\equiv 0+1\equiv1\pmod {998244353}$.
- For $i=2$, $x$ becomes $x\times A_2\equiv 1\times 2\equiv2 \pmod {998244353}$.
- For $i=3$, $x$ becomes $x/A_3\equiv 2/3\equiv 665496236 \pmod {998244353}$.
- For $i=4$, $x$ becomes $x+A_4\equiv 4+665496236\equiv 665496240\pmod {998244353}$.
- Finally, $x=665496240$.
- Initially, $a=b=c=\ldots=0$.
- In instruction $1$, $b$ becomes $A_1+b \equiv1+0\equiv 1\pmod {998244353}$.
- In instruction $2$, $c$ becomes $A_2\times b\equiv 2\times 1\equiv2 \pmod {998244353}$.
- In instruction $3$, $d$ becomes $c/A_3\equiv2/3\equiv 665496236 \pmod {998244353}$.
- In instruction $4$, $a$ becomes $A_4+d\equiv4+665496236\equiv 665496240\pmod {998244353}$.
- Finally, $a=665496240$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。