GIF-də sıxılmış faylların açılması
Məlum üsullardan biri şəkil fayllarını sıxışdırmaq üçün Graphics Interchange Format (GIF) kodlaşdırmasıdır. Bu üsul CompuServe tərəfindən 1987-ci ildə yaradılmışdır. Burada əlifba simvollarından ibarət sətirlərə tətbiq olunan sadələşdirilmiş bir versiya təqdim olunur. Sıxışdırma üçün vacib olan bir lüğətdir ki, o, müxtəlif simvol sətirlərinə rəqəmli kodlar (bu məsələdə 10 əsaslı rəqəmlərdən istifadə edəcəyik) təyin edir. Lüğət, sətirdə görünə biləcək simvollar və ya alt sətirlər üçün uyğunluqlarla başlanğıc vəziyyətə gətirilir. Məsələn, əgər biz bütün 26 əlifba hərfləri ilə qarşılaşacağımızı gözləyiriksə, lüğət əvvəlcə kodları (A, 00), (B, 01), (C, 02), . . . , (Z, 25) saxlayacaq. Əgər biz DNT məlumatlarını sıxışdırırıqsa, lüğət əvvəlcə yalnız 4 giriş saxlayacaq: (A, 0), (T, 1), (G, 2) və (C, 3). Qeyd edək ki, hər bir başlanğıc kodun uzunluğu bütün girişlər üçün eynidir (birinci nümunədə 2 rəqəm, ikinci nümunədə isə 1 rəqəm).
Sıxışdırma alqoritmi aşağıdakı kimi işləyir:
Sıxışdırılmamış sətirin lüğətdə olan ən uzun prefiksini tapın və onu rəqəmli kodu ilə əvəz edin.
Əgər sətirin sonuna çatılmayıbsa, lüğətə yeni bir uyğunluq (s, n) əlavə edin, burada s = yeni sıxışdırılmış prefiks və sətirdəki ondan sonrakı simvol, n isə lüğətdə hələ istifadə olunmamış ən kiçik rəqəmdir.
Məsələn, əgər biz ABABBAABB sətiri ilə və yalnız iki girişdən ibarət lüğətlə başlamışıqsa, (A, 0) və (B, 1), aşağıdakı cədvəl sətirin sıxışdırılma addımlarını göstərir.
Nəticədə sıxışdırılmış sətir 01234 olur.
Yalnız bir başqa qayda var: əvəzləmə üçün istifadə olunan sətirlər həmişə əvəzləmə baş verən anda lüğətdəki ən uzun kodun ölçüsündə olmalıdır. Beləliklə, yuxarıdakı lüğətlə, əgər sıxışdırılacaq sətir kifayət qədər uzundursa və lüğətə (s, 10) formasında bir giriş əlavə olunursa, o zaman bu nöqtədən etibarən sıxışdırılmış sətirdə istifadə olunan bütün rəqəmli əvəzləmə sətirləri 2 rəqəm uzunluğuna genişlənməlidir (yəni, A indi 00, B isə 01, AB isə 02 kimi kodlanacaq); əgər lüğətə (s′, 100) formasında bir giriş əlavə olunursa, bu nöqtədən etibarən bütün əvəzləmələr 3 rəqəm uzunluğuna artacaq və s. Beləliklə, daha uzun ABABBAABBAABAABAB sətiri 01234027301 kimi kodlanacaq, 0123402731 kimi yox. Cəhd edin!
Yaxşı, indi sıxışdırma üzrə mütəxəssis olduğunuz üçün rahatlayın və açın!
Giriş verilənləri
Hər bir test halı iki sətirdən ibarət olacaq. Birinci sətir açılacaq rəqəmli sətiri ehtiva edəcək. İkinci sətir sıxışdırmada istifadə olunan başlanğıc lüğəti ehtiva edəcək. Bu sətir lüğətdəki girişlərin sayını göstərən müsbət tam ədəd n ilə başlayacaq (1 ≤ n ≤ 100), ardınca n əlifba sətirləri gələcək. Bunlardan birincisi lüğətdə 0 (və ya 00 əgər n > 10 olarsa), ikincisi 1 ilə uyğunlaşdırılacaq və s. Son test halı 0 tək sətiri ilə bitəcək.
Çıxış verilənləri
Hər bir test halı üçün, hal nömrəsini (aşağıda göstərilən formatda) və açılmış sətiri ehtiva edən tək bir sətir çıxarın. Bütün giriş sətirləri qanuni şəkildə sıxışdırılmış olacaq.