#!/usr/bin/env python3 import sys import math import numpy as np #––– FORMAT OPERACJI ––– # Operacja sumy: "1 x y" (A_new = A_x ∪ A_y) # Operacja przecięcia: "2 x y" (A_new = A_x ∩ A_y) # Operacja negacji: "3 x" (A_new = A′_x, czyli dopełnienie A_x w [1,n]) # Globalna lista operacji oraz licznik następnego indeksu. ops = [] # lista napisów (str) opisujących operacje next_idx = None # kolejne indeksy dla nowych zbiorów def new_op(op_type, x, y=None): """ Rejestruje nową operację i zwraca indeks nowo utworzonego zbioru. op_type: "1" dla sumy, "2" dla przecięcia, "3" dla negacji. x, y: indeksy operandów (dla negacji tylko x). """ global next_idx, ops if op_type == "3": s = f"3 {x}" else: s = f"{op_type} {x} {y}" ops.append(s) cur = next_idx next_idx += 1 return cur def main(): global next_idx, ops data = sys.stdin.read().strip().split() if not data: return # Wczytujemy n oraz s (rozmiar docelowego zbioru B) n = int(data[0]) s = int(data[1]) B = list(map(int, data[2:2+s])) # elementy B – rosnąco, 1 ≤ b₁ < b₂ < … < b_s ≤ n # Jeśli B jest pełnym zbiorem (czyli B = {1,2,…,n}) to A1 = [1,n] już jest uniwersum. if s == n: print(0) return # Indeksy początkowych zbiorów A1, A2, …, An to 1,2,…,n. # Następnie operacje będą produkowały zbiory o indeksach n+1, n+2, … next_idx = n + 1 # Funkcja pomocnicza – dla danego v, chcemy "singleton" F(v) = A_v ∩ (complement (∪{ A_{k*v} for k=2..⌊n/v⌋ })) # Jeśli v > n/2, A_v = {v} już jest singleton. singleton = dict() # dla każdego v ∈ B zapisujemy indeks zbioru zawierającego {v} for v in B: if v > n//2: # Dla v > n/2 mamy A_v = {v} singleton[v] = v else: # Obliczamy listę mnożników: M = [2*v, 3*v, ..., ⌊n/v⌋*v] maxk = n // v if maxk < 2: # w teorii nie wystąpi, bo v ≤ n//2 zapewnia maxk ≥ 2 singleton[v] = v else: M = [k*v for k in range(2, maxk+1)] # Obliczamy U = ∪_{j in M} A_j. # Jeśli M ma tylko jeden element, U = A_{M[0]}, inaczej łączymy sumami. if len(M) == 1: U = M[0] else: # Rozpoczynamy od A_{M[0]} U = M[0] for j in M[1:]: U = new_op("1", U, j) # U jest sumą A_{2*v} ∪ A_{3*v} ∪ … ∪ A_{maxk*v}. # Obliczamy dopełnienie U: C = A′_U. C = new_op("3", U) # F(v) = A_v ∩ C. Fv = new_op("2", v, C) singleton[v] = Fv # Teraz chcemy złożyć zbiór B jako sumę (union) wszystkich F(v) dla v ∈ B. # Zbieramy indeksy wszystkich pojedynczych zbiorów list_singletons = [singleton[v] for v in B] if len(list_singletons) == 0: S = new_op("3", 1) # np. puste – ale s>=1 więc to nie powinno wystąpić elif len(list_singletons) == 1: S = list_singletons[0] else: # Łączymy sumą w sposób sekwencyjny (można też robić drzewo binarne, by zmniejszyć liczbę operacji, # ale tu wystarczy sekwencyjnie – łączymy po kolei) cur = list_singletons[0] for idx in list_singletons[1:]: cur = new_op("1", cur, idx) S = cur # S to indeks zbioru, który (przy poprawności konstrukcji) powinien być równy B. # Wypisujemy ciąg operacji – liczba operacji to len(ops). m_ops = len(ops) # Sprawdzamy limit – jeżeli operacji jest więcej niż 100000, wypisujemy (dla pewności) błąd. if m_ops > 100000: # Można zamiast tego wypisać dowolny poprawny ciąg – poniższy kod nie powinien się zdarzyć dla przykładowych testów. print("0") return out_lines = [str(m_ops)] out_lines.extend(ops) sys.stdout.write("\n".join(out_lines)) if __name__ == '__main__': main()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #!/usr/bin/env python3 import sys import math import numpy as np #––– FORMAT OPERACJI ––– # Operacja sumy: "1 x y" (A_new = A_x ∪ A_y) # Operacja przecięcia: "2 x y" (A_new = A_x ∩ A_y) # Operacja negacji: "3 x" (A_new = A′_x, czyli dopełnienie A_x w [1,n]) # Globalna lista operacji oraz licznik następnego indeksu. ops = [] # lista napisów (str) opisujących operacje next_idx = None # kolejne indeksy dla nowych zbiorów def new_op(op_type, x, y=None): """ Rejestruje nową operację i zwraca indeks nowo utworzonego zbioru. op_type: "1" dla sumy, "2" dla przecięcia, "3" dla negacji. x, y: indeksy operandów (dla negacji tylko x). """ global next_idx, ops if op_type == "3": s = f"3 {x}" else: s = f"{op_type} {x} {y}" ops.append(s) cur = next_idx next_idx += 1 return cur def main(): global next_idx, ops data = sys.stdin.read().strip().split() if not data: return # Wczytujemy n oraz s (rozmiar docelowego zbioru B) n = int(data[0]) s = int(data[1]) B = list(map(int, data[2:2+s])) # elementy B – rosnąco, 1 ≤ b₁ < b₂ < … < b_s ≤ n # Jeśli B jest pełnym zbiorem (czyli B = {1,2,…,n}) to A1 = [1,n] już jest uniwersum. if s == n: print(0) return # Indeksy początkowych zbiorów A1, A2, …, An to 1,2,…,n. # Następnie operacje będą produkowały zbiory o indeksach n+1, n+2, … next_idx = n + 1 # Funkcja pomocnicza – dla danego v, chcemy "singleton" F(v) = A_v ∩ (complement (∪{ A_{k*v} for k=2..⌊n/v⌋ })) # Jeśli v > n/2, A_v = {v} już jest singleton. singleton = dict() # dla każdego v ∈ B zapisujemy indeks zbioru zawierającego {v} for v in B: if v > n//2: # Dla v > n/2 mamy A_v = {v} singleton[v] = v else: # Obliczamy listę mnożników: M = [2*v, 3*v, ..., ⌊n/v⌋*v] maxk = n // v if maxk < 2: # w teorii nie wystąpi, bo v ≤ n//2 zapewnia maxk ≥ 2 singleton[v] = v else: M = [k*v for k in range(2, maxk+1)] # Obliczamy U = ∪_{j in M} A_j. # Jeśli M ma tylko jeden element, U = A_{M[0]}, inaczej łączymy sumami. if len(M) == 1: U = M[0] else: # Rozpoczynamy od A_{M[0]} U = M[0] for j in M[1:]: U = new_op("1", U, j) # U jest sumą A_{2*v} ∪ A_{3*v} ∪ … ∪ A_{maxk*v}. # Obliczamy dopełnienie U: C = A′_U. C = new_op("3", U) # F(v) = A_v ∩ C. Fv = new_op("2", v, C) singleton[v] = Fv # Teraz chcemy złożyć zbiór B jako sumę (union) wszystkich F(v) dla v ∈ B. # Zbieramy indeksy wszystkich pojedynczych zbiorów list_singletons = [singleton[v] for v in B] if len(list_singletons) == 0: S = new_op("3", 1) # np. puste – ale s>=1 więc to nie powinno wystąpić elif len(list_singletons) == 1: S = list_singletons[0] else: # Łączymy sumą w sposób sekwencyjny (można też robić drzewo binarne, by zmniejszyć liczbę operacji, # ale tu wystarczy sekwencyjnie – łączymy po kolei) cur = list_singletons[0] for idx in list_singletons[1:]: cur = new_op("1", cur, idx) S = cur # S to indeks zbioru, który (przy poprawności konstrukcji) powinien być równy B. # Wypisujemy ciąg operacji – liczba operacji to len(ops). m_ops = len(ops) # Sprawdzamy limit – jeżeli operacji jest więcej niż 100000, wypisujemy (dla pewności) błąd. if m_ops > 100000: # Można zamiast tego wypisać dowolny poprawny ciąg – poniższy kod nie powinien się zdarzyć dla przykładowych testów. print("0") return out_lines = [str(m_ops)] out_lines.extend(ops) sys.stdout.write("\n".join(out_lines)) if __name__ == '__main__': main() |