telecomanda

Cu ocazia olimpiadei, televiziunea locală organizează un nou joc în direct. Organizatorii utilizează un calculator, care generează și afiseaza pe un monitor două numere N1 și N2.

Fiecare concurent dispune de o telecomandă prevazută cu un afișaj de o cifră și cu anumite taste, ca în figura alăturată. Telecomanda are și o memorie, în care sunt reținute în ordine cifrele obtinuțe de concurenți.



Cifrele primului numar 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 telecomanda. 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 urmatoarele:

• + urmat de o cifră - Se generează suma dintre cifra de pe afișaj și cifra tastată (operație posibilă doar dacă suma este tot o cifră). Cifra sumă este reținută în memorie.

$\\$

• – urmat de o cifră - Se generează diferența dintre cifra de pe afișaj și cifra tastată (operație posibilă doar dacă se obține tot o cifră). Cifra obținută este reținută în memorie.

$\\$

• * urmat de o cifră - Se reține în memorie valoarea tastei care se acționează după tasta *. Deoarece asupra cifrei curente din N1 nu se efectuează nicio operație, aceasta nu dispare de pe afișaj.

$\\$

• / - Se șterge cifra curentă din N1

$\\$

• # - Se șterg din N1 cifra curentă și toate cifrele care urmează, până la sfârșit.

$\\$

• = - Se copiază în memorie cifra curentă.

$\\$

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 numarului 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ța

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 pe prima linie numărul N1 și pe a doua linie numărul N2.

Date de ieșire

Fișierul de ieșire telecomanda.out conține două linii:

min
$t_1t_2...t_{min}$

unde n este un număr natural nenul, reprezentând numărul minim de taste acționate pentru transformarea lui N1 în N2. $t_1t_2...t_{min}$ este o succesiune de min caractere, care reprezintă tastele acționate; între caractere nu se vor pune separatori.

Restricții și precizări

• 1 ≤ numărul de cifre ale fiecărui număr ≤ 5000
• Problema a fost modificată
• Se acordă 30% din punctaj pentru afișarea numărului de pași corecți
• Pentru 50% din teste avem 1 ≤ numărul de cifre ale fiecărui număr ≤ 100

Exemplu

telecomanda.in

372
78

telecomanda.out

4
/=+6

Explicații

Soluția optimă efectuează 4 pași.
Sărim peste prima cifră din N1 apăsând /, luăm noua cifră curentă din N1 apăsând = (obținând 7 în memorie) iar apoi adunăm 6 la ultima cifră din N1 apăsând +6 (obținând 78 în memorie), prelucrând toate cifrele din N1 și obținând N2.
Alte soluții ar fi /=*8/, +4+1/, +4+1# sau *7*8#, care au 5 pași și nu sunt optime.