問題一覧 > 通常問題

No.3278 Avoid Division

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 38
作問者 : とりゐ / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10319 / 自分の提出
問題文最終更新日: 2025-09-19 17:31:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest オムニバス (順位表) の他の問題:

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$.
  • 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$.
Find the value of $x$ after these operations.

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.
To refer to the $i\ (1\leq i\leq N)$-th element of $A$, write it as 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$.
On the other hand, the program works as follows.
  • 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$.
Since the answer to the problem matches $a$ in the program, this is a correct output. The conditions on the numbers of additions, multiplications, and divisions in the program are also satisfied.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。