Ključ - Državno

Tajna Komisija vredno je radila na pripremi zadataka za Državno takmičenje i došlo je vreme da se zadaci pošalju na mesta održavanja takmičenja. Naravno, zadaci se čuvaju kao stroga tajna, pa se pre slanja šifruju dobro poznatim algoritmom nastalim u laboratorijama Tajne Komisije.

Algoritmom se šifruje tekst dužine N ∙ M na sledeći način: Matrica sa N redova i M kolona popunjava se slovima teksta red po red, odozgo na dole. Zatim se nekim kolonama u matrici zamene mesta. Formalno, ključ kojim se šifruje je jedna permutacija brojeva od 1 do M. Ključ predstavljamo nizom (a₁, a₂ ,... , a_M), gde a_i predstavlja novu poziciju i-te kolone u matrici. Nakon primene ključa, šifrat (šifrovani tekst) se čita iz matrice istim redosledom kojim je originalni tekst unet u matricu.

Međutim, članovi komisije su malo zaboravni i ne sećaju se ključa koji koriste za šifrovanje zadataka. Naravno, kako je Tajna Komisija veoma odgovorna, ranije je izrađen plan i za ovu situaciju. U tajnom sefu, koji se nalazi negde u zgradi Tajne Komisije (čija lokacija je takođe tajna), sačuvali su jedan tekst sa veoma bitnom osobinom - šifrovanjem tog teksta bilo kojim kljušem ne dobija se leksikografski veći šifrat od šifrata dobijenim šifrovanjem pomoću zaboravljenog ključa.

Ako vam je poznata matrica koja se šifruje i činjenica da se njenim šifrovanjem dobija leksikografski najveći mogući šifrat, odredite ključ.