結果

問題 No.3024 全単射的
ユーザー lam6er
提出日時 2025-04-15 22:10:46
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,224 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 88,692 KB
最終ジャッジ日時 2025-04-15 22:12:10
合計ジャッジ時間 3,872 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from fractions import Fraction
from functools import lru_cache

sys.setrecursionlimit(1 << 25)

def main():
    n = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A_frac = [Fraction(x) for x in A]

    for mask in range(1, (1 << n) - 1):
        comp_mask = ((1 << n) - 1) ^ mask
        if mask > comp_mask:
            continue  # Skip to avoid duplicate processing

        S = []
        T = []
        for i in range(n):
            if (mask >> i) & 1:
                S.append(A_frac[i])
            else:
                T.append(A_frac[i])

        S_sorted = tuple(sorted(S))
        results_S = generate_results(S_sorted)
        if not results_S:
            continue

        T_sorted = tuple(sorted(T))
        results_T = generate_results(T_sorted)
        if not results_T:
            continue

        # Check for intersection
        if not results_S.isdisjoint(results_T):
            print("YES")
            return

    print("NO")

@lru_cache(maxsize=None)
def generate_results(nums_sorted):
    if len(nums_sorted) == 1:
        return frozenset([nums_sorted[0]])

    results = set()

    for i in range(len(nums_sorted)):
        for j in range(i + 1, len(nums_sorted)):
            a = nums_sorted[i]
            b = nums_sorted[j]

            # Create remaining list by removing i and j
            remaining = list(nums_sorted)
            del remaining[j]
            del remaining[i]

            # Calculate all possible operations
            add_res = a + b
            mul_res = a * b
            sub_res1 = a - b
            sub_res2 = b - a
            div_res1 = a / b if b != 0 else None
            div_res2 = b / a if a != 0 else None

            # Process each possible result
            for new_num in [add_res, mul_res, sub_res1, sub_res2, div_res1, div_res2]:
                if new_num is None:
                    continue

                new_remaining = remaining + [new_num]
                new_remaining_sorted = tuple(sorted(new_remaining))
                sub_results = generate_results(new_remaining_sorted)
                results.update(sub_results)

    return frozenset(results)

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