DNT-nin çevrilməsi#4176
Biologiya laboratoriyası Advanced Cellular Mechanics Lab. (ACM Lab.) genomlar və DNT sahəsində tədqiqatlar aparır. Bu laboratoriyada son zamanlarda DNT zəncirində bəzi çevrilmələri daha ucuz başa gətirən bir texnologiya hazırlanmışdır.
DNT zəncirini {A, G, C, T} çoxluğundan simvolların n uzunluqlu bir sıra kimi təsəvvür edək. Laboratoriyanın biologlarının bacardığı elementar çevrilmə, l-dən r-ə qədər olan simvolların (burada l və r elə seçilir ki, 1 ≤ l ≤ r ≤ n) alt-sırasının çevrilməsidir. Beləliklə, a_1a_2...a_la_{l+1}...a_{r−1}a_r...a_n sırasından a_1a_2...a_ra_{r−1}...a_{l+1}a_l...a_n sırası alınır.
İndi biologlar DNT çevrilmələrini həyata keçirmək üçün proqram-aparat kompleksi hazırlayırlar. Onun funksiyalarından biri ilkin DNT zəncirini tələb olunan zəncirə çevirmək olacaq.
Sizin vəzifəniz - ilkin və tələb olunan DNT zəncirlərinə görə bu çevrilmələr zəncirini tapacaq proqram yazmaqdır.
Giriş faylının birinci sətiri ilkin DNT zəncirinin təsvirini, ikinci sətir isə tələb olunan DNT zəncirinin təsvirini ehtiva edir. Hər iki zəncirin uzunluğu eynidir və 5000-i keçmir. Hər bir zəncir yalnız {A, G, C, T} çoxluğundan simvollar ehtiva edir.
Axtarılan çevrilmələr ardıcıllığının mövcudluğu təmin edilir.
Çıxış faylının birinci sətirində qurulmuş həllin k çevrilmələrinin sayını göstərin. Say k qeyri-mənfi olmalı və 4999-u keçməməlidir.
Daha sonra qurulmuş elementar çevrilmələr ardıcıllığını təsvir edən k sətir göstərin. Hər bir sətir iki ədəd ehtiva etməlidir: l_i və r_i - müvafiq olaraq i-ci addımda çevrilən seqmentin sol və sağ ucu.
Nümunə 1