RNA Molekulları#6899
RNA molekulu dörd nukleotiddən ibarətdir: A, C, G və U. Nukleotidlərin kimyəvi quruluşuna əsasən, yalnız (A, U), (U, A), (G, C) və (C, G) cütləri arasında hidrogen bağları qurula bilər. Digər hallarda, məsələn, A nə C ilə, nə də G ilə hidrogen bağı qura bilməz. Hər bir nukleotid yalnız bir başqa nukleotid ilə hidrogen bağı qura bilər və RNA ardıcıllığında ardıcıl olan iki nukleotid arasında hidrogen bağı ola bilməz, çünki onların arasında artıq kovalent əlaqə mövcuddur.
Canlı hüceyrələrdə RNA qatlanır və çoxlu hidrogen bağları qurulur. Lakin hidrogen bağları bir-birini kəsə bilməz. Yəni əgər i nukleotidindən j nukleotidinə (i < j) bir bağ varsa, i+1, … , j−1 nukleotidləri yalnız öz aralarında bağlar qura bilər və 1, …, i−1 və ya j+1, …, n (burada n RNA-dakı nukleotidlərin sayıdır) ilə heç bir bağ qura bilməzlər.
RNA-nın real vəziyyəti daha mürəkkəbdir, lakin bu yarışmada sizə çox mürəkkəbliklərlə üzləşdirməyəcəyik, həyatınızı asanlaşdıracağıq.
Sizin vəzifəniz verilmiş RNA molekulları üçün mümkün olan maksimum bağları tapmaqdır.
Girişdə bir neçə test halı var. Hər bir test halı 0 ≤ n ≤ 500 qeyri-mənfi tam ədədi ilə başlayan bir sətirdən ibarətdir. Hər bir test halının ikinci sətri n ölçüsündə A, C, G və U simvollarından ibarət bir sətirdir (RNA molekulu). Giriş "0" ilə bitir və bu işlənməməlidir.
Hər bir test halı üçün verilmiş RNA molekulu üçün maksimum hidrogen bağlarının sayını çıxış edin.
Nümunə 1