Tanqleqram
Müstəvi üzərində N hissəli iki tamamlanmış binar ağac yerləşir. Onun 2x2^N yarpağı iki paralel düz xətt üzərində yerləşir və soldan sağa nömrələnmişdir.
Birinci və ikinci ağacdakı eyni nömrəli yarpaqlar qarşı-qarşıya yerləşib. Ağacların yarpaqları arasında qarşılıqlı uyğunluq verilmişdir- bir ağacın hər bir yarpağına ikinci ağacda uyğun olan düz bir ədəd yarpaq var və əksinə. Şəkildə belə uyğunluq yarpaqlar arasında düz xətt parçaları ilə verilmişdir. Belə konstruksiya, yəni yarpaqları arasında qarşılıqlı uyğunluqla birlikdə iki ağac tanqleqram adlanır. Tanqleqramdan, məsələn, biologiyada müxtəlif növ bitkilərin genlərinin qarşılıqlı əlaqəsinin tədqiqində istifadə olunur. Əgər tanqleqramda uyğunluq parçaları kəsişərsə, onda onu tədqiq etmək çətindir. Kəsişmələrin sayını azaltmaq üçün bir əməliyyat aparmağa icazə verilir: birinci (yuxarıdakı) ağacdakı ixtiyari təpəli iki alt ağacın yerini ikinci şəkildə göstərilən kimi dəyişmək olar.
Tapşırıq: İki ağacın yarpaqları arasında verilmiş uyğunluğa aid informasiyaya görə tanqleqramın qrafik təsvirində birinci ağacın qonşu altağaclarında yerdəyişmə əməliyyatı aparmaqla parçaların nail olunan mümkün ən az kəsişmələrinin sayını tapmaq üçün proqram yazın. Əgər bir nöqtədə ikidən artıq parça kəsişirsə, kəsişmə sayı kimi cüt-cüt parçaların sayı başa düşülür. Məsələn, birinci şəkildə 4-8, 5-5 və 6-4 uyğunluğu üç kəsişmə əmələ gətirir.
Giriş verilənləri
Giriş faylının birinci sətrində ağacın hissələrinin sayı olan N (1 ≤ N ≤ 19) bir natural ədəd yerləşir. İkinci sətirdə 2^N sayda 1-dən 2^N-dək müxtəlif tam ədəd - hər bir i-cisi birinci ağacın i-ci yarpağı ilə əlaqəli parçası olan ikinci ağacın yarpağını verir.
Çıxış verilənləri
Çıxış faylının yeganə sətrində tanqleqramda uyğun parçaların birinci ağacın altağaclarında yerdəyişmə əməliyyatı aparmaqla nail olunan mümkün ən az kəsişmələrinin sayı yerləşməlidir.