Sistem Mühəndisi
Bob bacarıqlı bir sistem mühəndisidir və daim çətin problemlərlə qarşılaşır. Hazırda o, uzun müddət və ya qeyri-müəyyən müddət ərzində işlənməsi lazım olan iş tələblərini davamlı mənbələrdən emal etmək üçün müxtəlif imkanlara malik serverlər dəstini idarə etməlidir. Davamlı iş tələblərinin ardıcıllığı, onların tələblərini yerinə yetirə bilən serverlərin alt qrupunu göstərir. Hər bir iş yalnız bir serverdə işlənir və hər bir server yalnız bir işi emal edə bilər. Bob serverlərdə maksimum sayda işi planlaşdırmalıdır. Məsələn, əgər 2 iş j1, j2 və 2 server s1, s2 varsa, j1 işi s1 serverini tələb edir və j2 işi də s1 serverini tələb edir. Bu halda Bob yalnız bir işi planlaşdıra bilər. Ona kömək edə bilərsinizmi?
Ümumi halda, 0-dan n-1-ə qədər nömrələnmiş n iş, n-dən 2*n-1-ə qədər nömrələnmiş n server və iş tələblərinin ardıcıllığı var. Problem maksimum sayda işlənə bilən işlərin tapılmasını tələb edir.
Proqramın girişi bir mətn faylından (ən çox 1 MB) alınır. Fayldakı hər bir məlumat dəsti müəyyən bir iş dəstini təmsil edir. Məlumat dəsti işlərin sayı n (n <= 10000) ilə başlayır, sonra hər bir iş üçün tələb olunan serverlərin siyahısı gəlir, formatda: iş_nömrəsi: (server_sayı) s_1 … s_{server_sayı} Proqram işlənə bilən maksimum işlərin sayını çap edir.
Girişdə boşluqlar sərbəst şəkildə ola bilər. Giriş məlumatları doğrudur və faylın sonu ilə bitir. Hər bir məlumat dəsti üçün proqram nəticəni standart çıxışa sətirin əvvəlindən çap edir. Aşağıdakı cədvəldə giriş/çıxış nümunəsi var. İki məlumat dəsti var. Birinci halda, işlərin sayı n 2-dir, 0 və 1 nömrələnmişdir. 0 işinin tələblərinin ardıcıllığı: 0: (1) 2, yəni 0 işi 1 server tələb edir, 2 nömrəli server. 1 işinin tələblərinin ardıcıllığı: 1: (1) 2, yəni 1 işi 1 server tələb edir, 2 nömrəli server. Məlumat dəsti üçün nəticə planlaşdırılmış maksimum işlərin uzunluğudur, 1.