結果

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

ソースコード

diff # 

import sys
from itertools import combinations
from fractions import Fraction

sys.setrecursionlimit(1 << 25)

def main():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    
    memo = {}
    
    def compute_results(nums):
        key = tuple(sorted(nums))
        if key in memo:
            return memo[key]
        if len(nums) == 1:
            res = {Fraction(nums[0])}
            memo[key] = res
            return res
        results = set()
        for i in range(1, len(nums)):
            for left in combinations(nums, i):
                left = list(left)
                right = [num for num in nums if num not in left]
                left_res = compute_results(left)
                right_res = compute_results(right)
                for l in left_res:
                    for r in right_res:
                        results.add(l + r)
                        results.add(l - r)
                        results.add(l * r)
                        if r != 0:
                            results.add(l / r)
                        results.add(r - l)
                        if l != 0:
                            results.add(r / l)
        memo[key] = results
        return results
    
    first = A[0]
    full_mask = (1 << N) - 1
    for mask in range(1, full_mask):
        if not (mask & 1):
            continue
        S = []
        T = []
        for i in range(N):
            if (mask >> i) & 1:
                S.append(A[i])
            else:
                T.append(A[i])
        if not S or not T:
            continue
        s_res = compute_results(tuple(S))
        t_res = compute_results(tuple(T))
        s_floats = set(float(x) for x in s_res)
        t_floats = set(float(x) for x in t_res)
        if s_floats & t_floats:
            print("YES")
            return
    print("NO")

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