Ханой qüllələri
Hər bir proqramçı "Hanoi qüllələri" tapmacasını bilir. Gəlin onun şərtini qısaca xatırlayaq.
3 çubuq var: A, B, C. Əvvəlcə müxtəlif diametrli n disk çubuq A-da yerləşir: ən kiçik disk yuxarıda, daha böyük diametrli disklər isə aşağıda yerləşir. İkinci və üçüncü çubuqlar isə boşdur.
Məqsəd bütün diskləri çubuq A-dan çubuq B-yə köçürməkdir, bu zaman çubuq C köməkçi kimi istifadə edilə bilər.
Bir addımda yalnız 1 üst disk çıxarılıb ya boş çubuğa, ya da başqa çubuqdakı daha böyük diametrli diskin üstünə qoyula bilər.
Demək olar ki, bütün proqramlaşdırma kitablarında bu məsələnin rekursiv həlli mövcuddur. Aşağıda Pascal dilində bir prosedur verilmişdir.
Procedure Hanoi (A, B, C: integer; N:integer);
Begin
If N>0 then
Begin
Hanoi (A, C, B, N-1);
Writeln(‘Disk ’, N, ‘ from ‘, A, ‘ to ‘, B);
Hanoi (C, B, A, N-1)
End
End;
Məsələn, "BCA" kombinasiyası ən kiçik diskin B çubuğunda, orta diskin C çubuğunda və ən böyük diskin A çubuğunda yerləşdiyini göstərir.
Münsiflər heyəti yarışa hazırlaşarkən bəzən bu oyunu oynayır və cari kombinasiyaları (hər birini ayrı bir kağız parçasında) qeyd edirlər. Lakin sonradan bu kağızlar qarışır.
Verilən kombinasiyanın oyunda olub-olmadığını müəyyən edən bir proqram yazın.
Giriş verilənləri
Birinci sətir n (1 ≤ n ≤ 250) — disk sayı və m (1 ≤ m ≤ 1000) — kombinasiyaların sayını ehtiva edir. Növbəti m sətir m kombinasiyanı ehtiva edir. Hər bir kombinasiyada çubuqlardakı n diskin yerləşməsi göstərilir və böyük hərflərlə ("A", "B" və ya "C") ifadə olunur. İlk (sol) hərf ən kiçik diskin mövqeyini (çubuq adını), ikinci hərf isə ikinci ən böyük diskin mövqeyini göstərir və s.
Çıxış verilənləri
m sətir çıxarın — oyunda ardıcıllıqla gələn m kombinasiyalar.