結果

問題 No.2069 み世界数式
ユーザー gew1fw
提出日時 2025-06-12 18:43:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,127 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 85,632 KB
最終ジャッジ日時 2025-06-12 18:43:25
合計ジャッジ時間 4,946 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 1 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

def parse_expression(expr):
    tokens = []
    current = []
    for c in expr:
        if c in {'$', '&', '(', ')'}:
            if current:
                tokens.append(''.join(current))
                current = []
            tokens.append(c)
        else:
            current.append(c)
    if current:
        tokens.append(''.join(current))
    return tokens

def evaluate_expression(tokens, M, target):
    output = []
    operators = []
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    for token in tokens:
        if token == '(':
            operators.append(token)
        elif token == ')':
            while operators and operators[-1] != '(':
                output.append(operators.pop())
            if operators and operators[-1] == '(':
                operators.pop()
        elif token in precedence:
            while operators and operators[-1] != '(' and precedence[operators[-1]] >= precedence[token]:
                output.append(operators.pop())
            operators.append(token)
        else:
            output.append(token)
    while operators:
        output.append(operators.pop())
    
    stack = []
    for token in output:
        if token in {'+', '-', '*', '/'}:
            if len(stack) < 2:
                return False
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                res = a + b
            elif token == '-':
                res = a - b
            elif token == '*':
                res = a * b
            else:
                if b == 0:
                    return False
                res = a // b
            if not (0 <= res <= M):
                return False
            stack.append(res)
        else:
            num = int(token)
            if not (0 <= num <= M):
                return False
            stack.append(num)
    if len(stack) != 1:
        return False
    final = stack[0]
    return final == target

def main():
    M, ans = map(int, sys.stdin.readline().split())
    expr = sys.stdin.readline().strip()
    tokens = parse_expression(expr)
    operator_positions = []
    for i, token in enumerate(tokens):
        if token in {'$', '&'}:
            operator_positions.append(i)
    if not operator_positions:
        new_expr = ''.join(tokens)
        if new_expr == expr:
            print(-1)
        else:
            valid = evaluate_expression(tokens, M, ans)
            if valid:
                print(''.join(tokens))
            else:
                print(-1)
        return
    replacements = []
    for i in operator_positions:
        token = tokens[i]
        if token == '$':
            replacements.append(['+', '-'])
        else:
            replacements.append(['*', '/'])
    for combo in product(*replacements):
        new_tokens = tokens.copy()
        for idx, pos in enumerate(operator_positions):
            new_tokens[pos] = combo[idx]
        valid = evaluate_expression(new_tokens, M, ans)
        if valid:
            print(''.join(new_tokens))
            return
    print(-1)

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