Bərabəryanlı domino#4224
Hamımız adi domino daşının nə olduğunu bilirik - uzunluğu eni iki dəfə olan düzbucaqlı plitə şəklindədir. Plitə iki bərabər kvadrat hissəyə bölünür, hər birində 1 ilə 6 arasında nöqtələr yerləşir. Oyunun məqsədi domino daşlarını elə yerləşdirməkdir ki, qonşu domino daşlarının qonşu hissələrindəki rəqəmlər üst-üstə düşsün.
Bəs bərabəryanlı üçbucaqlardan domino düzəltmək necə olar, məsələn, bu kimi:
Bərabəryanlı domino iki bərabəryanlı üçbucaqdan ibarət olan dördbucaq şəklindədir. Hər üçbucaqda 1 ilə 6 arasında nöqtələr var. İki bərabəryanlı domino bir-birinə yerləşdirilə bilər, əgər bitişik üçbucaqlarda eyni sayda nöqtələr varsa və domino daşları bir-birini örtmürsə. Əlavə domino daşları yalnız masada artıq mövcud olanlara bitişik şəkildə yerləşdirilə bilər. Başqa sözlə, bir-birini kəsməyən iki domino qrupu icazə verilən yerləşdirmə yaratmır. Məsələn, bərabəryanlı domino daşları aşağıdakı kimi yerləşdirilə bilər:
Sizə verilmiş domino dəstinin müəyyən mənada ən yaxşı yerləşdirilməsini tapmaq lazımdır. İki qonşu domino daşının hər bir kənarı üçün bir xal veriləcək. Verilmiş bərabəryanlı domino dəstinin ən çox xal toplayacaq yerləşdirilməsini tapmaq lazımdır.
Bir neçə testdən ibarətdir. Hər testin ilk sətiri mövcud bərabəryanlı domino daşlarının sayı n (1 ≤ n ≤ 6) ilə başlayır. Sonra n sətir gəlir, hər birində 1 ilə 6 arasında olan iki tam ədəd var. Bu sətirlərdə hər bir domino daşının nöqtələrinin sayı göstərilir. Sonuncu sətir n = 0 ilə bitir və işlənmir.
Hər test üçün verilmiş bərabəryanlı domino dəstinin yerləşdirilməsi ilə əldə edilə bilən ən çox xalın sayını ayrıca sətirdə çıxarın. Əgər icazə verilən yerləşdirmə mövcud deyilsə, sıfır çıxarın.
Nümunə 1