Mühafizəçi#3025
Bluewater Security Company dəyərli əşyaları olan müştərilər üçün mühafizəçilər təmin edir. Bluewater müəyyən edib ki, müştərilər belə istəyirlər ki, mühafizəçilər yalnız başlarını çevirərək bütün dəyərli əşyaları görə bilsinlər, həmçinin mühafizəçilərin xüsusilə dəyərli əşyaların yanında olmasına üstünlük verirlər. Yuxarıda nümunəvi ərazi planı göstərilib. Hələlik üç qara nöqtəyə məhəl qoymayın. Müxtəlif məkanlar işarələnib və dəyər təyin edilib. Məsələn, koordinatında yerləşən A nöqtəsində yerləşən əşyanın dəyəri -dür. G kimi dəyəri göstərilən yerlərdə dəyərli əşya yoxdur. Düz xətlər koridorları göstərir. Sadələşdirmə üçün, koridorlar sıfır enli xətt parçası kimi modelləşdirilir. Bir neçə koridorun kəsişdiyi nöqtədə olan mühafizəçi həmin koridorlardakı əşyaları görə və qoruya bilər. Əgər Bluewater 3 mühafizəçi ilə təmin edilməyə tapsırılsaydı, onları kiçik qara nöqtələrlə göstərilən mövqelərdə yerləşdirə bilərdilər. Əvvəlcədən işarələnməmiş mövqedə olan mühafizəçi koordinatındadır. Daha dəyərli əşyaların yaxınlığında mühafizəçilərin dayanması arzusunu modelləşdirmək üçün, Bluewater dəyərli bir əşyaya olan riski həmin əşyanın dəyərinin, onu görə bilən ən yaxın mühafizəçiyə məsafəsi ilə hasilinə bərabər hesablayır. Əgər bir mühafizəçi bir əşyaya yaxın olsa da, o əşya bir bucaq arxasındadırsa, bu mühafizəçi həmin əşya üçün riski azaltmır, çünki o əşyanı görə bilmir. Göstərilən diaqramda əşyalar üçün risklər aşağıdakı kimidir: A: 4\times5=20, C: 4\times2.5=10, D: 2\times0=0, .... Ən böyük risklər H: 50\times7.5=375 və I: 50\times7.5=375 üçün düşür, beləliklə, istənilən əşyaya olan maksimum risk olur. Bu ərazi planında 3 mühafizəçi üçün heç bir başqa düzülüş daha kiçik maksimum risk vermir, yəni bu yerləşdirmə maksimum riski minimallaşdırır. Bluewater istənilən ərazi planı və istənilən sayda mühafizəçi üçün müştəriyə minimallaşdırılmış maksimum risk dəyərini demək istəyir.
Giriş bir ilə on altı arasında məlumat dəstindən ibarət olacaq, arxasınca yalnız olan sətr gələcək. Hər sətrdə verilənlər boşluqla ayrılmış tokenlərdən ibarət olacaq.
Hər datasetin birinci sətrində üç tam ədəd — veriləcək; burada — verilmiş nöqtələrin sayı, — koridorların sayı, — yerləşdiriləcək mühafizəçilərin sayıdır. Məhdudiyyətlər: 1 < p < 12, 0 < c < 12, 0 < g < 5.
Növbəti sətrlərdə cəmi sayda dörd tokenlik qrup olacaq, hər biri böyük hərf və üç qeyri-mənfi tam ədəddən ( ) ibarət: koordinatında, etiketi olan nöqtədə dəyəri olan əşya yerləşir. Əgər p \leq 6-dırsa, bu qrupların hamısı bir sətrdə olacaq. p > 6 olduqda, yeddinci və sonrakı qruplar növbəti sətrdə veriləcək. Etiketlər ardıcıl böyük hərflərdən A ilə başlayacaq. Bütün ədədlər -dən kiçikdir. Hər bir nöqtə unikaldır. v=0 olduğu halda, həmin nöqtədə dəyərli əşya yoxdur. Dəyərli əşyası olan yerlərin sayı mühafizəçilərin sayından az olmayacaq.
Datasetin sonuncu sətrində ədəd hərf ardıcıllığı veriləcək, hər biri bir koridora aiddir. Hər koridor üçün, həmin ardıcıllıqda hərflər koridordakı nöqtələrin etiketləri olacaq və xətt parçası boyunca başlanğıcdan sona doğru nöqtələrin sırasını göstərəcək. Buraya hər iki son nöqtə, bütün digər koridorlarla kəsişmə nöqtələri və dəyərli əşyası olan bütün nöqtələr daxildir. Datasetdə verilən nöqtələrin hər biri ən azı bir koridorda olacaq.
Hər bir dataset üçün bir sətrlik çıxış olmalıdır. Əgər bütün dəyərli əşyaları qoruya bilmək üçün kifayət qədər mühafizəçi yoxdursa, sətrdə **too few guards** yazılmalıdır. Əks halda, sətrdə işarəsiz ədədi verilməli, burada — maksimum riski minimallaşdıran bütün mühafizəçi yerləşdirmələri arasında ən kiçik maksimum risktir və iki onluqdan sonrakı rəqəmə qədər yuvarlaqlaşdırılmış şəkildə verilir.
Nümunə 1