Lista de probleme 2

Ana şi Bogdan au inventat jocul “Compar”. Ana scrie pe tablă o secvenţă formată din N numere naturale distincte cuprinse între 1 şi N, apoi compară fiecare două numere învecinate din secvenţă scriind între ele semnul < sau semnul >, după caz.
De exemplu, dacă secvenţa de pe tablă este 6 4 2 1 3 5, după compararea elementelor învecinate şi inserarea semnelor în secvenţă, Ana obţine:
6>4>2>1<3<5
După aceea Ana şterge cele N elemente ale secvenţei şi păstrează numai semnele, astfel:
>>><<
La final, Ana îi arată lui Bogdan şirul semnelor şi îi cere să reconstituie secvenţa de numere naturale scrisă iniţial pe tablă.

Cunoscând şirul semnelor construit de Ana, scrieţi un program care să îl ajute pe Bogdan să reconstituie secvenţa de numere naturale distincte scrisă iniţial pe tablă.

Se consideră un şir A=(A1, A2, ..., AN), format din N numere naturale nenule. Două numere se consideră vecine dacă se află pe poziţii alăturate (Ai are ca vecini pe Ai-1 şi Ai+1, pentru orice 1<i<N, A1 are ca vecin doar pe A2, iar AN are ca vecin doar pe AN-1).

Dacă două elemente vecine Ai, Ai+1 (1≤i<N) au cel puţin o cifră comună, ele se pot unifica. Procedeul de unificare constă în eliminarea din numerele Ai şi Ai+1 a tuturor cifrelor comune şi adăugarea prin alipirea numărului obţinut din Ai+1 la numărul obţinut din Ai, formându-se astfel un nou număr. Numărul Ai va fi înlocuit cu noul număr, iar numărul Ai+1 va fi eliminat din şir.

De exemplu, numerele Ai=23814 şi Ai+1=40273 au cifrele 2, 3, 4 comune, după unificare obţinem Ai=817, iar Ai+1 este eliminat; observaţi că dacă după eliminarea cifrelor comune, numerele încep cu zerouri nesemnificative, acestea vor fi eliminate, apoi se realizează alipirea.

Dacă în urma eliminării cifrelor comune, unul dintre numere nu mai are cifre, atunci numărul rezultat va avea cifrele rămase în celălalt. Dacă în urma eliminării cifrelor comune atât Ai cât şi Ai+1 nu mai au cifre, atunci ambele numere vor fi eliminate din şir, fără a fi înlocuite cu o altă valoare.

Ordinea în care se fac unificările în şir este importantă: la fiecare pas se alege prima pereche de elemente vecine Ai Ai+1 care poate fi unificată, considerând şirul parcurs de la stânga la dreapta. (De exemplu, considerând Ai=123, Ai+1=234, Ai+2=235, se unifică Ai cu Ai+1 => Ai=14, iar unificarea cu următorul număr nu mai este posibilă).

Cunoscându-se şirul celor N numere naturale, să se determine:

a) cifra care apare cel mai frecvent în scrierea tuturor celor N numere; dacă există mai multe cifre cu aceeaşi frecvenţă de apariţie maximă, se va reţine cea mai mică cifră.
b) şirul obţinut prin efectuarea unui număr maxim de unificări, după regulile descrise în enunţ.