Minimal matris#3075

Minimal matris

2 saniyə

256 meqabayt

Orta

Verilən Sətirlər Araşdırma İnstitutu yeni bir şöbə açıb — Verilən Matrislər Araşdırma Şöbəsi. Sətirin kanonizasiyası məsələsi kimi, bu şöbə matrisin kanonizasiyası məsələsi üzərində işləyir.

$2^{n} \times 2^{n}$ 2^n \times 2^n ölçülü, kiçik latın hərflərindən ibarət $m_{i, j}$ m_{i,j} matrisi nəzərdən keçirilir.

Matrisin dövri sürüşməsi $m$ matrisinin belə bir $m^{'}$ m' matrisinə deyilir ki, $m_{i, j}^{'} = m_{(i + Δ i) mod 2^{n}, (j + Δ j) mod 2^{n}}$ m'_{i,j} = m_{(i+\Delta i) \bmod 2^n,\ (j+\Delta j) \bmod 2^n} bərabərliyi ödənir, burada $Δ i$ və $Δ j$ bəzi ədədlərdir (matrisin sətir və sütunları $0$ -dan $2^{n} - 1$ 2^n-1-ə kimi indekslənir).

$p$ matrisi və $q$ matrisi eyni ölçüdə olmaqla, əgər elə $i$ və $j$ mövcuddursa ki, bütün $i^{'} < i$ i' < i üçün və ya $i^{'} = i$ i'=i və $j^{'} < j$ j'<j üçün $p_{i^{'}, j^{'}} = q_{i^{'}, j^{'}}$ p_{i',j'} = q_{i',j'} və $p_{i, j} < q_{i, j}$ p_{i,j} < q_{i,j} olursa, onda $p$ matrisi $q$ matrisindən leksikoqrafik cəhətdən kiçik sayılır. Yəni, matrislər sətir-sətir müqayisə edilir.

$m$ matrisinin kanonizasiya məsələsi, onun elə bir dövri sürüşməsini tapmaqdır ki, bu sürüşmə $m$ matrisinin bütün digər dövri sürüşmələrindən leksikoqrafik cəhətdən kiçik və ya bərabər olsun.

Yeni şöbənin tədqiqatçılarına matrisin kanonik təsvirini tapmaqda kömək edin.

Giriş

$2^{n} \times 2^{n}$ 2^n \times 2^n ( $0 \leq n \leq 9$ 0 \leq n \leq 9) ölçülü $m$ matrisi verilir.

Çıxış

$m$ matrisinin kanonik təsvirini çap edin.

Nümunələr

Nümunə 1

Loading

2^{n} \times 2^{n}

m_{i, j}

m^{'}

m_{i, j}^{'} = m_{(i + Δ i) mod 2^{n}, (j + Δ j) mod 2^{n}}

2^{n} - 1

i^{'} < i

i^{'} = i

j^{'} < j

p_{i^{'}, j^{'}} = q_{i^{'}, j^{'}}

p_{i, j} < q_{i, j}

2^{n} \times 2^{n}

0 \leq n \leq 9