Şirkət Təşkilatı

Bir neçə il əvvəl bir şirkət yaratdınız və xoşbəxtlikdən bu, çox uğurlu alınıb. Şirkət böyüdükcə işçiləri daha səliqəli idarə etmək üçün qruplar qurmağa və işçiləri bu qruplara bölüşdürməyə qərar verdiniz.

İndi siz $n$ qrup yaratmağı planlaşdırırsınız, hər biri şirkətdə bir layihəyə uyğundur. Bəzən bu qrupların üzvlüyü ilə əlaqədar məhdudiyyətlər var. Məsələn: - Bir qrup başqa bir qrupun alt dəsti olmalıdır, çünki o, yalnız daha böyük qrupun təcrübəli üzvlərindən ibarətdir - İki qrupun üzvləri tam eyni olmalıdır, çünki layihələri sıx bağlıdır - İki qrupun üzvləri tam eyni olmamalıdır ki, korrupsiyanın qarşısı alınsın - İki qrupun heç bir ortaq üzvü olmamalıdır, təhlükəsizlik səbəbi ilə - İki qrup arasında əməkdaşlığı artırmaq üçün ortaq ən azı bir üzv olmalıdır

Güman edək ki, X_i (i = 1, \ldots, n) — $i$-ci qrupa aid işçilərin çoxluğudur. Bu tip beş məhdudiyyət var:

1. X_i \subseteq X_j 2. X_i = X_j 3. X_i \neq X_j 4. X_i \cap X_j = \varnothing 5. X_i \cap X_j \neq \varnothing

Çünki məhdudiyyətlər uyğunluq yoxlanılmadan verilib, onları eyni anda təmin etmək qeyri-mümkün ola bilər. Məhdudiyyətlər prioritetə görə düzülür. Tapşırığınız — başlanğıcdan ən uzun uyğunluq təmin olunan prefiksi seçməkdir.

İşçilərin qabiliyyətini nəzərə almağınız tələb olunmur. İstədiyiniz işçini istənilən qrupa əlavə edə və hətta işçisiz qrup yarada bilərsiniz. Məhdudiyyətlərin daha çoxunu təmin etmək üçün istənilən sayda işçi əlavə edə və ya çıxara bilərsiniz.

Məsələn, aşağıda ilk nümunə girişdə olduğu kimi prioritetlə beş məhdudiyyət üç qrup üçün verilib:

- X_2 \subseteq X_1 - X_3 \subseteq X_2 - X_1 \subseteq X_3 - X_1 \neq X_3 - X_3 \subseteq X_1

X_1, X_2 və X_3-ə bir cür işçi bölüşdürmək ilk üç məhdudiyyəti təmin edir. Amma ilk dörd prioritetə malik məhdudiyyəti eyni anda təmin etmək mümkün deyil. İlk üç məhdudiyyət və beşinci eyni anda təmin olunsa da, cavab üçdür.