結果
| 問題 |
No.2069 み世界数式
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,479 bytes |
| コンパイル時間 | 177 ms |
| コンパイル使用メモリ | 82,104 KB |
| 実行使用メモリ | 79,724 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:52 |
| 合計ジャッジ時間 | 6,592 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 WA * 19 |
ソースコード
import sys
# Set a higher recursion depth limit for potentially deep expression trees.
# The problem constraints allow expression lengths up to 1000, which could lead to
# recursion depths close to that in worst-case scenarios (like deeply nested parentheses).
# Python's default limit is often 1000, so increasing it is safer.
try:
sys.setrecursionlimit(2000)
except Exception as e:
# Some environments might restrict changing the recursion limit.
# If it fails, we proceed with the default limit and hope it's sufficient.
pass
# Read M (maximum value) and ans (target answer)
M, ans = map(int, sys.stdin.readline().split())
# Read the expression string
expr_str = sys.stdin.readline().strip()
# Define a class for Abstract Syntax Tree (AST) nodes
class Node:
def __init__(self, type, value=None, left=None, right=None):
self.type = type # Node type: 'num', '$', or '&'
self.value = value # Stores the integer value for 'num' nodes
self.left = left # Left child node for operator nodes
self.right = right # Right child node for operator nodes
# Flag to indicate if this node represents a subexpression originally enclosed in parentheses
self.is_parenthesized = False
# Use object ID for memoization keys, ensuring unique identification for each node instance
self.id = id(self)
# Global variable to keep track of the current position in the expression string during parsing
pos = 0
# Flag to indicate if parsing encountered an error (e.g., invalid format)
parsing_failed = False
# Recursive descent parser functions based on the provided BNF grammar
# Parses a factor: either a number or a parenthesized expression
def parse_factor():
global pos, parsing_failed
# Prevent reading past the end of the string
if pos >= len(expr_str):
parsing_failed = True
# Return a dummy node to simplify error handling upstream
return Node('num', value=-1)
# Check if the current character indicates the start of a parenthesized expression
if expr_str[pos] == '(':
pos += 1 # Consume '('
# Recursively parse the expression within the parentheses
node = parse_expression()
# If parsing the inner expression failed, propagate the error
if parsing_failed: return node
# Expect a closing parenthesis
if pos >= len(expr_str) or expr_str[pos] != ')':
parsing_failed = True # Error: Mismatched or missing parenthesis
return Node('num', value=-1)
pos += 1 # Consume ')'
# Mark the node representing the inner expression as parenthesized.
# This is important for correct reconstruction of the output string.
node.is_parenthesized = True
return node
else:
# Parse a number
num_str = ""
start_pos = pos
# Consume all consecutive digits
while pos < len(expr_str) and expr_str[pos].isdigit():
num_str += expr_str[pos]
pos += 1
# If no digits were found, it's a syntax error (expected number or '(')
if not num_str:
parsing_failed = True
return Node('num', value=-1)
val = int(num_str)
# Create a 'num' node. The validity check (0 <= val <= M) is handled later.
return Node('num', value=val)
# Parses a term: a sequence of factors combined by '&' operators (multiplication/division)
def parse_term():
global pos, parsing_failed
# A term starts with a factor
node = parse_factor()
if parsing_failed: return node # Propagate parsing errors
# Repeatedly parse '&' followed by a factor, respecting left-to-right associativity
while pos < len(expr_str) and expr_str[pos] == '&':
op_type = '&'
pos += 1 # Consume '&'
# Parse the right operand (another factor)
right_node = parse_factor()
if parsing_failed: return right_node # Propagate parsing errors
# Create a new '&' node with the current term expression as left child
# and the newly parsed factor as right child.
new_node = Node(op_type, left=node, right=right_node)
# Update 'node' to be the root of the term evaluated so far
node = new_node
return node
# Parses an expression: a sequence of terms combined by '$' operators (addition/subtraction)
def parse_expression():
global pos, parsing_failed
# An expression starts with a term
node = parse_term()
if parsing_failed: return node # Propagate parsing errors
# Repeatedly parse '$' followed by a term, respecting left-to-right associativity
while pos < len(expr_str) and expr_str[pos] == '$':
op_type = '$'
pos += 1 # Consume '$'
# Parse the right operand (another term)
right_node = parse_term()
if parsing_failed: return right_node # Propagate parsing errors
# Create a new '$' node with the current expression evaluated so far as left child
# and the newly parsed term as right child.
new_node = Node(op_type, left=node, right=right_node)
# Update 'node' to be the root of the expression evaluated so far
node = new_node
return node
# --- Main Logic ---
# Build the AST from the input expression string
root = parse_expression()
# Check if parsing failed or did not consume the entire string
if parsing_failed or pos != len(expr_str):
# The problem statement guarantees valid input format, so this should ideally not happen.
# If it does, it indicates an issue, output -1.
print("-1")
sys.exit()
# Memoization dictionary for the DP computation (possible values for each node)
memo_possible = {}
# Dynamic Programming function (using memoized recursion) to compute possible values for each node
def compute_possible(node):
# Use the unique node ID as the key for memoization
node_id = node.id
if node_id in memo_possible:
return memo_possible[node_id] # Return cached result if available
# Initialize a boolean array to store possible values (indices 0 to M)
possible = [False] * (M + 1)
if node.type == 'num':
# Base case: For a number node, check if its value is within the valid range [0, M]
if 0 <= node.value <= M:
possible[node.value] = True # Mark this value as possible
elif node.type in ['$', '&']:
# Recursive case: For operator nodes
# Compute possible values for left and right children
possible_left = compute_possible(node.left)
possible_right = compute_possible(node.right)
# Iterate through all pairs of possible values from children
for v_left in range(M + 1):
if possible_left[v_left]: # If v_left is a possible value for the left child
for v_right in range(M + 1):
if possible_right[v_right]: # If v_right is a possible value for the right child
# Apply the operations corresponding to the node type ('$' or '&')
if node.type == '$':
# Try addition (+)
res_add = v_left + v_right
# Check if result is within the valid range [0, M]
if 0 <= res_add <= M: possible[res_add] = True
# Try subtraction (-)
res_sub = v_left - v_right
# Check if result is within the valid range [0, M]
if 0 <= res_sub <= M: possible[res_sub] = True
elif node.type == '&':
# Try multiplication (*)
res_mul = v_left * v_right
# Check if result is within the valid range [0, M]
if 0 <= res_mul <= M: possible[res_mul] = True
# Try integer division (//)
# Check for division by zero first
if v_right != 0:
res_div = v_left // v_right # Use integer division
# Check if result is within the valid range [0, M]
# Note: Since v_left >= 0 and v_right > 0, res_div >= 0 is guaranteed.
if 0 <= res_div <= M: possible[res_div] = True
# Store the computed possible values in the memoization cache before returning
memo_possible[node_id] = possible
return possible
# Compute the set of possible values for the root of the AST
root_possible = compute_possible(root)
# Check if the target answer 'ans' is among the possible values for the entire expression
if not root_possible[ans]:
# If 'ans' is not possible, print -1
print("-1")
else:
# If 'ans' is possible, reconstruct one valid assignment string
# Memoization dictionary for the reconstruction process
memo_reconstruct = {}
# Recursive function to reconstruct the expression string for a given node and target value
def reconstruct(node, target_value):
# Use a tuple (node ID, target value) as the key for memoization
state_key = (node.id, target_value)
if state_key in memo_reconstruct:
# Return cached result (could be the reconstructed string or None if failed)
return memo_reconstruct[state_key]
if node.type == 'num':
# Base case: If it's a number node, it must match the target value
if node.value == target_value:
return str(node.value) # Return the number as a string
else:
# This path is invalid (should not happen if logic is correct and called based on possible values)
return None
# Recursive case: Operator node
# Retrieve pre-computed possible values for children from memo_possible cache
possible_left = memo_possible[node.left.id]
possible_right = memo_possible[node.right.id]
# Iterate through possible value pairs from children to find one that yields the target_value
for v_left in range(M + 1):
if possible_left[v_left]:
for v_right in range(M + 1):
if possible_right[v_right]:
current_op_char = None # Stores the character '+', '-', '*', '/' for the reconstructed op
valid_op_found = False # Flag to indicate if a valid operation is found for this pair
# Check which operation(s) with v_left and v_right result in target_value
if node.type == '$':
# Check addition first
res_add = v_left + v_right
if res_add == target_value and 0 <= res_add <= M:
current_op_char = '+'
valid_op_found = True
# If addition didn't work, check subtraction
# The problem asks for any solution, so picking the first one found is fine.
if not valid_op_found:
res_sub = v_left - v_right
if res_sub == target_value and 0 <= res_sub <= M:
current_op_char = '-'
valid_op_found = True
elif node.type == '&':
# Check multiplication first
res_mul = v_left * v_right
if res_mul == target_value and 0 <= res_mul <= M:
current_op_char = '*'
valid_op_found = True
# If multiplication didn't work, check division
if not valid_op_found:
if v_right != 0: # Avoid division by zero
res_div = v_left // v_right
if res_div == target_value and 0 <= res_div <= M:
# Use '/' for output string as specified
current_op_char = '/'
valid_op_found = True
# If a valid operation was found for this pair (v_left, v_right)
if valid_op_found:
# Recursively reconstruct the strings for left and right children
left_str = reconstruct(node.left, v_left)
# If reconstruction for the left child failed, this path is invalid, try next pair
if left_str is None: continue
right_str = reconstruct(node.right, v_right)
# If reconstruction for the right child failed, this path is invalid, try next pair
if right_str is None: continue
# Both children successfully reconstructed. Combine them with the operator.
res_str = f"{left_str}{current_op_char}{right_str}"
# If the original subexpression was parenthesized, add parentheses back
if node.is_parenthesized:
res_str = f"({res_str})"
# Cache the successful reconstruction and return it
memo_reconstruct[state_key] = res_str
return res_str
# If the loops complete without finding a valid reconstruction for this (node, target_value)
memo_reconstruct[state_key] = None # Cache the failure (None)
return None
# Start the reconstruction process from the root node with the target answer 'ans'
final_expr = reconstruct(root, ans)
# Print the final reconstructed expression string.
# If final_expr is None (which ideally shouldn't happen if root_possible[ans] was true),
# print -1 as a fallback.
print(final_expr if final_expr is not None else "-1")