Avem la dispoziţie cartonaşe dreptunghiulare pe care sunt inscripţionate numere naturale şi o valoare dată x. Pornind de la un număr N de astfel de cartonaşe, aşezate alăturat şi considerate a forma nivelul de bază (notat cu 1), se formează următoarele N-1 niveluri după regulile de mai jos (a se vedea şi figura din exemplu pentru clarificare):
- numărul de cartonaşe de pe un nivel oarecare este cu 1 mai mic decât numărul de cartonaşe de pe nivelul imediat inferior
- numărul înscris pe orice cartonaş se obţine ca sumă a numerelor de pe cartonaşele peste care “se aşează”, cartonaşe aflate pe nivelul imediat inferior.
Pe fiecare nivel se calculează suma numerelor de pe toate cartonaşele. Se vor forma astfel N sume care se reprezintă fiecare în baza 2.
Exemplu:
Cerinţă
a) Să se afişeze numărul inscripţionat pe cartonaşul de pe ultimul nivel.
b) Să se precizeze numărul nivelului pe care se află valoarea dată x
c) Să se afişeze numerele nivelelor în ordinea descrescătoare a numărului de cifre egale cu 1 din reprezentarea în baza 2 a sumei fiecărui nivel. Dacă există două nivele cu sumă având acelaşi număr de cifre egale cu 1, se va afişa mai întâi nivelul cu numărul mai mic.
Date de intrare
În fişierul cartonas.in se află:
- pe prima linie un număr natural N care reprezintă numărul de cartonaşe ce formează nivelul 1 (nivelul de bază)
- pe a doua linie un număr natural x care reprezintă valoarea căutată
- pe a treia linie se află cele N numere de pe nivelul 1 (de bază), separate două câte două printr-un spaţiu
Date de ieşire
În fişierul cartonas.out se va scrie:
- pe prima linie numărul inscripţionat pe cartonaşul de pe ultimul nivel
- pe linia a doua se va afişa nivelul pe care se află valoarea căutată x
- pe linia a treia se vor afişa numerele de nivel în ordinea cerută, separate două câte două printr-un spaţiu
Restricţii
N număr natural mai mic sau egal cu 100 x este număr natural de maxim 7 cifre
Valorile de pe cartonaşe sunt numere naturale de maxim 7 cifre
Se ştie că există suficiente cartonaşe cu inscripţia oricărui număr necesar, numerele de pe nivelul de bază nu conduc la numere pe celelalte nivele care să aibă mai mult de 7 cifre, iar sumele de pe fiecare nivel au maxim 9 cifre.
Exemple
cartonas.in
cartonas.out
Explicaţii
4
8
1 2 3 2
18
3
2 3 4 1
Pe ultimul nivel se va găsi valoarea 18, iar valoarea 8 se găseşte pe nivelul al treilea, conform desenului şi cerinţelor.
Pe primul nivel S=1+2+3+2=8=10002, adică are o cifră 1
Pe al doilea nivel S=3+5+5=13=11012, adică are 3 cifre 1
Pe al treilea nivel S=8+10=100102, adică 2 cifre 1
Pe al patrulea nivel S=18=100102, adică 2 cifre 1
