結果

問題 No.3024 全単射的
ユーザー qwewe
提出日時 2025-05-14 13:16:18
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,340 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 65,792 KB
最終ジャッジ日時 2025-05-14 13:17:46
合計ジャッジ時間 3,165 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import itertools
from math import isclose

# Epsilon for floating-point comparison
EPS = 1e-9

# Memoization dictionary: maps tuple(sorted_numbers) -> set(possible_values)
memo = {}

def get_possible_values(nums):
    """
    Recursively calculates all possible values obtainable from the tuple 'nums'
    using +, -, *, /. Uses memoization.
    Input: tuple of numbers.
    Output: set of possible float values.
    """
    # Ensure canonical representation for memoization key
    # Convert to tuple and sort if not already done (should be done before calling usually)
    # Here we assume the input 'nums' itself will be used as key directly or indirectly
    # after sorting within the caller or callee. Let's sort here for safety.
    
    # Convert potential ints to floats early
    nums_float = tuple(float(x) for x in nums)
    
    # Sort for canonical memoization key
    key = tuple(sorted(nums_float))

    if key in memo:
        return memo[key]

    n = len(key)
    if n == 1:
        return {key[0]}

    results = set()

    # Split the 'key' tuple into two non-empty sub-tuples
    # Iterate through possible sizes of the first subset (from 1 to n-1)
    for i in range(1, n):
        # Generate combinations of indices for the first subset
        for indices1 in itertools.combinations(range(n), i):
            sub1 = tuple(key[j] for j in indices1)
            sub2 = tuple(key[j] for j in range(n) if j not in indices1)

            # Recursively get values for sub-problems
            # The recursive call will handle sorting and memoization for sub-problems
            values1 = get_possible_values(sub1)
            values2 = get_possible_values(sub2)

            # Combine results from sub-problems
            for v1 in values1:
                for v2 in values2:
                    results.add(v1 + v2)
                    results.add(v1 - v2)
                    results.add(v2 - v1)
                    results.add(v1 * v2)
                    if not isclose(v2, 0.0, abs_tol=EPS):
                        results.add(v1 / v2)
                    if not isclose(v1, 0.0, abs_tol=EPS):
                         results.add(v2 / v1)

    memo[key] = results
    return results

# --- Main Execution ---

# Read input
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
all_nums = tuple(A)

found_equation = False

# Iterate through all possible ways to partition A into two non-empty subsets
# We only need to check partitions where the first set has size 1 to N//2
# because partitioning into (Set1, Set2) is equivalent to (Set2, Set1).
for i in range(1, N // 2 + 1):
    # Generate all subsets (indices) of size i for the first part (left side)
    for left_indices in itertools.combinations(range(N), i):
        
        left_set = tuple(all_nums[k] for k in left_indices)
        right_set = tuple(all_nums[k] for k in range(N) if k not in left_indices)

        # Calculate possible values for both sets
        # The function get_possible_values handles memoization internally
        # based on the sorted tuple of numbers.
        
        # Clear memoization for each top-level partition?
        # No, memoization should persist across partitions as subsets might overlap.
        
        possible_left_values = get_possible_values(left_set)
        possible_right_values = get_possible_values(right_set)

        # Check if there's any common value (within epsilon)
        # Optimization: Check if intersection is non-empty first for exact matches
        # if not possible_left_values.isdisjoint(possible_right_values):
        #    found_equation = True
        #    break
            
        # Check with tolerance for floats
        match_found_in_partition = False
        for val_l in possible_left_values:
            for val_r in possible_right_values:
                if isclose(val_l, val_r, abs_tol=EPS):
                    match_found_in_partition = True
                    break
            if match_found_in_partition:
                break
        
        if match_found_in_partition:
            found_equation = True
            break # Break from the inner loop (combinations)

    if found_equation:
        break # Break from the outer loop (sizes i)


# Print the result
if found_equation:
    print("YES")
else:
    print("NO")
0