İnək ləzzətləri#8667
Küllər daha bir əlamətdar ayda rekord miqdarda süd istehsalını qeyd etdilər və hər biri xüsusi bir hədiyyə qazandı. Küllər hədiyyələrini gözləyərkən düzbucaqlı w * h ölçüsündə bir sahəni tamamilə doldurdular.
Hər bir külün unikal dəyəri F[rc] (1 ≤ F[rc] ≤ 1000000) var ki, bu da onun ümumi süd istehsalını göstərir. Fermer Con hesab edir ki, hədiyyələrin paylanmasında ədalətli olmaq üçün yüksək məhsuldarlığa malik külləri əvvəlcə mükafatlandırmaq lazımdır. O, düzbucaqlı sahəni sıra ilə keçməyi planlaşdırır, hədiyyələri sıra 1-dən başlayaraq, sonra sıra 2-dən və s. paylamağa başlayacaq.
Fermer Con hesab edir ki, hədiyyələrin paylanmasında ədalətli olmaq üçün yüksək məhsuldarlığa malik külləri əvvəlcə mükafatlandırmaq lazımdır. O, düzbucaqlı sahəni sıra ilə soldan sağa keçməyi planlaşdırır, hədiyyələri küllərə bu ardıcıllıqla paylayacaq.
O, küllərdən özlərini elə təşkil etmələrini xahiş etdi ki, yüksək məhsuldarlığa malik küllər əvvəlcə mükafatlandırılsın. Küllər, lakin, təşkilatçılıqda o qədər də yaxşı deyillər. Onlar öz formalaşmalarında iki sıranı və ya iki sütunu dəyişə bilərlər. Fermer Con onlardan ən yaxşısını etmələrini xahiş etdi, ən yaxşı külü yuxarı sol küncə (sıra 1, sütun 1), növbəti ən yaxşı külü isə sıra 1, sütun 2-yə (əgər mümkündürsə) və s. yerləşdirməklə. Əlbəttə ki, küllər özlərini tamamilə sıralaya bilməzlər, amma bu hevristikaya əməl edərək ən yaxşısını edə bilərlər:
Fermer Conun mükafatlandırma ardıcıllığını müəyyənləşdirin:
Ən yüksək reytinqə malik külü tapın. Sıra və sütunları dəyişin ki, o, sıra 1, sütun 1-də olsun. Onu bir daha heç vaxt hərəkət etdirməyin.
Sonra mümkün qədər çox külü dəyişmək üçün aşağıdakı qaydanı tətbiq edin:
Növbəti ən yüksək reytinqə malik külü tapın. Sıra və sütunları dəyişin (daha yüksək reytinqə malik külləri hərəkət etdirmədən) ki, onu hələ də mövcud olan ən yaxşı mövqeyə keçirin (məsələn, sıra 1, sütun 2, əgər mövcuddursa, və ya sıra 2, sütun 1, əgər birinci sırada boş yuvalar yoxdursa).
Məsələn, 3 * 4 küllər dəstini nəzərdən keçirək:
99 reytinqə malik kül açıq şəkildə ən yüksək reytinqə malikdir, onu sol yuxarı küncə yerləşdirəcəyik. Bunun üçün sıra 1 və 2-ni dəyişdirəcəyik, sonra sütun 1 və 2-ni dəyişdirəcəyik (və ya əksinə - cavab eynidir):
11 reytinqə malik kül ən yüksək reytinqə malik küllərdən sonra mümkün qədər tez mükafatlandırılmalıdır. O, hazırda (3, 4)-dədir - mükafatlandırılacaq son hüceyrədə. Bu mərhələdə onu birinci sıraya və ya hətta birinci sütuna dəyişmək üçün artıq çox gecdir. O, sütunları 2 və 4-ü dəyişərək, sonra sıra 2 və 3-ü dəyişərək (2, 2)-yə keçməlidir:
10 reytinqə malik kül 11-dən dərhal sonra mükafatlandırılır. 9 reytinqə malik kül artıq mükafatlandırılıb. 8 reytinqə malik kül 10-dan dərhal sonra mükafatlandırılır. 7 reytinqə malik kül 8-dən dərhal sonra mükafatlandırılır. 6 reytinqə malik kül artıq mükafatlandırılıb. 5 reytinqə malik külü ən yaxşı halda sıra 3, sütun 2-yə keçirmək olar, amma sıra 1 və 2 dondurulub, həmçinin bütün sütunlar. Beləliklə, 1, 4 və 5 külləri hərəkət etmir və yuxarıdakı ikinci diaqram - "küllərin edə biləcəyi ən yaxşısıdır".
Bu alqoritmi digər düzbucaqlı kül massivləri üçün həyata keçirin.
Birinci sətir iki tam ədəd w və h (1 ≤ w ≤ 25, 1 ≤ h ≤ 25) ehtiva edir. Növbəti h sətirin hər biri w tam ədəd F[ic] (1 ≤ c ≤ w) ehtiva edir.
h sətir çıxarın. Hər bir sətir küllərin son yerləşməsini müəyyən edən w tam ədəd ehtiva edir.
Nümunə 1