結果
問題 |
No.2121 帰属関係と充足可能性
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:37:22 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,228 bytes |
コンパイル時間 | 195 ms |
コンパイル使用メモリ | 81,424 KB |
実行使用メモリ | 53,780 KB |
最終ジャッジ日時 | 2025-04-16 16:39:30 |
合計ジャッジ時間 | 3,048 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 WA * 2 |
ソースコード
from itertools import combinations def generate_vn(n): if n == 0: return [] prev = generate_vn(n-1) prev_list = list(prev) subsets = [] for mask in range(0, 1 << len(prev_list)): subset = [] for i in range(len(prev_list)): if mask & (1 << i): subset.append(prev_list[i]) subsets.append(frozenset(subset)) return subsets # Precompute V_0 to V_4 v = [] for i in range(5): vn = generate_vn(i) v.append(vn) # V_5 is not generated due to its size, so handle N=5 as a special case def main(): import sys input = sys.stdin.read().split() N = int(input[0]) A = list(map(int, input[1:7])) A0, A1, A2, A3, A4, A5 = A if N == 0: print("NO") return # Handle N >=5 as special case (cannot generate V_5) if N >= 5: print("NO") return required_vars = {A1, A3, A4, A5} # Check if required_vars need to be in V_{N-1} which might be empty if (N-1 >=0) and (len(v[N-1]) == 0) and (len(required_vars) > 0): print("NO") return # Determine possible values for each variable possible = [] for var in [0, 1, 2]: if var in required_vars: # Must be in V_{N-1} possible_var = v[N-1] if (N-1 >=0) else [] else: possible_var = v[N] possible.append(possible_var) # Iterate through all combinations for m0 in possible[0]: for m1 in possible[1]: for m2 in possible[2]: m = [m0, m1, m2] # Condition 1: m[A0] subset of m[A1] if not m[A0].issubset(m[A1]): continue # Condition 2: m[A1] in m[A2] if m[A1] not in m[A2]: continue # Condition 3: m[A3] in m[A2] if m[A3] not in m[A2]: continue # Condition 4: m[A4] in m[A2] if m[A4] not in m[A2]: continue # Condition 5: m[A5] in m[A0] if m[A5] in m[A0]: print("YES") return print("NO") if __name__ == "__main__": main()