OJI 2012 VI | cifru

Costel a descoperit într-o debara servieta cu cifru a tatălui său. Cifrul este compus din $4$ discuri metalice pe care sunt inscripționate cifrele de la $0$ la $9$. Fiecare disc se poate mișca individual, de sus în jos sau de jos în sus, formându-se combinații de cifre. De multe ori, datorită comodității, combinația ce permite deschiderea servietei este formată numai din cifre identice: $0000, 1111$ etc.

Costel își imaginează un cifru compus din $N$ discuri metalice, fiecare având inscripționate cifrele de la $0$ la $9$, fiecare putând fi deplasat în cele două direcții specificate anterior. Prin mutare Costel înțelege deplasarea unui disc în sus sau în jos, cu o singură poziție, adică deplasarea discului până la cifra precedentă, respectiv următoare celei curente.

Cerință

Realizați un program care, cunoscând poziția inițială a fiecărui disc dintre cele N discuri ale cifrului, determină și afișează:

1. cifra cea mai mare care apare pe discurile cifrului în forma inițială;
2. numărul minim de mutări necesare pentru ca numărul obținut pe cifru să fie compus numai din cifre identice, număr necesar deschiderii servietei;
3. cifra cea mai mică ce se poate obține în urma efectuării numărului minim de mutări determinat;
4. numărul de combinații formate din cifre identice, care se poate obține în urma efectuării numărului minim de mutări determinat.

Date de intrare

Fișierul cifru.in conține:

• pe prima linie numărul natural $N$ reprezentând numărul discurilor;
• pe următoarele $N$ linii câte o cifră, reprezentând cifra curentă de pe fiecare disc al cifrului.

Date de ieșire

În fișierul de ieșire cifru.out se vor afișa, pe linii separate, cele $4$ valori solicitate.

Restricții și precizări

• $1 < N \leq 100 \ 000$;
• Un disc poate să rămână nemișcat.
• Pentru rezolvarea corectă a cerinței $1$ se acordă $20\%$ din punctajul fiecărui test
• Pentru rezolvarea corectă a cerinței $2$ se acordă $40\%$ din punctajul fiecărui test
• Pentru rezolvarea corectă a cerinței $3$ se acordă $20\%$ din punctajul fiecărui test
• Pentru rezolvarea corectă a cerinței $4$ se acordă $20\%$ din punctajul fiecărui test

Exemplu

cifru.in

4
7
3
9
0

cifru.out

9
7
0
2

Explicație

Avem un cifru cu $4$ discuri. Inițial, cifrul este în starea $7390$ (primul disc este poziționat pe cifra $7$, al doilea pe cifra $3$ etc.) Cea mai mare cifră de pe cifru este cifra $9$.
Numărul minim de mutări este $7$ și se poate obține în două moduri:

1. Deplasăm primul disc cu $2$ poziții în sus, al doilea disc cu $4$ poziții în jos, al treilea rămâne nemișcat, iar ultimul se deplasează cu o poziție în jos. Combinația obținută este $9999$.
2. Deplasăm primul disc cu $3$ poziții în sus, al doilea disc cu $3$ poziții în jos, al treilea cu o poziție în sus, iar ultimul rămâne nemișcat. Combinația obținută este $0000$. Astfel, cifra cea mai mică ce formează combinația cu număr minim de mutări este $0$. Avem $2$ combinații care se pot obține în numărul minim de mutări determinat: $0000$ și $9999$.