結果

問題 No.2069 み世界数式
ユーザー lam6er
提出日時 2025-03-31 17:45:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,533 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 73,500 KB
最終ジャッジ日時 2025-03-31 17:46:02
合計ジャッジ時間 5,913 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 1 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from itertools import product

    M_ans = sys.stdin.readline().strip()
    M, ans = map(int, M_ans.split())
    expr = sys.stdin.readline().strip()

    # Tokenization
    tokens = []
    i = 0
    n = len(expr)
    while i < n:
        c = expr[i]
        if c in {'(', ')', '$', '&'}:
            tokens.append(c)
            i += 1
        elif c.isdigit():
            j = i
            while j < n and expr[j].isdigit():
                j += 1
            num = int(expr[i:j])
            tokens.append(num)
            i = j
        else:
            i += 1

    # Extract the operator list
    op_list = [tok for tok in tokens if tok in {'$', '&'}]

    # Check case with no operators
    if not op_list:
        if len(tokens) == 1 and isinstance(tokens[0], int) and tokens[0] == ans:
            print(expr)
            return
        else:
            print(-1)
            return

    # Generate all possible operator choices
    choices_options = []
    for op in op_list:
        if op == '$':
            choices_options.append(['+', '-'])
        else:
            choices_options.append(['*', '/'])

    # Parse helper functions
    def parse(tokens):
        index = [0]
        val, valid = parse_expression(tokens, index)
        if valid and index[0] == len(tokens):
            return (val, True)
        else:
            return (0, False)

    def parse_expression(tokens, index):
        val, valid = parse_term(tokens, index)
        if not valid:
            return (0, False)
        while index[0] < len(tokens):
            current_token = tokens[index[0]]
            if current_token not in {'+', '-'}:
                break
            op = current_token
            index[0] += 1
            term_val, valid_term = parse_term(tokens, index)
            if not valid_term:
                return (0, False)
            if op == '+':
                new_val = val + term_val
            else:
                new_val = val - term_val
            if not (0 <= new_val <= M):
                return (0, False)
            val = new_val
        return (val, True)

    def parse_term(tokens, index):
        val, valid = parse_factor(tokens, index)
        if not valid:
            return (0, False)
        while index[0] < len(tokens):
            current_token = tokens[index[0]]
            if current_token not in {'*', '/'}:
                break
            op = current_token
            index[0] += 1
            factor_val, valid_factor = parse_factor(tokens, index)
            if not valid_factor:
                return (0, False)
            if op == '*':
                new_val = val * factor_val
            else:
                if factor_val == 0:
                    return (0, False)
                new_val = val // factor_val
            if not (0 <= new_val <= M):
                return (0, False)
            val = new_val
        return (val, True)

    def parse_factor(tokens, index):
        if index[0] >= len(tokens):
            return (0, False)
        current_token = tokens[index[0]]
        if current_token == '(':
            index[0] += 1
            expr_val, valid_expr = parse_expression(tokens, index)
            if not valid_expr or index[0] >= len(tokens) or tokens[index[0]] != ')':
                return (0, False)
            index[0] += 1
            return (expr_val, True)
        elif isinstance(current_token, int):
            val = current_token
            index[0] += 1
            if not (0 <= val <= M):
                return (0, False)
            return (val, True)
        else:
            return (0, False)

    # Iterate over all possible choices and check validity
    for choice in product(*choices_options):
        # Build replaced tokens
        replaced_tokens = []
        op_idx = 0
        for tok in tokens:
            if tok in {'$', '&'}:
                replaced_tokens.append(choice[op_idx])
                op_idx += 1
            else:
                replaced_tokens.append(tok)
        # Parse and check
        result, valid = parse(replaced_tokens)
        if valid and result == ans:
            # Build the output string
            output = []
            op_idx = 0
            for c in expr:
                if c in {'$', '&'}:
                    output.append(choice[op_idx])
                    op_idx += 1
                else:
                    output.append(c)
            print(''.join(output))
            return

    print(-1)

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