HUNTER×HUNTER#10896
Məşhur "HUNTERxHUNTER" adlı manqanın birinci hissasinda Gon adlı asas qahraman və onun dostları ovçu imtahanında iştirak edirlər. İmtahanın dördüncü fazasında hər iştirakçıya üzərində və N-1 aralığında yerləşən unikal nömrə olan bac verilir. Həmçinin, hər birinin üzərində və N-1 aralığında yerləşən unikal nömrə yazılan sayda kağız parçaları bir qaba atılır. Hər iştirakçı qabdan kağız parçası götürür (və geri qaytarmır); iştirakçının götürdüyü kağız parçası onun hədəfinin T_i nömrəsini əks etdirir. Məlumdur ki, heç bir iştirakçı öz nömrəsinin qabdan götürməyib, yəni hər üçün T_i \neq i.
Namizəd ovçular Zevil adasına gətiriləndən bir həftə sonra orada bir-birindən baclərini oğurlaya bilərlər. Həftənin sonunda imtahanın dördüncü fazası bitir və kimin hansı baca sahib olduğu qeyd edilir. -ci iştirakçının qazandığı xal onun topladığı baclərin verə biləcəyi balın cəminə bərabərdir. və T_i nömrəli bacların hər biri sahibinə bal qazandırır, halbuki bütün digər baclər bal qazandıracaq. Ən azı bal qazanan iştirakçı fazanı müvəffəqiyyətlə keçir, qalanları isə keçə bilmir.
Aydındır ki, hər kəs növbəti fazaya keçə bilməz. Səni mümkün olan ən yaxşı nəticə maraqlandırır. Çünki sən bəzi personajlara daha çox pərəstiş edirsən. Daha dəqiq desək, personajına sən L_i miqdarında pərəstiş edirsən (müəyyən ölçü vahidində). Sən bütün L_m-lərin, hansındakı ən azı bal qazanan iştirakçıların nömrələrini əks etdirir, maksimum mümkün olan cəmini bilmək istəyirsən.
Məsələ ondadır ki, iştirakçıların sayı çoxdur və nəticə olaraq çoxlu mümkün kombinasiyalar mövcuddur. Buna görə ən yaxşı kombinasiyanı əl ilə hesablamaq sənə olduqca çətindir. Xoşbəxtlikdən sən 21-ci əsrdə yaşayırsan və qarşında müasir kompüter var. Sən qərara gəlirsən ki, ən yaxşı çıxış yolu hunterxhunter proqramı yaratmaqdır, hansıki sənə verilən giriş məlumatları ilə maksimum mümkün olan cəmi tapacaq.
Standart girişin birinci sətrində iki müsbət tam ədəd: və müvafiq olaraq iştirakçıların sayı və iştirakçının öz bacı ilə onun hədəfinin bacının ona qazandırdığı xal verilir. Növbəti sıranın hər birində mənfi olmayan iki tam ədəd: T_i və L_i müvafiq olaraq -ci iştirakçının hədəfinin nömrəsi və sənin iştirakçıya olan pərəstişinin miqdarı verilir.
Standart çıxışda yeganə sətirdə mənfi olmayan bir tam ədəd: ən azı bal qazanan iştirakçılara mümkün olan maksimum cəmi pərəstişini ver.
Nümunə 1
Nümunə 2
Nümunə 1-in izahı
Müvəffəqiyyətli iştirakçılar 1, 4 və 6-dır. Mümkün olan bir həll: iştirakçı nömrə 1, 1 və 6 nömrəli baclara sahib olur, iştirakçı nömrə 4 — 0, 4 və 7, iştirakçı nömrə 6 isə 2, 3 və 5. Cəm bərabərdir L_1 + L_4 + L_6 = 111 + 105 + 108 = 324.
Verilən alt tapsırığın balını əldə etmək üçün, sənin həllin həmin alt tapsırıq üçün nəzərdə tutulmuş bütün testləri keçməlidir. Alt tapsırıqlar aşağıdakılardır:
Alt tapsırıq | Bal | N | Əlavə məhdudiyyətlər |
1 | 10 | 10 | Yoxdur |
2 | 15 | 700 | T_{P_j} = P_{(j+1) \mod N} və L_{P_{N-1}} = 0 |
3 | 15 | 10^4 | T_{P_j} = P_{(j+1) \mod N} və L_{P_{N-1}} = 0 |
4 | 10 | 700 | T_{P_j} = P_{(j+1) \mod N} |
5 | 10 | 10^4 | T_{P_j} = P_{(j+1) \mod N} |
6 | 20 | 700 | Yoxdur |
7 | 20 | 10^4 | Yoxdur |
Burada , və N-1 aralığında olan ədədlərin ixtiyari permutasiyasıdır, hardakı P_0 = 0. Qeyd: (j+1) \mod N, (j+1)-in -ə bölünməsindən alınan qalıq deməkdir.
Məhdudiyyətlər: