結果

問題 No.2069 み世界数式
ユーザー gew1fw
提出日時 2025-06-12 13:34:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,401 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 108,224 KB
最終ジャッジ日時 2025-06-12 13:40:08
合計ジャッジ時間 4,852 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

def tokenize(expr):
    tokens = []
    i = 0
    while i < len(expr):
        if expr[i] in '()+-*/$&':
            tokens.append(expr[i])
            i += 1
        elif expr[i].isdigit():
            num = 0
            while i < len(expr) and expr[i].isdigit():
                num = num * 10 + int(expr[i])
                i += 1
            tokens.append(str(num))
        else:
            i += 1
    return tokens

def infix_to_postfix(tokens):
    precedence = {'+':1, '-':1, '*':2, '/':2}
    output = []
    stack = []
    for token in tokens:
        if token.isdigit():
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # 移除 '('
        elif token in precedence:
            while stack and stack[-1] != '(' and precedence[token] <= precedence.get(stack[-1], 0):
                output.append(stack.pop())
            stack.append(token)
    while stack:
        output.append(stack.pop())
    return output

def evaluate_postfix(postfix, M, ans):
    try:
        stack = []
        for token in postfix:
            if token.isdigit():
                stack.append(int(token))
            else:
                if len(stack) < 2:
                    return False, None
                b = stack.pop()
                a = stack.pop()
                if token == '+':
                    res = a + b
                elif token == '-':
                    res = a - b
                    if res < 0:
                        return False, None
                elif token == '*':
                    res = a * b
                elif token == '/':
                    if b == 0:
                        return False, None
                    res = a // b
                else:
                    return False, None
                if res < 0 or res > M:
                    return False, None
                stack.append(res)
        if len(stack) != 1:
            return False, None
        final = stack[0]
        return final == ans, final
    except:
        return False, None

def main():
    import sys
    input = sys.stdin.read().splitlines()
    M, ans = map(int, input[0].split())
    expr = input[1].strip()

    dollar_indices = [i for i, c in enumerate(expr) if c == '$']
    amp_indices = [i for i, c in enumerate(expr) if c == '&']

    replacement_options = []
    for i in range(len(dollar_indices)):
        replacement_options.append(['+', '-'])
    for i in range(len(amp_indices)):
        replacement_options.append(['*', '/'])

    for replacement in product(*replacement_options):
        expr_list = list(expr)
        dollar_idx = 0
        amp_idx = 0
        for i, c in enumerate(expr_list):
            if c == '$':
                expr_list[i] = replacement[dollar_idx]
                dollar_idx += 1
            elif c == '&':
                expr_list[i] = replacement[amp_idx + len(dollar_indices)]
                amp_idx += 1
        new_expr = ''.join(expr_list)
        tokens = tokenize(new_expr)
        postfix = infix_to_postfix(tokens)
        success, final = evaluate_postfix(postfix, M, ans)
        if success:
            print(new_expr)
            return
    print(-1)

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