Trgovac Joca je u svojoj radnji uveo sistem multiplikativnih cena. Naime, za svaki artikal postoji osnovna cena i Jocina marža, a kupac je dužan da za artikal plati iznos jednak njihovom proizvodu. Trgovac Joca trenutno vrši popis i postavlja nove cene. Za jedan artikal on ima određeni broj pločica, pri čemu je na svakoj ispisana po jedna cifra. Od tih pločica on želi da sastavi osnovnu cenu i maržu za taj artikal tako da iznos koji kupac mora da plati za njega bude maksimalan. S obzirom da je on sva računanja obavio na papiru, on vas je zamolio da vi na računaru nađete poslednje cifre tog maksimalnog iznosa, na osnovu koga će on proveriti ispravnost svog računanja. I cena i marža moraju da sadrže makar jednu pločicu.

Ulaz:

U prvom redu ulaznog tekstualnog fajla proizvod.in nalaze se dva prirodna broja N i M razdvojenih blanko znakom ( 2 ≤ N ≤ 105, 1 ≤ M ≤ 8 ). N predstavlja broj pločica za dati artikal, a M predstavlja broj poslednjih cifara maksimalnog iznosa koje interesuju trgovca Jocu. U drugom redu nalazi se N dekadnih cifara koje predstavljaju cifre na pločicama. Pre i između cifara u drugom redu ne postoji ni jedan blanko znak.

Izlaz:

U prvi i jedini red izlaznog tekstualnog fajla proizvod.out upisati poslednjih M cifara maksimalnog iznosa koji se za dati artikal može dobiti pomoću zadatih pločica. Ukoliko je broj cifara maksimalnog iznosa manji od M, onda upisati ceo iznos dopunjen vodećim nulama tako da je ukupan broj cifara u ispisu jednak M. Pre i između cifara ne upisivati ni jedan blanko znak.

Primer:

4 2
2397

16

Objašnjenje:

Najveći iznos se dobija ako je osnovna cena 92, a Jocina marža 73 (ili obrnuto). Tada je iznos 6716, a u ispisu se prikazuju poslednje dve cifre, tj. 16.

Primer:

3 3
501

050

Objašnjenje:

Najveći iznos se dobija ako je osnovna cena 5, a Jocina marža 10 (ili obrnuto); ili ako je osnovna cena 50, a marža 1 (ili obrnuto). Tada je iznos 50, a u ispisu se prikazuje pun iznos sa dopisanom jednom nulom, tj. 050.

Problem opisan u zadatku se može iskazati kao problem sastavljanja dva broja od zadatih cifara, tako da je njihov proizvod maksimalan. Neka su to brojevi A i B i neka se oni mogu napisati kao:

A=a_na_n-1…a₁a₀ i B=b_mb_m-1…b₁b₀

Očigledno je da će u oba broja cifre biti poređane u nerastućem redosledu, posmatrajući počev od cifre najveće težine, odnosno:

a_n≥a_n-1≥…≥a₁≥a₀ i b_m≥b_m-1≥…≥b₁≥b₀

Neka su na raspolaganju cifre (bez gubljenja opštosti možemo ih posmatrati u uređenom redosledu):

c_t≥c_t-1≥…≥c₁≥c₀ (t=n+m+1)

Naš zadatak možemo posmatrati kao određivanje koja cifra pripada kom od dva broja, pošto znamo kako se cifre raspoređuju unutar jednog broja. Radi lakšeg zapisa, uvedimo da oznaka A_i,j predstavlja broj a_ia_i-1...a_j+1a_j i analognu oznaku B_i,j.

Očigledno, najveća data cifra mora biti cifra najveće težine jednog od ova dva broja. Neka je to broj A. Dakle, c_t≥a_n. Pokušajmo da utvrdimo kom broju pripada cifra c_t-1. Postoje dve mogućnosti: c_t-1≥b_m ili c_t-1≥a_n-1. Dokazaćemo da je c_t-1≥b_m. Pretpostavimo suprotno, tj. da je c_t-1≥a_n-1. Tada je proizvod brojeva A i B:

AB⁽¹⁾=(c_t10ⁿ+c_t-110^n-1+A_n-2,0) (b_m10^m+B_m-1,0)=c_tb_m10^n+m+c_t10ⁿB_m-1,0+c_t-1b_m10^n+m-1+c_t-110^n-1B_m-1,0+A_n-2,0b_m10^m+A_n-2,0B_m-1,0

Ako bi cifre a_n-1 i b_m zamenile mesta, dobili bismo proizvod:

AB⁽²⁾=(c_t10ⁿ+b_m10^n-1+A_n-2,0) (c_t-110^m+B_m-1,0)=c_tc_t-110^n+m+c_t10ⁿB_m-1,0+b_mc_t-110^n+m-1+b_m10^n-1B_m-1,0+A_n-2,0c_t-110^m+A_n-2,0B_m-1,0

Razliku ovih proizvoda možemo pisati kao:

AB⁽²⁾ – AB⁽¹⁾=c_t10^n+m(c_t-1-b_m)+10^n-1B_m-1,0(b_m-c_t-1)+A_n-2,010^m(c_t-1-b_m) =(c_t-1-b_m) (c_t10^n+m-10^n-1B_m-1,0+10^mA_n-2,0)

S obzirom na to što je c_t-1≥b_m, izraz u prvoj zagradi je nenegativan. Ako je c_t≥0, onda je i B_m-1,0≥0 (nijedna cifra u B nije veća od c_t), pa je i izraz u drugoj zagradi nenegativan (tačnije jednak 0). Ako je c_t > 0, onda je c_t10^n+m≥10^n+m, a pošto iz B_m-1,0 < 10^m sledi 10^n-1B_m-1,0 < 10^n+m-1, tada je c_t10^n+m-10^n-1B_m-1,0>10^n+m-10^n+m-1 > 0, pa je i u ovom slučaju izraz u drugoj zagradi nenegativan (u ovom slučaju strogo pozitivan). Time smo dokazali da uvek važi:

AB⁽²⁾ – AB⁽¹⁾≥0

Samo za c_t-1=b_m važi znak jednakosti. Za c_t-1 > b_m važi da je AB⁽²⁾ – AB⁽¹⁾ > 0, što je kontradikcija našem izboru lokacije za cifru c_t-1. Dakle, potrebno je odabrati c_t-1≥b_m.

Pretpostavimo da smo rasporedili cifre c_t,...,c_k+1 među ciframa a_n,...,a_i+1,b_m,...,b_j+1 (t – k=n – i+m – j). Za cifru c_k mora važiti c_k≥b_j ili c_k≥a_i. Ukoliko je A_n,i+1 ≥ B_m,j+1, prethodni izbor je proizvoljan (zbog simetrije). U suprotnom, bez gubljenja opštosti, pretpostavimo da je A_n,i+1> B_m,j+1. Dokazaćemo da je tada c_k≥b_j. Pretpostavimo suprotno, tj. da je c_k≥a_i. Tada je proizvod brojeva A i B:

AB⁽¹⁾=(A_n,i+110ⁱ⁺¹+c_k10ⁱ+A_i-1,0) (B_m,j+110^j+1+b_j10^j+B_j-1,0) =A_n,i+1B_m,j+110^i+j+2+A_n,i+1b_j10^i+j+1+A_n,i+1B_j-1,010ⁱ⁺¹+c_kB_m,j+110^i+j+1+c_kb_j10^i+j+ c_kB_j-1,010ⁱ+A_i-1,0B_m,j+110^j+1+A_i-1,0b_j10^j+A_i-1,0B_j-1,0

Ako bi cifre a_i i b_j zamenile mesta, dobili bismo proizvod:

AB⁽¹⁾=(A_n,i+110ⁱ⁺¹+b_j10ⁱ+A_i-1,0) (B_m,j+110^j+1+c_k10^j+B_j-1,0) =A_n,i+1B_m,j+110^i+j+2+A_n,i+1c_k10^i+j+1+A_n,i+1B_j-1,010ⁱ⁺¹+b_jB_m,j+110^i+j+1+b_jc_k10^i+j+ b_jB_j-1,010ⁱ+A_i-1,0B_m,j+110^j+1+A_i-1,0c_k10^j+A_i-1,0B_j-1,0

Razliku ovih proizvoda možemo pisati kao:

AB⁽²⁾-AB⁽¹⁾=A_n,i+110^i+j+1(c_k-b_j)+B_m,j+110^i+j+1(b_j-c_k)+B_j-1,010ⁱ(b_j-c_k)+A_i-1,010^j(c_k-b_j) =(c_k – b_j) (A_n,i+110^i+j+1-B_m,j+110^i+j+1 - B_j-1,010ⁱ+A_i-1,010^j)

S obzirom na to što je c_k≥b_j, izraz u prvoj zagradi je nenegativan. S obzirom na to što je An,i+1>B_m,j+1, važi:

A_n,i+110^i+j+1-B_m,j+110^i+j+1=(A_n,i+1-B_m,j+1)10^i+j+1≥10^i+j+1

S druge strane je B_j-1,0 < 10^j, pa je B_j-1,010ⁱ < 10^i+j. Odatle je

A_n,i+110^i+j+1-B_m,j+110^i+j+1-B_j-1,010ⁱ > 10^i+j+1-10^i+j > 0,

pa je izraz u drugoj zagradi pozitivan. Time smo dokazali da uvek važi:

AB⁽²⁾ – AB⁽¹⁾≥0

Samo za c_k=b_j važi znak jednakosti. Za c_k>b_j važi da je AB⁽²⁾ – AB⁽¹⁾ > 0, što je kontradikcija našem izboru lokacije za cifru c_k. Dakle, potrebno je odabrati c_k≥b_j.

Sada možemo sastaviti algoritam:

	sortirati niz cifara c u opadajući poredak c[t]≥c[t-1]≥…≥c[1]≥c[0];
	A=c[t]t;
	B=c[t-1];
	za svako i od t-2 do 0 uraditi:
		ako je A≥B, dopisati cifru c[i] broju B sa desne strane;
		u suprotnom, dopisati cifru c[i] broju A sa desne strane;
	D=A * B;
	rezultat=D mod 10^(broj cifara ispisa)
	dopisati odgovarajući broj nula rezultatu sa leve strane

Nakon raspoređivanja cifara c_t i c_t-1 važi A≥B i cifra c_t-2 će biti dopisana broju B, a potom će cifra c_t-3 biti dopisana broju A pošto je broj B veći jer ima veći broj cifara (napomena: A će biti veći ako je c_t > 0, a c_t-1≥0, ali tada su i sve cifre nadalje jednake 0 i svejedno je kom broju se dopisuju). Nakon raspoređivanja cifara c_t-2 i c_t-3, brojevi A i B će imati isti broj cifara. Ako posmatramo naredne dve cifre (c_t-4 i c_t-5), c_t-4 će biti dopisana manjem (ili jednakom) broju, a c_t-5 onom drugom broju. Na taj način, proces dopisivanja cifara možemo raditi u parovima (osim eventualno poslednje cifre).

Pogodno je da relaciju između brojeva A i B određujemo iterativno nakon svakog para cifara, dakle samo na osnovu dopisanih cifara. To možemo uraditi uvođenjem logic_ke premenljive jednaki koja ima vrednost true dok god su brojevi A i B jednaki, pri čemu vodimo računa da u slučaju nejednakosti uvek znamo koji je broj veći (recimo A).

Takođe, nije pogodno množenje brojeva A i B, jer oni mogu biti jako veliki i, s obzirom na to što je algoritam množenja velikih brojeva kvadratne složenosti poo broju njihovih cifara, vreme izvršenja ovog algoritma bilo bi jako veliko. Međutim, s obzirom na to što je potrebno odrediti samo zadnjih M≤8 cifara proizvoda, dovoljno je pomnožiti poslednjih M cifara brojeva A i B, odnosno naći poslednjih M cifara tog proizvoda. Zgodno je, prilikom množenja, sve operacije obavljati po modulu 10^m. Direktno množenje brojeva A_M-1,0 i B_M-1,0 premašuje opseg 32-bitnog celobrojnog tipa. To nas navodi na množenje jednog od ova dva broja, recimo A_M-1,0, ciframa drugog broja, pri čemu se sve operacije obavljaju po modulu 10^m.

Konačno, algoritam se može napisati ovako:

	sortirati niz cifara c u opadajući poredak c[t]≥c[t-1]≥…≥c[1]≥c[0];
	A=c[t];
	B=c[t-1];
	ako je c[t]=c[t-1], jednaki=true;
	u suprotnom, jednaki=false i veciJeA=true;
	za svako i od t-2 do 0 sa korakom 2 uraditi:
		ako je  jednaki=true, uraditi sledeće:
			dopisati cifru c[i] broju A sa desne strane;
			ako je i-1≥0 uraditi:
				dopisati cifru c[i-1] broju B sa desne strane;
				ako je c[i]>c[i-1], jednaki=false;
		u suprotnom (jednaki=false),  uraditi sledeće:
			dopisati cifru c[i] broju B sa desne strane;
			ako je i-1≥0, dopisati cifru c[i-1] broju A sa desne strane;
	ako je n≥M-1,  ApoModulu=A[M-1,0];
	u suprtnom, ApoModulu=A;
	rezultat=0;
	za svako i od min(M-1, m) do 0 uraditi:
		rezultat=( 10 * rezultat+ApoModulu * B[i,i] ) mod 10^m
	dopisati odgovarajući broj nula rezultatu sa leve strane

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int rezultat;
vector<int> nizCifara;
vector<int> prviBroj;
vector<int> drugiBroj;

void ucitavanje()
{
  int i;
  char ch;

  ifstream inFile = ifstream("proizvod.in");
  
  inFile >> N >> M;

  do
  {
    inFile >> ch;
  } while ((ch < '0') || (ch > '9'));

  nizCifara.push_back((int)ch - 48);  

  for (i = 0; i < N - 1; i++)
  {
    inFile >> ch;
    nizCifara.push_back((int)ch - 48);
  }

  inFile.close();
}


void obrada()
{
  int i, j;
  int modul = 1;
  int prviBrojPoModulu;
  bool jednaki;
  
  for (i = 0; i < M; i++)
    modul *= 10;

  sort(nizCifara.begin(), nizCifara.end());

  prviBroj.push_back(nizCifara[N - 1]);
  drugiBroj.push_back(nizCifara[N - 2]);

  if (nizCifara[N - 1] == nizCifara[N - 2])
    jednaki = true;
  else
    jednaki = false;

  j = N - 3;
  
  // generisanje jednog i drugog broja od cifara
  while (j >= 0)
  {
    if (jednaki)
    {
      prviBroj.push_back(nizCifara[j]);
      j--;
      if (j >= 0)
      {
        drugiBroj.push_back(nizCifara[j]);
        if (nizCifara[j + 1] > nizCifara[j])
          jednaki = false;
        j--;
      }
    }
    else
    {
      drugiBroj.push_back(nizCifara[j]);
      j--;
      if (j >= 0)
      {
        prviBroj.push_back(nizCifara[j]);
        j--;
      }
    }
  }

  if (prviBroj.size() >= M)
    j = prviBroj.size() - M;
  else
    j = 0;

  prviBrojPoModulu = prviBroj[j];
  for (i = j + 1; i < prviBroj.size(); i++)
    prviBrojPoModulu = 10 * prviBrojPoModulu + prviBroj[i];

  if (drugiBroj.size() >= M)
    j = drugiBroj.size() - M;
  else
    j = 0;
  
  rezultat = 0;
  for (i = j; i < drugiBroj.size(); i++)
    rezultat = (10 * rezultat + prviBrojPoModulu * drugiBroj[i]) % modul;
}

void stampanje()
{
  ofstream outFile = ofstream("proizvod.out");

  int i;
  vector<int> cifreRezultata;

  while (rezultat > 0)
  {
    cifreRezultata.push_back(rezultat % 10);
    rezultat /= 10;
  }

  for (i = 0; i < M - cifreRezultata.size(); i++)
    outFile << 0;
  
  for (i = cifreRezultata.size() - 1; i >= 0; i--)
    outFile << cifreRezultata[i];

  outFile << endl;

  outFile.close();
}

int main()
{
  ucitavanje();
  obrada();
  stampanje();

  return 0;
}

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

int main() {

    long long N, d[100000], M, k=0, A[2]={0,0}; string s; bool b=1;

    cin >> N >> M >> s;
    for (int i=0; i<N && ((d[i]=s[i]-'0')||1); i++) {}

    sort(d, d+N); reverse(d,d+N);

    for (long i=0; i<N && ((A[k] = (A[k]*10 + d[i]) % 1000000000L)||1); i++)
        b = !(!(k=1-k) && b && (d[i]!=d[i-1]) && (k=1-k)) && b;

    cout << setfill('0') << setw(M) << (A[0] * A[1] % (long long)pow(10.0,(double)M)) << endl;
}