\textbf{Sistem Mühəndisi}#369

\textbf{Sistem Mühəndisi}

2 saniyə
64 meqabayt
Çox asan

Bob bacarıqlı sistem mühəndisidir və mütəmadi olaraq çətin problemlərlə üzləşir. İndi o, yeni bir problemi həll etməlidir: müxtəlif imkanlara malik serverlər dəstəsini fasiləsiz mənbələrdən gələn davamlı iş sorğularını emal etmək üçün idarə etməlidir; burada hər bir iş uzun müddət və ya qeyri-müəyyən müddət ərzində emal edilməlidir.

Bir sıra iş sorğuları gəlir, onların hər biri həmin işi emal edən serverlərin alt dəstini göstərir. Hər bir iş yalnız bir serverdə emal olunur və hər bir server yalnız bir işi emal edə bilər. Bob maksimum sayda işi serverlərə yerləşdirməlidir. Məsələn, əgər iş j_1 və j_2, və server s_1 və s_2 varsa və həm j_1, həm də j_2 yalnız s_1-də işləyə bilirsə, Bob yalnız bir işi yerləşdirə bilər. Ona kömək edə bilərsən?

Ümumi halda, iş var, ədədləri -dan n-1-ə qədərdir, server var, ədədləri -dən 2n-1-ə qədərdir və bir sıra iş sorğuları verilir. Tapşırıq maksimum neçə işin emal oluna biləcəyini tapmaqdan ibarətdir.

Proqram daxil olanları tekst faylından oxuyur (ən çoxu MB). Hər bir məlumat dəsti faylda müəyyən bir işlər dəstəsini göstərir. Məlumat dəsti əvvəlcə işlərin sayı (n \leq 10000), sonra isə hər bir iş üçün tələb olunan serverlərin siyahısı ilə davam edir, format belədir: job_number: (nr_servers) s_1 ...s_{nr\_servers} Proqram maksimum neçə işin emal oluna biləcəyini çıxış verir.

Daxil olan məlumatlarda istənilən sayda boşluq ola bilər. Daxil olan məlumat düzgündür və faylın sonu ilə bitir. Hər bir məlumat dəsti üçün nəticə standart çıxışa, sətirin əvvəlinə yazılır. Aşağıdakı cədvəldə nümunə giriş/çıxış göstərilmişdir. İki məlumat dəsti var. Birinci halda, işlərin sayı n=2-dir, nömrələri və -dir. İş üçün sorğu belədir: 0: (1) 2, yəni iş yalnız serverə, server -yə ehtiyac duyur. İş üçün də sorğu belədir: 1: (1) 2, yəni iş də yalnız bir serverə – server -yə ehtiyac duyur. Bu məlumat dəsti üçün nəticə maksimum yerləşdirilə bilən işlərin sayı olan -dir.

Nümunələr

Nümunə 1

Loading
Loading