Özüaçılan şifrələmə
Petya onun icazəsi olmadan oxunmaması üçün gündəliyini şifrələmək qərarına gəldi. Bunun üçün o növbəti şifrədən istifadə etdi.
O N×N xanalı (N — cütdür) trafaret hazırladı, N^2/4 xananı elə kəsdi ki, trafareti dörd mümkün variantda (trafareti döndərmək olar, çevirmək isə olmaz) kağız vərəqi üzərində yerləşdirdikdə vərəqin hər bir xanası tam bir dəfə görönsün.
Belə bir trafaretə aid nümunə aşağıdakı şəkildə verilmişdir:
Bu trafaret vasitəsilə N^2 simvol növbəti şəkildə şifrələnir. Əvvəlcə şifrələnən mətnin ilk N^2/4 hərfi trafaretin kəsiklərinə yazılır (hərflər gəsilmiş xanalara sətirlər boyunca yuxarıdan aşağıya, hər sətirdə də soldan sağa doğru yazılır. Məsələn, əgər Petya ОЛИМПИАДА sözünü şifrələyirsə, onda bu söz xanalara növbəti şəkildə yazılacaqdır:
Bundan sonra trafaret saat əqrəbi istiqamətində 90 dərəcə döndərilir və kəsilmiş xanalara eyni ardıcıllıqla növbəti N^2/4 hərf yazılır, mətn qurtardıqda qalan xanalar böş saxlanılır.
Məsələn, əgər Petya ОЛИМПИАДА ПО ИНФОРМАТИКЕ 2006 ГОДА mətnini verilmiş trafaret vasitəsilə şifrələyirsə, onda şifrələmə prosesi növbəti şəkildə aparılacaq: ОЛИМПИАДА sözünü necə şifrələməyi biz artıq göstərmişdik. Rahat olması üçün burada və sonra boşluğu altcizgi ilə işarələyəcəyik. Trafaretin ikinci qoyuluşunda Petya _ПО_ИНФОР şifrələyə biləcək:
Trafaretin üçüncü qoyuluşunda МАТИКЕ_20 şifrələyəcək:
Trafaretin dördüncü qoyuluşunda Petya 06_ГОДА şifrələyəcək. Qalan xanalar boş qalacaq (hesab edəcəyik ki, onlara bizim altcizgi ilə işarə etdiyimiz boşluq yazılıb):
Bundan sonra Petya alınmış mətni sətirdə yazır:
О М0ЛП6И МОАТГ ИПОИКИДНАДАЕФ О 2РА 0
Etibarlılığını artırmaq üçün Petya şifrələnmiş mətni həmin trafaret vasitəsilə eyni metodla təkrar şifrələmək qərarına gəldi, sonra alınan mətni yenə və s. Bir neçə təkrarlamadan sonra Petya heyrətlə gördü ki, şifrələnmiş mətn ilkin mətnlə üst-üstə düşür.
Mətnin məzmunundan asılı olmayaraq Petyanın verilmiş trafaretdən istifadə edərək cari mətni əldə etməsi üçün şifrələmə prosedurlarının minimal sayını təyin edən proqramı tərtib edin.
Giriş verilənləri
Giriş faylında əvvəlcə trafaretin ölçüsü N (2 ≤ N ≤ 150) verilir. Sonra trafareti əks etdirən hər biri 0 və ya 1 olan N^2 sayda ədəd verilir. 1 kəsilmiş xananı, 0 — kəsilməmiş xananı ifadə edir. Verilmiş ardıcıllığın verilmiş şifrələmə üsulu üçün düzgün trafareti əks etdirdiyinə zəmanət verilir.
Çıxış verilənləri
Çıxış faylında bir ədəd — mətnin məzmunundan asılı olmayaraq Petyanın verilmiş trafaretdən istifadə edərək cari mətni əldə etməsi üçün şifrələmə əməliyyatının təkrarlanmasının minimal sayını verməli.