Robotul Vasile s-a angajat la fabrica decoraţiunilor de Crăciun unicat. El trebuie să monteze beculeţe colorate în brăduţi, astfel încât oricare doi brăduţi să fie diferiţi.
Pe o bandă de asamblare robotul Vasile are la dispoziţie beculeţe colorate , astfel încât oricare două beculeţe sunt colorate diferit. În vârful bradului va pune o steluţă, iar pentru montarea beculeţelor în brăduţ el construieşte lanţuri de becuri în modul următor:
- pentru primul lanţ selectează beculeţe , în ordinea în care acestea sunt plasate pe bandă () şi montează în pe tulpina bradului, în stânga, iar în dreapta;
- pentru al doilea lanţ selectează apoi beculeţe , în ordinea de pe bandă () şi montează pe tulpina bradului imediat sub , în stânga şi (în această ordine), iar în dreapta şi (în această ordine);
- continuă în acelaşi mod, construind la fiecare pas un lanţ în care se selectează două becuri în plus faţă de lanţul precedent, respectând ordinea în care se află becurile pe banda de asamblare; becul situat la mijlocul lanţului este montat pe tulpină, imediat sub becul precedent, celelalte becuri fiind plasate în ordine în partea stângă, respectiv în partea dreaptă;
- procedeul se repetă până când numărul de becuri rămase pe banda de asamblare este insuficient pentru construirea unui nou lanţ.
Înălţimea bradului este considerată egală cu numărul de lanţuri construite (egal cu numărul de beculeţe montate pe tulpină). Doi brazi sunt diferiţi dacă există cel puţin o poziţie în care în cei doi brazi se află beculeţe de culori diferite.
Cerințe
Cunoscând numărul de beculeţe aflate pe banda de asamblare, scrieţi un program care să rezolve următoarele două cerinţe:
- determină înălţimea bradului (numărul de lanţuri ce pot fi construite cu cele beculeţe);
- determină numărul de brazi diferiţi ce pot fi construiţi cu cele beculeţe.
Date de intrare
Fişierul de intrare braduti.in
conţine pe prima linie numărul care reprezintă cerinţa care trebuie să fie rezolvată ( sau ). Pe a doua linie se află numărul natural care reprezintă numărul de beculeţe colorate de pe linia de asamblare.
Date de ieșire
Fişierul de ieşire braduti.out
va conţine o singură linie pe care va fi scris un număr natural reprezentând rezultatul determinat pentru cerinţa .
Restricții și precizări
- Pentru teste valorând puncte
- Pentru teste valorând de puncte, şi rezultatul va avea cel mult cifre
- Pentru teste valorând de puncte, şi rezultatul va avea cel mult cifre
- puncte se acordă din oficiu.
Exemplul 1
braduti.in
1
17
braduti.out
3
Explicație
Se va rezolva cerința . Numărul de lanţuri ce pot fi construite cu beculeţe este . Beculeţele vor fi aranjate ca în desen.
Exemplul 2
braduti.in
2
17
braduti.out
49008960
Explicație
Se va rezolva cerința . Se determină numărul de brăduţi diferiţi ce pot fi construiţi cu beculeţe.
Exemplul 3
braduti.in
2
5
braduti.out
10
Explicație
Se va rezolva cerința . Se determină numărul de brăduţi diferiţi ce pot fi construiţi cu beculeţe.