結果

問題 No.2069 み世界数式
ユーザー lam6er
提出日時 2025-04-16 00:18:46
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,812 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 81,388 KB
実行使用メモリ 848,252 KB
最終ジャッジ日時 2025-04-16 00:20:29
合計ジャッジ時間 6,502 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8 MLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

def tokenize(expr):
    tokens = []
    i = 0
    while i < len(expr):
        c = expr[i]
        if c in '()$&':
            tokens.append({'value': c, 'type': 'paren' if c in '()' else 'op', 'pos': i})
            i += 1
        elif c.isdigit():
            num = []
            pos = i
            while i < len(expr) and expr[i].isdigit():
                num.append(expr[i])
                i += 1
            tokens.append({'value': ''.join(num), 'type': 'number', 'pos': pos})
        else:
            i += 1
    return tokens

def parse_factor(tokens, pos):
    if pos >= len(tokens):
        return [], pos
    token = tokens[pos]
    if token['value'] == '(':
        pos += 1
        expr_values, pos = parse_expression(tokens, pos)
        if pos >= len(tokens) or tokens[pos]['value'] != ')':
            return [], pos
        pos += 1
        return expr_values, pos
    elif token['type'] == 'number':
        num = int(token['value'])
        if num < 0 or num > M:
            return [], pos + 1
        return [ (num, {}) ], pos + 1
    else:
        return [], pos

def parse_term(tokens, pos):
    factor_values, pos = parse_factor(tokens, pos)
    if not factor_values:
        return [], pos
    current = factor_values
    while pos < len(tokens) and tokens[pos]['value'] == '&':
        op_pos = tokens[pos]['pos']
        pos += 1
        next_factor_values, pos = parse_factor(tokens, pos)
        if not next_factor_values:
            return [], pos
        new_current = []
        for (val1, ops1) in current:
            for (val2, ops2) in next_factor_values:
                for op in ['*', '/']:
                    if op == '/' and val2 == 0:
                        continue
                    if op == '*':
                        new_val = val1 * val2
                    else:
                        new_val = val1 // val2
                    if new_val < 0 or new_val > M:
                        continue
                    merged_ops = ops1.copy()
                    merged_ops.update(ops2)
                    merged_ops[op_pos] = op
                    new_current.append( (new_val, merged_ops) )
        current = new_current
        if not current:
            return [], pos
    return current, pos

def parse_expression(tokens, pos):
    term_values, pos = parse_term(tokens, pos)
    if not term_values:
        return [], pos
    current = term_values
    while pos < len(tokens) and tokens[pos]['value'] == '$':
        op_pos = tokens[pos]['pos']
        pos += 1
        next_term_values, pos = parse_term(tokens, pos)
        if not next_term_values:
            return [], pos
        new_current = []
        for (val1, ops1) in current:
            for (val2, ops2) in next_term_values:
                for op in ['+', '-']:
                    new_val = val1 + val2 if op == '+' else val1 - val2
                    if new_val < 0 or new_val > M:
                        continue
                    merged_ops = ops1.copy()
                    merged_ops.update(ops2)
                    merged_ops[op_pos] = op
                    new_current.append( (new_val, merged_ops) )
        current = new_current
        if not current:
            return [], pos
    return current, pos

M, ans = map(int, input().split())
expr = input().strip()

tokens = tokenize(expr)
operator_tokens = [t for t in tokens if t['value'] in {'$', '&'}]

possible_values, _ = parse_expression(tokens, 0)

found = False
output_str = -1

for value, ops in possible_values:
    if value == ans:
        output = list(expr)
        for op_token in operator_tokens:
            pos = op_token['pos']
            if pos in ops:
                output[pos] = ops[pos]
        output_str = ''.join(output)
        found = True
        break

print(output_str if found else -1)
0