Qeydlər və dövrlər#7321
Bu tapşırıqda sizdən, verilən hər bir n uzunluqlu k dövrlü permutasiyanı n uzunluqlu k qeydləri olan permutasiyaya uyğunlaşdıran bijeksiya qurmağınız tələb olunur.
p permutasiyası n uzunluqlu p(1), p(2), ..., p(n) ardıcıllığıdır ki, burada 1, 2, ..., n ədədlərinin hər biri ardıcıllıqda dəqiq bir dəfə iştirak edir.
p permutasiyasında dövr c_1, c_2, ..., c_m ədədləri ardıcıllığıdır ki, burada p(c_1) = c_2, p(c_2) = c_3, ..., p(c_m) = c_1. Xüsusi hal olaraq, tək uzunluqlu dövr: p(i) = i. Hər bir permutasiyanın cüt-cüt kəsişməyən dövrlərin birləşməsi kimi təqdim edilə biləcəyini göstərmək olar.
p permutasiyasında qeyd və ya qeydin dəyəri, özündən əvvəlki bütün elementlərdən böyük olan p_j elementidir: p_j > p_i hər bir i < j üçün. Qeyd edək ki, p_1 həmişə qeyd olaraq qəbul edilir. n və k verilmiş olduqda, n uzunluqlu k dövrlü permutasiyaların sayının n uzunluqlu k qeydləri olan permutasiyaların sayına bərabər olduğunu sübut etmək olar. Buna görə də, n uzunluqlu k dövrlü permutasiyaları n uzunluqlu k qeydləri olan permutasiyalara və əksinə uyğunlaşdıran bijeksiya mövcuddur. Bijeksiya iki çoxluğun elementlərini qarşılıqlı bir-birinə uyğunlaşdıran funksiyadır: birinci çoxluğun hər bir elementinə dəqiq bir dəfə ikinci çoxluğun elementi uyğun gəlir və ikinci çoxluğun hər bir elementinə dəqiq bir dəfə birinci çoxluğun elementi uyğun gəlir. Siz belə bir funksiyanı tapmalı və həyata keçirməlisiniz.
Birinci sətir permutasiyaların sayı t (1 ≤ t ≤ 300 000) verir.
Növbəti t sətirin hər biri bir permutasiyanın təsvirini ehtiva edir. Təsvir n (1 ≤ n ≤ 300 000) - permutasiyanın uzunluğu ilə başlayır, sonra permutasiyanın növünü göstərən “r” və ya “c” simvolu gəlir. Daha sonra permutasiyanı təyin edən n tam ədədlər ardıcıllığı gəlir. Bu ardıcıllıqda 1 ilə n arasında olan hər bir ədəd yalnız bir dəfə iştirak edir.
Sətirdəki ardıcıl elementlər boşluqla ayrılır. Bütün giriş permutasiyalarının ümumi uzunluğu 300 000-i keçmir.
Giriş məlumatları ilə eyni formatda olmalıdır.
Birinci sətir giriş permutasiyalarının sayını t verir.
Verilən t permutasiyanın hər biri üçün uyğun gələn permutasiyanı ayrıca sətirdə çıxış edin. Əgər giriş permutasiyasının növü “r”dirsə, onun qeydlərinin sayını tapın və ona uyğun gələn, eyni sayda dövrləri olan “c” növündə permutasiyanı çıxış edin. Əgər giriş permutasiyasının növü “c”dirsə, onun dövrlərinin sayını tapın və ona uyğun gələn, eyni sayda qeydləri olan “r” növündə permutasiyanı çıxış edin.
Hər bir t sətir permutasiyanın uzunluğu n ilə başlayır, sonra növü göstərən simvol gəlir. Daha sonra permutasiyanı təsvir edən n ədəd gəlir. Bir sətirdəki ardıcıl tokenləri bir boşluqla ayırın.
Uyğunluq ardıcıl olmalıdır: əgər “r” növündə olan p permutasiyasına “c” növündə olan q permutasiyası uyğun gəlirsə, əksinə də doğru olmalıdır, başqa heç bir “c” növündə permutasiya p-yə uyğun gələ bilməz və başqa heç bir “r” növündə permutasiya q-ya uyğun gələ bilməz. Sizin bijeksiyanız müxtəlif testlərlə uyğunlaşmaq məcburiyyətində deyil.
Nümunə 1
Birinci permutasiyanın uzunluğu n = 3. Birinci permutasiya “r” növündədir və üç qeyd ehtiva edir. İkinci permutasiya “c” növündədir və üç dövr ehtiva edir. Bu iki permutasiya bir-birinə uyğun gəlir. Üçüncü və dördüncü permutasiyalar “r” növündədir və hər biri iki qeyd ehtiva edir. Beşinci permutasiya “c” növündədir və iki dövr ehtiva edir. O, üçüncü permutasiyaya uyğun gəlir. Dördüncü permutasiya 3, 2, 1 növündə olan və iki dövr ehtiva edən “c” növündəki permutasiyaya uyğun gəlir.
Son permutasiya n = 2 uzunluqlu, “c” növündədir və bir dövrdən ibarətdir. O, bir qeydi olan 2, 1 növündəki “r” permutasiyasına uyğun gəlir.
Qeyd edək ki, bu, yeganə mümkün bijeksiya deyil: nümunədə alternativ çıxış variantı verilmişdir. Üçüncü giriş permutasiyası (2, 1, 3 növündə “r”) üçün 3, 2, 1 növündə “c” uyğun seçilmişdir. Onda dördüncü permutasiya (2, 3, 1 növündə “r”) başqa uyğun permutasiya olmalıdır, buna görə də ona 1, 3, 2 növündə “c” permutasiyasını seçəcəyik. Beşinci permutasiya (2, 1, 3 növündə “c”) üçün yeganə mümkün olan 1, 3, 2 növündə “r”dir, çünki iki qeydi olan digər iki permutasiya artıq iki dövrü olan digər permutasiyalara uyğun gəlir.