結果
| 問題 |
No.2069 み世界数式
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-16 00:23:04 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,420 bytes |
| コンパイル時間 | 261 ms |
| コンパイル使用メモリ | 81,672 KB |
| 実行使用メモリ | 85,688 KB |
| 最終ジャッジ日時 | 2025-04-16 00:24:30 |
| 合計ジャッジ時間 | 4,628 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 8 TLE * 1 -- * 32 |
ソースコード
import sys
import itertools
class ASTNode:
pass
class Expression(ASTNode):
def __init__(self, terms, operators):
self.terms = terms # list of Term nodes
self.operators = operators # list of operator indices (for $)
class Term(ASTNode):
def __init__(self, factors, operators):
self.factors = factors # list of Factor nodes
self.operators = operators # list of operator indices (for &)
class Factor(ASTNode):
def __init__(self, value, expr):
self.value = value # number, or None if it's an expression
self.expr = expr # Expression node, or None if it's a number
class Parser:
def __init__(self, tokens):
self.tokens = tokens
self.pos = 0
self.operators = [] # list of tuples (type, index)
self.operator_counter = 0
def parse_expression(self):
terms = []
operators = []
terms.append(self.parse_term())
while self.pos < len(self.tokens) and self.current_token() == '$':
op_type = self.current_token()
self.operators.append(('$', self.operator_counter))
operators.append(self.operator_counter)
self.operator_counter += 1
self.pos += 1
terms.append(self.parse_term())
return Expression(terms, operators)
def parse_term(self):
factors = []
operators = []
factors.append(self.parse_factor())
while self.pos < len(self.tokens) and self.current_token() == '&':
op_type = self.current_token()
self.operators.append(('&', self.operator_counter))
operators.append(self.operator_counter)
self.operator_counter += 1
self.pos += 1
factors.append(self.parse_factor())
return Term(factors, operators)
def parse_factor(self):
if self.current_token() == '(':
self.pos += 1
expr = self.parse_expression()
if self.current_token() != ')':
raise ValueError("Mismatched parentheses")
self.pos += 1
return Factor(None, expr)
else:
value = int(self.current_token())
self.pos += 1
return Factor(value, None)
def current_token(self):
if self.pos < len(self.tokens):
return self.tokens[self.pos]
return None
def tokenize(expr):
tokens = []
i = 0
while i < len(expr):
c = expr[i]
if c in '()&$':
tokens.append(c)
i += 1
elif c.isdigit():
j = i
while j < len(expr) and expr[j].isdigit():
j += 1
tokens.append(expr[i:j])
i = j
else:
i += 1
return tokens
def evaluate_expression(ast, operator_choices, M):
current_value = evaluate_term(ast.terms[0], operator_choices, M)
for i in range(1, len(ast.terms)):
op_index = ast.operators[i-1]
op_choice = operator_choices[op_index]
next_term_value = evaluate_term(ast.terms[i], operator_choices, M)
if op_choice == '+':
new_value = current_value + next_term_value
else:
new_value = current_value - next_term_value
if new_value < 0 or new_value > M:
raise ValueError("Intermediate out of range")
current_value = new_value
return current_value
def evaluate_term(term, operator_choices, M):
current_value = evaluate_factor(term.factors[0], operator_choices, M)
for i in range(1, len(term.factors)):
op_index = term.operators[i-1]
op_choice = operator_choices[op_index]
next_factor_value = evaluate_factor(term.factors[i], operator_choices, M)
if op_choice == '*':
new_value = current_value * next_factor_value
else:
if next_factor_value == 0:
raise ZeroDivisionError("Division by zero")
new_value = current_value // next_factor_value
if new_value < 0 or new_value > M:
raise ValueError("Intermediate out of range")
current_value = new_value
return current_value
def evaluate_factor(factor, operator_choices, M):
if factor.value is not None:
return factor.value
else:
return evaluate_expression(factor.expr, operator_choices, M)
def rebuild_expression(original_expr, operator_choices, operators_order):
expr_list = list(original_expr)
op_indices = [index for (_, index) in operators_order]
sorted_ops = sorted(zip(op_indices, operators_order), key=lambda x: x[0])
current_op = 0
for i in range(len(expr_list)):
c = expr_list[i]
if c in ('$', '&'):
if current_op >= len(operator_choices):
return None
expr_list[i] = operator_choices[sorted_ops[current_op][0]]
current_op += 1
return ''.join(expr_list)
def main():
M, ans = map(int, sys.stdin.readline().split())
expr_line = sys.stdin.readline().strip()
tokens = tokenize(expr_line)
parser = Parser(tokens)
try:
ast = parser.parse_expression()
except:
print(-1)
return
operators_order = parser.operators
if not operators_order:
try:
value = evaluate_expression(ast, [], M)
if value == ans and 0 <= value <= M:
print(expr_line)
else:
print(-1)
return
except:
print(-1)
return
choices_for_each = []
for op_type, index in operators_order:
if op_type == '$':
choices = ['+', '-']
else:
choices = ['*', '/']
choices_for_each.append(choices)
found = False
output_expr = None
for choices in itertools.product(*choices_for_each):
operator_choices = [''] * (max([index for _, index in operators_order]) + 1)
for i, (op_type, index) in enumerate(operators_order):
operator_choices[index] = choices[i]
try:
result = evaluate_expression(ast, operator_choices, M)
if result == ans:
output_expr = rebuild_expression(expr_line, operator_choices, operators_order)
print(output_expr)
return
except (ValueError, ZeroDivisionError):
continue
print(-1)
if __name__ == "__main__":
main()