結果

問題 No.2069 み世界数式
ユーザー gew1fw
提出日時 2025-06-12 20:22:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,409 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 81,408 KB
実行使用メモリ 102,048 KB
最終ジャッジ日時 2025-06-12 20:23:48
合計ジャッジ時間 5,253 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools

def evaluate_expr(expr, M):
    def evaluate_sub(sub_expr):
        # First, handle parentheses recursively
        while True:
            start = sub_expr.rfind('(')
            if start == -1:
                break
            end = sub_expr.find(')', start)
            if end == -1:
                return None
            inner = sub_expr[start+1:end]
            inner_val = evaluate_sub(inner)
            if inner_val is None or inner_val < 0 or inner_val > M:
                return None
            sub_expr = sub_expr[:start] + str(inner_val) + sub_expr[end+1:]
        
        # Split into terms by '+' and '-'
        terms = []
        current = []
        ops = []
        for c in sub_expr:
            if c in '+-':
                if not current:
                    return None  # invalid operator position
                terms.append(''.join(current))
                ops.append(c)
                current = []
            else:
                current.append(c)
        if current:
            terms.append(''.join(current))
        else:
            return None  # trailing operator
        
        if not terms:
            return None
        
        # Evaluate each term (split by * and /)
        term_values = []
        for term in terms:
            factors = []
            current_factor = []
            factors_ops = []
            for c in term:
                if c in '*/':
                    if not current_factor:
                        return None  # invalid operator position
                    factors.append(''.join(current_factor))
                    factors_ops.append(c)
                    current_factor = []
                else:
                    current_factor.append(c)
            if current_factor:
                factors.append(''.join(current_factor))
            else:
                return None  # trailing operator
            
            if not factors:
                return None
            try:
                val = int(factors[0])
            except:
                return None
            if val < 0 or val > M:
                return None
            for i in range(len(factors_ops)):
                op = factors_ops[i]
                next_factor = factors[i+1]
                try:
                    num = int(next_factor)
                except:
                    return None
                if num < 0 or num > M:
                    return None
                if op == '*':
                    val *= num
                elif op == '/':
                    if num == 0:
                        return None
                    val = val // num
                    if val < 0:
                        return None
                else:
                    return None
                if val < 0 or val > M:
                    return None
            term_values.append(val)
        
        # Now evaluate the terms with + and -
        if not term_values:
            return None
        result = term_values[0]
        for i in range(len(ops)):
            op = ops[i]
            term_val = term_values[i+1]
            if op == '+':
                result += term_val
            elif op == '-':
                result -= term_val
            else:
                return None
            if result < 0 or result > M:
                return None
        return result
    
    return evaluate_sub(expr)

def main():
    import sys
    input = sys.stdin.read().splitlines()
    M_ans = input[0].split()
    M = int(M_ans[0])
    ans = int(M_ans[1])
    expr = input[1].strip()
    
    dollar_positions = [i for i, c in enumerate(expr) if c == '$']
    amp_positions = [i for i, c in enumerate(expr) if c == '&']
    
    total_dollars = len(dollar_positions)
    total_amps = len(amp_positions)
    
    for dollars in itertools.product(['+', '-'], repeat=total_dollars):
        for amps in itertools.product(['*', '/'], repeat=total_amps):
            expr_list = list(expr)
            for i, pos in enumerate(dollar_positions):
                expr_list[pos] = dollars[i]
            for i, pos in enumerate(amp_positions):
                expr_list[pos] = amps[i]
            new_expr = ''.join(expr_list)
            result = evaluate_expr(new_expr, M)
            if result == ans:
                print(new_expr)
                return
    print(-1)

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