Sehrli piramida
Məşhur Rubik Kubunun bir çox modifikasiyası mövcuddur. Bunlardan biri də Magic Pyramid adlanır və bu, orijinal kub yerinə tetraedr formasında qurulmuşdur. Tetraedrin üzləri Latın hərfləri X, U, V və W ilə işarələnmişdir. Hər bir üz Şəkil 1-də göstərildiyi kimi 1-dən 36-ya qədər nömrələnmiş 9 bərabərtərəfli üçbucağa bölünmüşdür. Tetraedri yığmaq üçün böyük üçbucaq daxili qalın xətlər boyunca aşağı qatlanmalı və xarici qalın xətlərin uyğun yarıları birləşdirilməlidir.
Hər bir kiçik üçbucaq dörd fərqli rəngdən biri ilə boyanmışdır ki, biz onları
Şəkil 1
Latın hərfləri a, b, c və d ilə işarələyirik. Hər dörd rəngdən dəqiq 9 üçbucaq var.
Tetraedri "üzü döndər" əməliyyatı ilə dəyişə bilərik. Bu əməliyyatı yerinə yetirmək üçün piramidanın bir üzünü seçirik və piramidanı seçilmiş üz bizə tərəf yönəldəcək şəkildə yerləşdiririk. Sonra döndürmə istiqamətini (saat əqrəbi istiqamətində və ya əksinə) müəyyən edirik. Nəhayət, tetraedrin seçilmiş üzü ilə ən yaxın olan və tetraedrin hündürlüyünün 1/3 qalınlığında olan hissəsini seçilmiş istiqamətdə 120 dərəcə döndəririk, tetraedrin qalan hissəsini isə hərəkətsiz saxlayırıq. Şəkil 2 saat əqrəbi istiqamətində U üzünün döndərilməsinin təsirini göstərir.
Üzlərin döndərilməsinə əlavə olaraq, "sehrli yenidən boyama" əməliyyatını da tətbiq edə bilərik. Bu əməliyyat 1 -dən 36-ya qədər olan tam ədədlərin permutasiyası (p_1, …, p_36) ilə müəyyən edilir. Əməliyyatın təsiri, hazırda Şəkil 1-də verilmiş nömrələməyə görə mövqedə olan i üçbucağının, hazırda mövqedə olan p_{i} üçbucağının rənginə yenidən boyanmasıdır. Bütün 36 üçbucaq eyni anda yenidən boyanır.
Əgər bir sıra "üzü döndər" və ya "sehrli yenidən boyama" əməliyyatları tətbiq edildikdən sonra tetraedrin hər üzündəki bütün üçbucaqlar eyni rəngdədirsə, tapmaca həll olunmuş sayılır.
Magic Pyramid tapmacasını minimal mümkün hərəkət sayı ilə həll etmək üçün bir proqram yazın. Bütün test halların 9 və ya daha az hərəkətlə həll edilə biləcəyini qəbul edə bilərsiniz.
Giriş verilənləri
Faylın ilk sətri 36 'a'…'d' hərflərini ehtiva edir. Mövqedə olan hərf i üçbucağın ilkin rəngini göstərir. Məlumdur ki, hər dörd hərf dəqiq 9 dəfə faylın ilk sətrində mövcuddur.
Faylın ikinci sətri "sehrli yenidən boyama" əməliyyatını təsvir edən 36 fərqli tam ədəd 1…36 ehtiva edir. Bu sətirdəki i-ci tam ədəd əməliyyatı müəyyən edən permutasiyanın p_i üzvüdür.
Çıxış verilənləri
Faylın ilk və yeganə sətri 'X', 'U', 'V', 'W', 'x', 'u', 'v', 'w' və '*' simvollarından ibarət bir simvol sırasını ehtiva etməlidir. Tapmacanın həllindəki i-ci hərəkəti təsvir etməlidir. Hər "üzü döndər" əməliyyatı müvafiq üzün etiketi kimi verilir, kiçik hərf saat əqrəbi istiqamətində döndərməni, böyük hərf isə əks istiqamətdə döndərməni göstərir. "Sehrli yenidən boyama" əməliyyatı '*' simvolu ilə verilir.
Əgər minimal hərəkət sayı ilə bir neçə həll yolu varsa, onlardan hər hansı birini çıxış edin. Əgər tapmaca heç bir hərəkət etmədən həll edilə bilərsə, fayla boş bir sətir çıxış edin.
Nümunənin izahı: Şəkil 3 tetraedrin ilkin rənglənməsini göstərir, Şəkil 4 və 5 isə hər bir əməliyyatın nəticələrini göstərir. Üçbucaqların rəngləri aşağıdakı nümunələrlə verilir:
