Telecomanda

Cu ocazia olimpiadei, televiziunea locala organizeaza un nou joc în direct. Organizatorii utilizeaza un calculator, care genereaza si afiseaza pe un monitor doua numere de maxim 100 de cifre fiecare (N1 si N2).

Fiecare concurent dispune de o telecomanda prevazuta cu un afisaj de o cifra si cu anumite taste, ca în figura alaturata. Telecomanda are si o memorie, în care sunt retinute în ordine cifrele obtinute de concurenti.

Cifrele primului numar (N1) sunt afisate succesiv pe afisajul telecomenzii fiecarui concurent, în ordine de la stânga la dreapta. Concurentii trebuie sa transforme primul numar, obtinând în memoria telecomenzii proprii pe cel de al doilea, utilizând tastele pe care le au la dispozitie pe telecomanda. Dupa efectuarea unei operatii asupra cifrei curente (cea de pe afisaj), pe afisaj apare automat urmatoarea cifra din N1 (daca mai exista).

Efectele apasarii tastelor sunt urmatoarele:

Taste actionate

Efect

+ urmat de o cifra

Se genereaza suma dintre cifra de pe afisaj si cifra tastata (operatie posibila doar daca suma este tot o cifra). Cifra suma este retinuta în memorie.

– urmat de o cifra

Se genereaza diferenta dintre cifra de pe afisaj si cifra tastata (operatie posibila doar daca se obtine tot o cifra). Cifra obtinuta este retinuta în memorie.

* urmat de o cifra

Se retine în memorie valoarea tastei care se actioneaza dupa tasta *. Deoarece asupra cifrei curente din N1 nu se efectueaza nici o operatie, aceasta nu dispare de pe afisaj.

/

Se sterge cifra curenta din N1

#

Se sterg din N1 cifra curenta si toate cifrele care urmeaza, pâna la sfârsit.

=

Se copiaza în memorie cifra curenta.

Actiunea se încheie atunci când toate cifrele lui N1 au fost prelucrate. Am obtinut o solutie când în memoria telecomenzii se afla cifrele numarului N2. O solutie este optima daca numarul de taste actionate este minim. Câstigatorii jocului sunt acei concurenti care descopera o solutie optima.

Cerinta

Date fiind N1 si N2, scrieti un program care sa determine o solutie optima de transformare a numarului N1 în numarul N2.

Date de intrare

Fisier de intrare TELE.IN contine doua linii:
N1
N2

Date de iesire

Fisier de iesire TELE.OUT contine doua linii:

min
t1t2...tmin

unde:

Exemplu

TELE.IN
372
78

TELE.OUT
4
/=+6

Timp maxim de executie/test: 1 secunda