結果

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

ソースコード

diff # 

import sys
from itertools import product

def main():
    M, ans = map(int, sys.stdin.readline().split())
    expr = sys.stdin.readline().strip()

    # Tokenize the expression
    def tokenize(s):
        tokens = []
        i = 0
        while i < len(s):
            c = s[i]
            if c in ('$', '&', '(', ')'):
                tokens.append(c)
                i += 1
            elif c.isdigit():
                num = []
                while i < len(s) and s[i].isdigit():
                    num.append(s[i])
                    i += 1
                tokens.append(''.join(num))
            else:
                return None  # invalid character
        return tokens

    original_tokens = tokenize(expr)
    if not original_tokens:
        print(-1)
        return

    # Collect positions of $ and & operators
    operator_positions = []
    operator_types = []
    for i, tok in enumerate(original_tokens):
        if tok in ('$', '&'):
            operator_positions.append(i)
            operator_types.append(tok)

    # Generate possible replacements for each operator
    replacements = []
    for op in operator_types:
        if op == '$':
            replacements.append(['+', '-'])
        else:
            replacements.append(['*', '/'])

    # Check if there are no operators
    if not replacements:
        # Check if the single number equals ans
        if len(original_tokens) == 1 and original_tokens[0].isdigit():
            num = int(original_tokens[0])
            if num == ans and 0 <= num <= M:
                print(original_tokens[0])
                return
        print(-1)
        return

    # Define the parser functions
    def evaluate_expression(tokens):
        try:
            tokens_copy = tokens.copy()
            value, remaining = parse_expression(tokens_copy)
            if remaining or value is None:
                return None
            return value
        except:
            return None

    def parse_expression(tokens):
        val, tokens = parse_term(tokens)
        if val is None:
            return None, None
        while tokens and tokens[0] in ('+', '-'):
            op = tokens.pop(0)
            right, tokens = parse_term(tokens)
            if right is None:
                return None, None
            if op == '+':
                new_val = val + right
            else:
                new_val = val - right
            if new_val < 0 or new_val > M:
                return None, None
            val = new_val
        return val, tokens

    def parse_term(tokens):
        val, tokens = parse_factor(tokens)
        if val is None:
            return None, None
        while tokens and tokens[0] in ('*', '/'):
            op = tokens.pop(0)
            right, tokens = parse_factor(tokens)
            if right is None:
                return None, None
            if op == '*':
                new_val = val * right
            else:
                if right == 0:
                    return None, None
                new_val = val // right
            if new_val < 0 or new_val > M:
                return None, None
            val = new_val
        return val, tokens

    def parse_factor(tokens):
        if not tokens:
            return None, None
        token = tokens[0]
        if token == '(':
            tokens.pop(0)
            val, tokens = parse_expression(tokens)
            if not tokens or tokens[0] != ')':
                return None, None
            tokens.pop(0)
            return (val, tokens)
        elif token.isdigit():
            num_str = tokens.pop(0)
            val = int(num_str)
            if val < 0 or val > M:
                return None, None
            return (val, tokens)
        else:
            return None, None

    # Iterate through all possible combinations
    for combo in product(*replacements):
        new_tokens = original_tokens.copy()
        for i, pos in enumerate(operator_positions):
            new_tokens[pos] = combo[i]
        # Check if the new_tokens form a valid expression
        value = evaluate_expression(new_tokens.copy())
        if value == ans:
            print(''.join(new_tokens))
            return

    print(-1)

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