結果

問題 No.2069 み世界数式
ユーザー lam6er
提出日時 2025-03-20 20:31:27
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,848 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 848,628 KB
最終ジャッジ日時 2025-03-20 20:32:34
合計ジャッジ時間 5,007 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 MLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class ExprNode:
    pass

class NumberNode(ExprNode):
    def __init__(self, value):
        self.value = value

class BinOpNode(ExprNode):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

class ParenExprNode(ExprNode):
    def __init__(self, expr):
        self.expr = expr

def tokenize(expr):
    tokens = []
    i = 0
    while i < len(expr):
        c = expr[i]
        if c in '()$&':
            tokens.append(c)
            i += 1
        elif c.isdigit():
            num = []
            while i < len(expr) and expr[i].isdigit():
                num.append(expr[i])
                i += 1
            tokens.append(''.join(num))
        else:
            i += 1
    return tokens

def parse_expression(tokens):
    node = parse_term(tokens)
    while tokens and tokens[0] == '$':
        op = tokens.pop(0)
        right = parse_term(tokens)
        node = BinOpNode('$', node, right)
    return node

def parse_term(tokens):
    node = parse_factor(tokens)
    while tokens and tokens[0] == '&':
        op = tokens.pop(0)
        right = parse_factor(tokens)
        node = BinOpNode('&', node, right)
    return node

def parse_factor(tokens):
    if not tokens:
        raise SyntaxError("Unexpected end of input")
    if tokens[0] == '(':
        tokens.pop(0)
        expr = parse_expression(tokens)
        if not tokens or tokens[0] != ')':
            raise SyntaxError("Unclosed parenthesis")
        tokens.pop(0)
        return ParenExprNode(expr)
    elif tokens[0].isdigit():
        num_str = tokens.pop(0)
        while tokens and tokens[0].isdigit():
            num_str += tokens.pop(0)
        return NumberNode(int(num_str))
    else:
        raise SyntaxError(f"Unexpected token: {tokens[0]}")

def evaluate(node, M):
    if isinstance(node, NumberNode):
        return [(str(node.value), node.value)]
    elif isinstance(node, ParenExprNode):
        inner = evaluate(node.expr, M)
        return [(f'({s})', v) for (s, v) in inner]
    elif isinstance(node, BinOpNode):
        left_options = evaluate(node.left, M)
        right_options = evaluate(node.right, M)
        possible = []
        operators = {'$': ['+', '-'], '&': ['*', '/']}
        for op in operators[node.op]:
            for (ls, lv) in left_options:
                for (rs, rv) in right_options:
                    valid = True
                    current_val = None
                    if op == '+':
                        current_val = lv + rv
                    elif op == '-':
                        current_val = lv - rv
                    elif op == '*':
                        current_val = lv * rv
                    elif op == '/':
                        if rv == 0:
                            valid = False
                        else:
                            current_val = lv // rv
                            if current_val < 0:
                                valid = False
                    if current_val is not None and (current_val < 0 or current_val > M):
                        valid = False
                    if valid:
                        expr_str = ls + op + rs
                        possible.append((expr_str, current_val))
        return possible
    else:
        return []

def main():
    M_ans_line = sys.stdin.readline().strip()
    M, ans = map(int, M_ans_line.split())
    expr_line = sys.stdin.readline().strip()
    
    try:
        tokens = tokenize(expr_line)
        ast = parse_expression(tokens)
        if tokens:
            raise SyntaxError("Invalid syntax")
    except Exception as e:
        print(-1)
        return
    
    options = evaluate(ast, M)
    for s, val in options:
        if val == ans:
            print(s)
            return
    print(-1)

if __name__ == "__main__":
    main()
0