Лойд tapşırığı#4344
Sem Loyd məşhur amerikalı tapmaca ustasıdır. Onun ən tanınmış tapmacalarından biri “On beş oyunu”dur. O, həmçinin bir çox şahmat məsələlərinin və kəsim məsələlərinin müəllifi kimi də tanınır. İndi siz Loydun şahmat taxtasının kəsilməsi məsələsini həll etməyi sınaya bilərsiniz.
Sizə n \times n ölçüsündə şahmat taxtası verilir. Onu maksimum sayda hissəyə elə kəsmək lazımdır ki, istənilən iki hissə fərqli olsun. Hər bir hissə bir və ya bir neçə hüceyrədən ibarət olmalı və yan tərəfdən əlaqəli bir fiqur təşkil etməlidir. Əgər bir hissə digərindən fırlatma ilə əldə edilirsə, onlar eyni sayılır. Məsələn, iki tək hüceyrəli hissə var: qara hüceyrə və ağ hüceyrə, və yalnız bir iki hüceyrədən ibarət hissə mövcuddur.
Budur, adi 8 \times 8 ölçülü şahmat taxtasını fərqli hissəyə kəsmək üçün Loyddan orijinal məsələnin bir həlli:
Birinci sətirdə taxtanın tərəfinin uzunluğunu göstərən tam ədəd verilir (1 \leq n \leq 30).
Birinci sətirdə taxtanı kəsmək üçün mümkün olan maksimum hissələrin sayını çıxarın. Sonra kəsimi göstərin: hər birində kiçik latın hərfi olan sətir. Hər bir hissə eyni hərflərdən ibarət olmalıdır. Eyni hərfi bir neçə hissəni göstərmək üçün istifadə etmək olar, lakin istənilən iki qonşu hissə fərqli hərflərdən ibarət olmalıdır (izahat üçün nümunəyə baxın). Əgər bir neçə optimal kəsim mövcuddursa, istənilənini çıxara bilərsiniz.
Nümunə 1