Kimyəvi Maddələrin Monitorinqi
Viktor Alberta Chemicals Monitoring (ACM) şirkətində çalışır. ACM, Alberta'da neft qumu və digər sənayelərdə istifadə olunan kimyəvi maddələrlə bağlı xam ətraf mühit məlumatlarını təhlil edir və ətraf mühit nəzarətçiləri üçün hesabatlar hazırlayır.
Viktor ACM-də çox prosessorlu klasterin idarə olunmasına cavabdehdir. Hər bir prosessor xüsusi məqsədli çıxış yaratma vahidinə (OGU) bağlıdır. Bu klaster sahə sensorlarından bir neçə xam məlumat axını alır və hər bir axını bir prosessora təyin edir. Hər bir prosessor bir məlumat axını üzərində real vaxt emalı aparır və onun bitməsindən dərhal sonra OGU-dan istifadə edərək hesabat hazırlayır.
Hər bir axının başlanğıc vaxtı s, müddəti d və prioriteti p var. Bu axın [s, s + d) intervalında (sağ açıq interval) aktivdir. Hər bir axının hesabatı onun bitməsindən dərhal sonra hazırlanmalıdır; əks halda, faydasız olacaq. OGU hesabatı çox sürətlə yaradır, buna görə də OGU-nun bu hesabatı dərhal hazırladığını qəbul edə bilərsiniz.
Keçmişdə, hər hansı bir anda, məlumat axınlarının sayı prosessorların və OGU-ların sayından çox deyildi. Beləliklə, Viktor bütün məlumat axınlarını emal edə bilirdi. Təəssüf ki, son zamanlarda şübhəli bir enerji artımında bütün OGU-lar yanıb. Viktor digər OGU-ların hissələrindən istifadə edərək bir OGU-nu xilas edə bildi. İndi o, bütün məlumat axınları üçün hesabat hazırlaya bilmir və onlara təyin olunan prioritetlərə əsasən onların bir alt qrupunu seçməlidir. Bu OGU-ya giriş üçün Viktor klaster arxitekturasını aşağıdakı kimi yenidən qurdu. Bir axın başladıqda, sistem onu qəbul edir və ya rədd edir. Əgər bir axını qəbul edərsə, bu axına təyin edilmiş prosessorun unikal identifikatoru stekə itələnir. Yalnız stekin üstündə identifikatoru olan bir prosessor OGU-dan istifadə edərək hesabatını hazırlaya bilər. Hesabat hazırlandıqdan sonra prosessor identifikatoru stekdən çıxarılır. Qeyd etmək lazımdır ki, əgər bəzi axınlar eyni vaxtda başlayırsa, o, onların prosessor identifikatorunu istədiyi sırada itələyə bilər. İndi Viktor sizdən bu tək OGU ilə hesabatları hazırlana biləcək axınların bir alt qrupunu seçməkdə kömək istəyir. Seçilmiş alt qrupdakı axınların ümumi prioriteti maksimum olmalıdır.
Giriş verilənləri
Giriş bir testdən ibarətdir. Birinci sətir tam ədəd n ehtiva edir, burada n (1 ≤ n ≤ 5000) məlumat axınlarının sayıdır. Növbəti n sətirin hər biri bir məlumat axınını təsvir edən üç tam ədəd s_i, d_i, p_i (1 ≤ s_i, d_i ≤ 10^9, 0 ≤ p_i ≤ 100000) ehtiva edir, burada s_i onun başlanğıc vaxtı, d_i axının müddəti və p_i onun prioritetidir. Qeyd edək ki, klasterdə ən azı 5000 prosessor var.
Çıxış verilənləri
Yuxarıda təsvir edilən arxitektura ilə tək OGU istifadə edərək hesabatları hazırlana biləcək axınların alt qrupunun maksimum ümumi prioritetini göstərin.