Təqdimat
Siz ikili ağaclar üzərində alqoritmləri araşdıran bir alim olaraq çalışırsınız. İkili ağac, budaqlanma düyünləri və yarpaqlardan ibarət olan bir məlumat strukturudur. Hər bir budaqlanma düyünü sol və sağ övladlara malikdir və hər bir övlad ya budaqlanma düyünü, ya da yarpaq ola bilər. Ağacın kökü isə valideyni olmayan budaqlanma düyünüdür.
Təqdimata hazırlaşarkən, proqram vasitəsilə ikili ağacların təsvirini yaratmalısınız. Artıq bir budaqlanma düyünü və iki yarpaqdan ibarət olan ikili ağacın təsvirini hazırlamısınız (Şəkil 1). Lakin qəfildən proqramın təsvir yaratma funksiyası işləmir. Bu sizi məyus etdi, çünki beş saat sonra böyük bir auditoriya qarşısında təqdimat etməlisiniz.
Siz yalnız kopyalama, sıxma və yapışdırma funksiyalarından istifadə edərək ikili ağacların təsvirini yaratmağa qərar verdiniz. Yəni yalnız aşağıdakı iki növ əməliyyatı həyata keçirə bilərsiniz:
Cari fiquru mübadilə buferinə kopyalamaq (fiqur buferə kopyalanır, əvvəlki məzmunu silinir).
Kopyalanmış fiquru yapışdırmaq (lazım gələrsə miqyaslama ilə), yapışdırılmış fiqurun kökünü cari fiqurun yarpağına birləşdirmək (kopyalanmış fiquru bir neçə dəfə yapışdırmaq olar).
Bundan əlavə, siz ən az sayda yapışdırma əməliyyatı ilə fiquru yaratmağa qərar verdiniz, çünki məhz yapışdırma əməliyyatı çox vaxt tələb edir. Sizin vəzifəniz - verilmiş fiquru yaratmaq üçün ən az sayda yapışdırma əməliyyatını tapmaqdır.
Şəkil 1: başlanğıc vəziyyət
Misalın cavabı 1 (Şəkil 4) 3-ə bərabərdir, çünki lazım olan fiquru minimum əməliyyatlarla əldə etmək olar.
Şəkil 2: aralıq mərhələ 1
Şəkil 3: aralıq mərhələ 2
Şəkil 4: Tapşırıq
Giriş verilənləri
Giriş sətiri ikili ağacı təyin edir. İfadənin qrammatikası aşağıdakı BNF ilə verilir:
::= | "(" ")"
::= "()"
Giriş məlumatları göstərilən sintaksisə uyğundur. Hər bir giriş ağacının ən azı bir və ən çox 10^5 budaqlanma düyünü olduğunu qəbul edin.
Çıxış verilənləri
Verilmiş ikili ağacı əldə etmək üçün yerinə yetirilməli olan ən az sayda yapışdırma əməliyyatını çıxarın.