Draganče radi za kontraobaveštajnu službu. On je otkrio da se šifrovane poruke neprijatelja uvek dobijaju linearnim preslikavanjem. Najpre se svako slovo predstavi brojem od 0 do n - 1, gde je n broj slova u pismu (ove brojeve ćemo zvati indeksima slova). Potom se šifra zada u obliku y = (a + b · x) mod n, gde je nzd(b, n) = 1. To znači da se slovo predstavljeno brojem x šifrira slovom koje je predstavljeno brojem y (y = (a + b · x) mod n). Pored saznanja o načinu šifrovanja poruka, Draganče ima i podatke o učestanosti svih slova u jeziku neprijatelja. Za svako slovo x se zna očekivani procenat pojavljivanja p(x) u proizvoljnom tekstu. Treba pomoći Dragančetu da dešifruje jednu izuzetno važnu poruku uz pomoć statistike i saznanja o linearnom šifrovanju.

Ulaz.

(Ulazni podaci se nalaze u datoteci sifra.in) U prvom redu se nalazi prirodan broj n, 3 ≤ n ≤ 26, ukupan broj slova u neprijateljskom alfabetu. Sledi n redova i u svakom je dato jedno slovo iz alfabeta i jedan broj, razdvojeni razmakom. Slovo u prvom redu ima indeks 0, u drugom 1, ... u n-tom redu ima indeks n - 1. Slovo je uvek predstavljeno kao veliko slovo iz engleskog alfabeta, dok broj predstavlja procenat učestanosti datog slova u proizvoljnom tekstu. Procenat je zadat sa dve decimale. Slovo imaju različite učestanosti, a ukupan zbir svih učestanosti je 100. U sledećem redu je ceo broj L (10 ≤ L ≤ 1000) i on predstavlja dužinu šifrovanog teksta. U poslednjem redu, nalazi se tekst od tačno L slova (bez razmaka i znakova interpunkcije) koji predstavljaju šifrovani tekst. Sva slova koja se nalaze u šifrovanom tekstu su prethodno već zadata sa svojim učestanostima.

Izlaz.

(Izlazne podatke upisati u datoteku sifra.out) U jedinom redu izlaza treba ispisati dešifrovani tekst, dešifrovan preko linearnog preslikavanja, a koji najviše odgovara zadatoj statistici.

Primer 1.

4
B 42.25
A 20.00
Z 10.15
E 27.60
8
AZABAZEBAZ

BEBABEZABE

Napomena.

Na osnovu ulaza imamo se slova predstavljaju brojevima od 0 do 3 na sledeći nachin: B → 0, A → 1, Z → 2 i E → 3. Preslikavanje kod kog se dobija najbolje preklapanje je y = (a + b · x) mod 4, gde su a = 1 i b = 3.

#include <fstream>
#include <iostream>
using namespace std;

const int MAXL = 1000+ 5, MAXN = 26 + 5;
int n, l;
char c[MAXN];
int index[MAXL];
char s[MAXL];
char res[MAXL];
double exp_freq[MAXN];
double freq[MAXN];

void input() {
  ifstream fin("sifra.in");
  fin >> n;
  // ucitavamo ocekivane frekvencije
  for (int i = 0; i < n; i++) {
    fin >> c[i] >> exp_freq[i];
    freq[i] = 0;
    exp_freq[i] /= 100.;
  }
  fin >> l;
  // ucitavamo poruku i azuriramo frekvencije
  for (int i = 0; i < l; i++) {
    fin >> s[i];
    for (int j = 0; j < n; j++)
      if (s[i] == c[j]) {
        index[i] = j;
        freq[j] ++;
      }
  }
  for (int i = 0; i < n; i++)
    freq[i] /= n;
  fin.close();
}

int nzd(int a, int b) {
  if (a ==0) return b;
  if (a < b) 
    return nzd(b%a, a);
  else 
    return nzd(a%b, b); 
}

void resi() {
  double minqual = 1e15;
  int bestA, bestB;
  for (int b = 1; b < n; b++)
    if (nzd(b, n) == 1)
      for (int a = 0; a < n; a++) {
        double qual = 0;
        for (int i = 0; i < n; i++) {
          int m = (i * b + a) % n;
          qual += (freq[i] - exp_freq[m]) * (freq[i] - exp_freq[m]);
        }
        if (qual < minqual) {
          minqual = qual;
          bestA = a;
          bestB = b;
        }
      }
  for (int i = 0; i < l; i++)
    for (int j = 0; j < n; j++)
      if (c[j] == s[i]) {
        res[i] = c[(j*bestB+bestA)%n];
      }
  res[l] = 0;

}

void output() {
  ofstream fout("sifra.out");
  fout << res << endl;
  fout.close();
}

int main() {
  input();
  resi();
  output();
  return 0;
}