cifru

Time limit: 0.3s Memory limit: 2MB Input: cifru.in Output: cifru.out

Costel a descoperit într-o debara servieta cu cifru a tatălui său. Cifrul este compus din 44 discuri metalice pe care sunt inscripționate cifrele de la 00 la 99. 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,11110000, 1111 etc.

Costel își imaginează un cifru compus din NN discuri metalice, fiecare având inscripționate cifrele de la 00 la 99, 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 NN reprezentând numărul discurilor;
  • pe următoarele NN 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 44 valori solicitate.

Restricții și precizări

  • 1<N100 0001 < N \leq 100 \ 000;
  • Un disc poate să rămână nemișcat.
  • Pentru rezolvarea corectă a cerinței 11 se acordă 20%20\% din punctajul fiecărui test
  • Pentru rezolvarea corectă a cerinței 22 se acordă 40%40\% din punctajul fiecărui test
  • Pentru rezolvarea corectă a cerinței 33 se acordă 20%20\% din punctajul fiecărui test
  • Pentru rezolvarea corectă a cerinței 44 se acordă 20%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 44 discuri. Inițial, cifrul este în starea 73907390 (primul disc este poziționat pe cifra 77, al doilea pe cifra 33 etc.) Cea mai mare cifră de pe cifru este cifra 99.
Numărul minim de mutări este 77 și se poate obține în două moduri:

  1. Deplasăm primul disc cu 22 poziții în sus, al doilea disc cu 44 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 99999999.
  2. Deplasăm primul disc cu 33 poziții în sus, al doilea disc cu 33 poziții în jos, al treilea cu o poziție în sus, iar ultimul rămâne nemișcat. Combinația obținută este 00000000. Astfel, cifra cea mai mică ce formează combinația cu număr minim de mutări este 00. Avem 22 combinații care se pot obține în numărul minim de mutări determinat: 00000000 și 99999999.

Log in or sign up to be able to send submissions!