結果

問題 No.3024 全単射的
ユーザー lam6er
提出日時 2025-03-31 17:38:33
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,309 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 89,388 KB
最終ジャッジ日時 2025-03-31 17:39:19
合計ジャッジ時間 4,762 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations
from fractions import Fraction

def main():
    n = int(sys.stdin.readline())
    input_numbers = list(map(int, sys.stdin.readline().split()))
    numbers = [Fraction(num) for num in input_numbers]
    memo = {}

    def generate(nums):
        sorted_nums = tuple(sorted(nums))
        if sorted_nums in memo:
            return memo[sorted_nums]
        if len(nums) == 1:
            result = {nums[0]}
            memo[sorted_nums] = result
            return result
        possible = set()
        length = len(nums)
        for i in range(length):
            for j in range(length):
                if i == j:
                    continue
                a = nums[i]
                b = nums[j]
                remaining = []
                for k in range(length):
                    if k != i and k != j:
                        remaining.append(nums[k])
                # Perform all operations
                # Addition
                add = a + b
                possible.update(generate(remaining + [add]))
                # Subtraction a - b
                sub_ab = a - b
                possible.update(generate(remaining + [sub_ab]))
                # Subtraction b - a
                sub_ba = b - a
                possible.update(generate(remaining + [sub_ba]))
                # Multiplication
                mul = a * b
                possible.update(generate(remaining + [mul]))
                # Division a / b
                if b != Fraction(0):
                    div_ab = a / b
                    possible.update(generate(remaining + [div_ab]))
                # Division b / a
                if a != Fraction(0):
                    div_ba = b / a
                    possible.update(generate(remaining + [div_ba]))
        memo[sorted_nums] = possible
        return possible

    for split_size in range(1, (n // 2) + 1):
        for s_combination in combinations(numbers, split_size):
            s = list(s_combination)
            t_set = set(numbers) - set(s_combination)
            t = list(t_set)
            possible_s = generate(s)
            possible_t = generate(t)
            if possible_s & possible_t:
                print("YES")
                return
    print("NO")

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