結果

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

ソースコード

diff # 

import itertools

def tokenize(expr):
    tokens = []
    current = ''
    for c in expr:
        if c in '+-*/()':
            if current:
                tokens.append(current)
                current = ''
            tokens.append(c)
        else:
            current += c
    if current:
        tokens.append(current)
    return tokens

def shunting_yard(tokens):
    output = []
    stack = []
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    for token in tokens:
        if token.isdigit():
            output.append(token)
        elif token in precedence:
            while stack and stack[-1] != '(' and precedence[token] <= precedence.get(stack[-1], 0):
                output.append(stack.pop())
            stack.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            if not stack:
                return None  # Mismatched parentheses
            stack.pop()  # Remove '('
        else:
            return None  # Invalid token
    while stack:
        if stack[-1] == '(':
            return None  # Mismatched parentheses
        output.append(stack.pop())
    return output

def evaluate(converted_expr, M):
    tokens = tokenize(converted_expr)
    if not tokens:
        return None
    rpn = shunting_yard(tokens)
    if rpn is None:
        return None
    stack = []
    for token in rpn:
        if token.isdigit():
            num = int(token)
            if num < 0 or num > M:
                return None
            stack.append(num)
        else:
            if len(stack) < 2:
                return None
            b = stack.pop()
            a = stack.pop()
            if token == '+':
                res = a + b
            elif token == '-':
                res = a - b
            elif token == '*':
                res = a * b
            elif token == '/':
                if b == 0:
                    return None
                res = a // b
            else:
                return None
            if res < 0 or res > M:
                return None
            stack.append(res)
    if len(stack) != 1:
        return None
    return stack[0]

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

    # Collect positions and types of operators
    original_operators = []
    for idx, c in enumerate(expr):
        if c in {'$', '&'}:
            original_operators.append((idx, c))
    
    # Generate possible replacements
    operator_choices = []
    for pos, typ in original_operators:
        if typ == '$':
            operator_choices.append(['+', '-'])
        else:
            operator_choices.append(['*', '/'])
    
    # Generate all combinations
    for combo in itertools.product(*operator_choices):
        converted = list(expr)
        for i in range(len(original_operators)):
            pos = original_operators[i][0]
            converted[pos] = combo[i]
        converted_expr = ''.join(converted)
        # Evaluate
        result = evaluate(converted_expr, M)
        if result == ans:
            print(converted_expr)
            return
    print(-1)

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