Mühafizəçi
Bluewater Təhlükəsizlik Şirkəti müştərilərinin qiymətli əşyalarını qorumaq üçün mühafizəçilər təmin edir. Şirkət müəyyən edib ki, müştərilər mühafizəçilərin qiymətli əşyaları görə biləcəyi yerlərdə yerləşdirilməsini və əşyaların yaxınlığında olmasını istəyirlər. Yuxarıda bir saytın planı göstərilib. Hələlik üç qara nöqtəni nəzərə almayın. Müxtəlif yerlər etiketlənib və dəyərlər təyin edilib. Məsələn, A nöqtəsi (0,8) koordinatlarında dəyəri 4 olan bir əşyanın yeridir. G kimi dəyəri 0 olan yerlərdə qiymətli əşya yoxdur. Düz xətlər dəhlizləri göstərir. Sadəlik üçün dəhlizlər eni 0 olan xətt seqmentləri kimi modelləşdirilir. Bir neçə dəhlizin kəsişmə nöqtəsində olan mühafizəçi hər dəhlizdəki əşyaları görə və beləliklə onları mühafizə edə bilər. Əgər Bluewater 3 mühafizəçi təmin etmək üçün müqavilə bağlasaydı, onları kiçik qara nöqtələrlə göstərilən mövqelərdə yerləşdirməyi seçə bilərdi. Artıq etiketlənmiş mövqedə olmayan mühafizəçi (15.5, 6) nöqtəsindədir. Mühafizəçilərin daha yüksək dəyərli əşyalara daha yaxın olma istəyini modelləşdirmək üçün Bluewater qiymətli əşyaya olan riski əşyanın dəyəri ilə əşyanı görə bilən mühafizəçiyə olan minimum məsafənin hasilinə bərabər hesablayır. Bir mühafizəçi küncün ətrafında olan bir əşyaya yaxın olsa belə, bu mühafizəçi əşyaya olan riski təsir etmir, çünki mühafizəçi küncün ətrafını görə bilmir. Göstərilən diaqramda əşyalara olan risklər A: 4x5=20, C: 4x2.5=10, D: 2x0=0, .... Ən böyük risklər H: 50x7.5=375 və I: 50x7.5=375 üçün olduğundan, hər hansı bir əşyaya olan maksimum risk 375-dir. Bu sayt planı ilə, 3 mühafizəçinin heç bir düzülüşü daha aşağı maksimum risk təmin etməzdi, beləliklə bu 3 mühafizəçinin düzülüşü maksimum riski minimallaşdırır. Bluewater hər hansı bir müştəriyə müəyyən bir sayt planı üçün müəyyən sayda mühafizəçi tələb etdikdə, minimallaşdırılmış maksimum riskin nə olacağını bildirmək istəyir.
Giriş verilənləri
Giriş bir xəttdə yalnız 0 olan bir sətirlə bitən birdən on altıya qədər məlumat dəstindən ibarət olacaq. Hər sətirdə məlumat boşluqla ayrılmış tokenlərdən ibarət olacaq.
Məlumat dəstinin ilk sətri p c g tam ədədlərini ehtiva edir, burada p göstərilən nöqtələrin sayıdır, c dəhlizlərin sayıdır və g yerləşdiriləcək mühafizəçilərin sayıdır. Məhdudiyyətlər 1< p < 12; 0 < c < 12; 0 < g < 5.
Daha sonra məlumat dəstində dörd tokendən ibarət p qrup gəlir, hər biri böyük hərf və üç qeyri-mənfi tam ədəd L x y v-dən ibarətdir, burada (x, y) nöqtəsi L etiketi ilə dəyəri v olan bir əşya ehtiva edir. Əgər p 6-dan çox deyilsə, bu qrupların hamısı bir sətirdə olacaq. Əgər p 6-dan çoxdursa, onda yeddinci və daha çox qruplar növbəti sətirdə olacaq. Etiketlər A-dan başlayan ardıcıl hərflər olacaq. Bütün rəqəmlər 1000-dən kiçikdir. Hər bir nöqtə unikaldır. v üçün 0 dəyəri orada qiymətli əşya olmadığını göstərir. Qiymətli əşyalar olan yerlərin sayı mühafizəçilərin sayından az olmayacaq.
Məlumat dəstinin son sətri hər dəhliz üçün bir ədəd olmaqla c hərfli sətirlərdən ibarətdir. Hər dəhliz üçün hərflər dəhliz boyunca nöqtələrin etiketləridir, xətt seqmentinin bir ucundan digərinə, bütün kəsişmə nöqtələrini və qiymətli əşyaların olduğu bütün yerləri əhatə edir. Məlumat dəstində verilən hər bir nöqtə ən azı bir dəhlizdə yerləşəcək.
Çıxış verilənləri
Hər məlumat dəsti üçün bir çıxış sətri var. Əgər bütün qiymətliləri görə bilmək üçün kifayət qədər mühafizəçi təmin edilmirsə, sətir "çox az mühafizəçi" olacaq. Əks halda, sətir maksimum "risk"in g mühafizəçinin bütün yerləşdirilmələri üzərində minimum dəyəri olan r-i iki onluq yerə qədər yuvarlaqlaşdırılmış imzasız bir rəqəm olacaq.