結果

問題 No.3024 全単射的
ユーザー lam6er
提出日時 2025-03-20 20:32:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,339 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 273,632 KB
最終ジャッジ日時 2025-03-20 20:33:23
合計ジャッジ時間 9,366 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 10 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

from fractions import Fraction
import sys

memo = {}

def generate_results(nums):
    nums_sorted = sorted(nums, key=lambda x: x)
    key = tuple(nums_sorted)
    if key in memo:
        return memo[key]
    if len(nums) == 1:
        res = {nums[0]}
        memo[key] = res
        return res
    res = set()
    n = len(nums)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            x = nums[i]
            y = nums[j]
            remaining = [nums[k] for k in range(n) if k != i and k != j]
            # Addition
            add = x + y
            # Subtraction in both orders
            sub_xy = x - y
            sub_yx = y - x
            # Multiplication
            mul = x * y
            # Division
            div_xy = div_yx = None
            if y != Fraction(0):
                div_xy = x / y
            if x != Fraction(0):
                div_yx = y / x
            # Collect all possible results from this pair
            current_results = [add, sub_xy, sub_yx, mul]
            if y != Fraction(0):
                current_results.append(div_xy)
            if x != Fraction(0):
                current_results.append(div_yx)
            for result in current_results:
                new_nums = remaining.copy()
                new_nums.append(result)
                sub_res = generate_results(new_nums)
                res.update(sub_res)
    memo[key] = res
    return res

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    numbers = list(map(int, input[1:n+1]))
    if n == 0:
        print("NO")
        return
    fractions = [Fraction(num) for num in numbers]
    first = fractions[0]
    others = fractions[1:]
    found = False
    total_comb = 1 << (n - 1)
    for mask in range(total_comb):
        t_count = (n - 1) - bin(mask).count('1')
        if t_count < 1:
            continue
        s_list = [first]
        t_list = []
        for k in range(n-1):
            if mask & (1 << k):
                s_list.append(others[k])
            else:
                t_list.append(others[k])
        s_res = generate_results(s_list)
        t_res = generate_results(t_list)
        if len(s_res & t_res) > 0:
            found = True
            break
    print("YES" if found else "NO")

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