Fișierul intrare/ieșire cifru2.in, cifru2.out Sursă OJI 2012 clasa a 6-a
Autor Alin Burță Adăugată de avatar Isabela_coman Coman Isabela Patricia Isabela_coman
Timp de execuție pe test 0.3 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Cifru2 (clasa a 6-a)

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ă:

a) cifra cea mai mare care apare pe discurile cifrului în forma inițială;
b)
b1) 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;
b2) cifra cea mai mică ce se poate obține în urma efectuării numărului minim de mutări determinat;
b3) 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 cifru2.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 cifru2.out se vor afișa, pe linii separate, cele 4 valori solicitate.

Restricții

  • 1 < N ≤ 100 000
  • Un disc poate să rămână nemișcat.
  • Pentru rezolvarea corectă a cerinței a) se acordă 20% din punctajul fiecărui test
  • Pentru rezolvarea corectă a cerinței b1) se acordă 40% din punctajul fiecărui test
  • Pentru rezolvarea corectă a cerinței b2) se acordă 20% din punctajul fiecărui test
  • Pentru rezolvarea corectă a cerinței b3) se acordă 20% din punctajul fiecărui test.

Exemplu

cifru2.in cifru2.out Explicație
4
7
3
9
0
9
7
0
2
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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii