# PBinfo #4345 – braduti – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 N beculeţe colorate b1,  b2, …, bN, 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ă 3 beculeţe bi1, bi2, bi3, în ordinea în care acestea sunt plasate pe bandă (i1 < i2 < i3) şi montează în bi2 pe tulpina bradului, bi1 în stânga, iar b3i în dreapta;
– pentru al doilea lanţ selectează apoi 5 beculeţe bj1, bj2, bj3, bj4, bj5, în ordinea de pe bandă (j1 < j2 < j3 < j4 < j5) şi montează bj3 pe tulpina bradului imediat sub bi2, în stânga bj1 şi bj2 (în această ordine), iar în dreapta bj4 şi bj5 (î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ța
Cunoscând numărul N de beculeţe aflate pe banda de asamblare, scrieţi un program care să rezolve următoarele două cerinţe:
1. determină înălţimea bradului (numărul de lanţuri ce pot fi construite cu cele N beculeţe);
2. determină numărul de brazi diferiţi ce pot fi construiţi cu cele N beculeţe.

Date de intrare
Fișierul de intrare braduti.in conţine pe prima linie numărul C care reprezintă cerinţa care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află numărul natural N 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 C.

Restricții și precizări

3 ≤ N ≤ 5555
Pentru teste valorând 10 puncte C = 1
Pentru teste valorând 20 de puncte, C = 2 şi rezultatul va avea cel mult 18 cifre
Pentru teste valorând 60 de puncte, C = 2 şi rezultatul va avea cel mult 10.000 cifre
10 puncte se acordă pentru exemplele din enunț.

Exemplul 1:
braduti.in

1
17
braduti.out

3
Explicație
Se va rezolva cerința 1. Numărul de lanţuri ce pot fi construite cu 17 beculeţe este 3. Beculeţele vor fi aranjate ca în desen.



Exemplul 2:
braduti.in

2
17
braduti.out

49008960
Explicație
Se va rezolva cerința 2. Se determină numărul de brăduţi diferiţi ce pot fi construiţi cu 17 beculeţe.

Exemplul 3:
braduti.in

2
5
braduti.out

10
Explicație
Se va rezolva cerința 2. Se determină numărul de brăduţi diferiţi ce pot fi construiţi cu 5 beculeţe.

## Cod sursă C++

```cpp
//prof. Em. Cerchez
#include <fstream>
#define LGMAX 10002
#define NMAX 5560
using namespace std;
ifstream fin("braduti.in");
ofstream fout("braduti.out");
typedef int NrMare[LGMAX];
int h(int N);
void nr(int N, NrMare rez, int& lgrez);
void scrie (NrMare rez, int lgrez);
void prod(NrMare a, int lga, int x, NrMare p, int& lgp);
void descompunere(int st, int dr, int semn);
int C, N;
NrMare rez, c, t;
int lgrez, lgc, lgt;
int p[NMAX];
int main()
{
  fin>>C>>N;
  if (C==1)
    fout<<h(N)<<'\n';
    else
    {nr(N, rez, lgrez);
     scrie(rez,lgrez);
    }
  fout.close();
  return 0;
}
int h(int N)
{int rez=0, pas=3;
 while (pas<=N) {rez++; N-=pas; pas+=2;}
 return rez;
}
void nr(int N, NrMare rez, int& lgrez)
{int pas=3, i, j;
 while (pas<=N)
       {//combinari de N luate cate pas
         descompunere(pas+1, N, 1);
         descompunere(2, N-pas, -1);
         N-=pas;
         pas+=2;
       }
 rez[0]=1; lgrez=1;
 for (i=2; i<NMAX; i++)
     for (j=0; j<p[i]; j++)
         prod(rez,lgrez,i,rez,lgrez);
}
void scrie (NrMare rez, int lgrez)
{int i;
 for (i=lgrez-1; i>=0; i--) fout<<rez[i];
 fout<<'\n';
}
void descompunere(int st, int dr, int semn)
{int k, d, x;
 for (k=st; k<=dr; k++)
      {d=2; x=k;
       while (d*d<=x)
             {
               while (x%d==0)
                     {p[d]+=semn;
                      x/=d;}
               d++;
              }
       if (x>1) p[x]+=semn;
      }
}
void prod(NrMare a, int lga, int x, NrMare p, int& lgp)
{int t = 0, val, i;
 for (i=0; i<lga; i++)
     {
       val = a[i] * x + t;
       p[i] = val %10;
       t = val / 10;
    }
 lgp = lga;
 while (t)
      {
       p[lgp] = t%10;
       lgp++;
       t = t/10;
    }
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4345)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4345/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4345/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)