Cu ocazia olimpiadei, televiziunea locală organizează un nou joc în direct. Organizatorii utilizează un calculator, care generează şi afişează pe un monitor două numere N1 şi N2.
Fiecare concurent dispune de o telecomandă prevăzută cu un afişaj de o cifră şi cu anumite taste, ca în figura următoare. Telecomanda are şi o memorie, în care sunt reţinute în ordine cifrele obţinute de concurenţi.
Cifrele primului număr (N1) sunt afişate succesiv pe afişajul telecomenzii fiecărui concurent, în ordine de la stânga la dreapta. Concurenţii trebuie să transforme primul număr, obţinând în memoria telecomenzii proprii pe cel de al doilea, utilizând tastele pe care le au la dispoziţie pe telecomandă. După efectuarea unei operaţii asupra cifrei curente (cea de pe afişaj), pe afişaj apare automat următoarea cifră din N1 (dacă mai există).
Efectele apăsării tastelor sunt următoarele:
Acţiunea se încheie atunci când toate cifrele lui N1 au fost prelucrate. Am obţinut o soluţie când în memoria telecomenzii se află cifrele numărului N2. O soluţie este optimă dacă numărul de taste acţionate este minim. Câştigătorii jocului sunt acei concurenţi care descoperă o soluţie optimă.
Cerinţă
Date fiind N1 şi N2, scrieţi un program care să determine o soluţie optimă de transformare a numărului N1 în numărul N2.
Date de intrare
Fişierul de intrare telecomanda.in conţine două numerele N1 şi N2, câte un număr pe o linie.
Date de ieşire
Fişierul de ieşire telecomanda.out va conţine două linii. Pe prima linie va fi afişat numărul natural min, reprezentând numărul minim de taste acţionate pentru transformarea lui N1 în N2. Pe cea de a două linie va fi afişată o succesiune de min caractere t1t2...tmin, care reprezintă tastele acţionate; între caractere nu se vor pune separatori.
