Pizza dilimləri borclarının hesablanması#1336
Yuvada pizza böhranı! Hər yerdə boş pizza qutuları. Dörd tısbağa, sıfır dilim qalıb. Usta Splinter şagirdlərinə baxır və deyir: "Yəqin ki, pizzanı daha müdrik paylaşmağı öyrənmək vaxtı gəlib, oğullarım!"
Yaxşı, vəziyyət belədir. Leonardo, Mikelancelo, Donatello və Rafayel bütün həftə bir-birləri ilə pizza dilimləri mübadiləsi ediblər və indi heç kim xatırlamır kimin kimə nə qədər borclu olduğunu. Hamı bir-birinə borcludur, amma heç bir tısbağanın hamıya ödəmək üçün kifayət qədər dilimi yoxdur, hərçənd riyazi olaraq rəqəmlər uyğun gəlməlidir.
İcazə verin, şəkildə (a) pizza borcları vəziyyətini göstərim. Qrafik dörd tısbağanın (Leo, Mayki, Donni və Raf) bir-birinə neçə dilim borclu olduğunu göstərir. Məsələn, Leo Maykiyə 50 dilim borcludur, Mayki isə Leoya 150 dilim borcludur. (Bəli, belə olur - iki tısbağa eyni anda bir-birinə borclu ola bilər!) Hər şeyi həll etmək üçün ora-bura 380 pizza dilimi ötürməli olardılar.
Amma gözləyin! Bu qarışıqlığı öyrəndikdən sonra anladım ki, daha ağıllı üsul var. Biz pizzanı lazımsız köçürmələrə sərf edirik! Baxın:
Donni Rafa tam 30 dilim borcludur və Raf Leoya eyni 30 dilim borcludur. Bəs niyə vasitəçi lazımdır? Donni birbaşa Leoya ödəyə bilər və biz Rafı zəncirdən çıxarırıq!
Amma dayan - Leo artıq Donniyə 100 dilim borcludur. Deməli, əslində Leo Donniyə yalnız fərqi ödəməlidir: 70 dilim.
Eyni ideya Mayki və Leo ilə. Mayki Leoya 150 dilim borcludur, amma Leo Maykiyə 50 dilim borcludur. Xalis nəticə? Mayki Leoya yalnız 100 dilim ödəyir. İndi bizdə şəkil (b) var və yalnız 190 dilim lazımdır. Bu 200 dilim qənaət, yaxud 53%!
Amma daha da yaxşısını edə bilərik! Maykinin 100 dilimi Leoya verməsi və sonra Leonun dönüb 70 dilimi Donniyə verməsi əvəzinə, niyə Mayki 70 dilimi birbaşa Donniyə verməsin? Onda Mayki yalnız 30 dilimi Leoya verir. Şəkilə (c) baxın - bizə cəmi 120 dilim lazımdır! Bu 260 dilim azalma, yaxud 68%! Kovabunga!
Məndə kimin kimə borclu olduğu haqqında bütün məlumatlar var, amma lazımi pizzanı minimuma endirmək üçün optimal üsulu tapa bilmirəm. Bütün borcları ödəmək üçün lazım olan minimum dilim sayını tapan proqram yaza bilərsinizmi?
Proqramınız bir və ya bir neçə testdə yoxlanılacaq. Hər test N+1 sətir tutur, burada N - tısbağaların sayı (birinci sətirdə verilir). Növbəti N sətir N()N matrisi ehtiva edir, burada elementi tısbağasının tısbağasına neçə dilim borclu olduğunu göstərir (diaqonal sıfırdır, çünki heç kim özünə borclu deyil). Dəyərlər boşluqla ayrılır, bütün rəqəmlər 1000-dən kiçikdir. Giriş məlumatları bir 0 olan sətrlə bitir.
Hər test üçün çıxarın:
k. B A
burada k - test nömrəsi (1-dən başlayır), B - optimallaşdırmadan əvvəl ümumi dilim sayı, A - optimallaşdırmadan sonra ümumi dilim sayı.
Nümunə 1