# PBinfo #3447 – Partit – Rezolvare C++

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

## Enunț

O partiție a unui număr natural n se definește ca o mulțime ordonată de numere naturale nenule (p1 , p2, … , pk) ce conține cel puțin două elemente, îndeplinind condiția: p1 +p2 +...+pk=n.

Să considerăm pentru un număr natural n toate partițiile luate în ordine lexicografică.

De exemplu, pentru numărul natural n=4 există 7 partiții. Le scriem în ordine lexicografică într-o listă pe care o vom numi în continuare tabel lexicografic.



 Nr. ordine 
 Partiție 


 1 
 1 1 1 1 


 2 
 1 1 2 


 3 
 1 2 1 


 4 
 1 3 


 5 
 2 1 1 


 3 
 2 2 


 7 
 3 1 


Cerința
Cunoscând valoarea numărului natural n:


pentru un număr k dat, să se tipărească partiția de pe poziția k din tabelul lexicografic.
pentru o partiție dată, să se calculeze numărul de ordine a ei din tabelul lexicografic

Date de intrare
Fișierul de intrare partit.in conține pe prima numărul c, reprezentând cerința de rezolvat. Dacă c=1, se va rezolva cerința 1, iar dacă c=2, se va rezolva cerința 2.

Pe linia a doua se găsește valoarea lui n – numărul pe care trebuie să îl descompunem.

Pe linia a treia, în funcție de valoarea lui c, putem avea


dacă c=1, pe linia 3 se găsește un număr natural k, reprezentând un număr de ordine,
dacă c=2, pe linia 3 se găsesc numere naturale separate prin câte un spațiu, reprezentând o partiție a numărului n.

Date de ieșire
Fișierul de ieșire partit.out va avea următorul conținut în funcție de valoarea lui c:


dacă c=1, pe prima linie se va tipări partiția cu numărul k în ordine lexicografică, numerele vor fi separate prin câte un spațiu;
dacă c=2, pe prima linie se va tipări numărul de ordine k al partiției citite.

Restricții și precizări

1 < n < 10 000
0 < k < 1017 (indiferent dacă este cazul c=1 sau c=2)
pentru teste în valoare de 18 puncte avem n ≤ 20
pentru alte teste în valoare de 36 de puncte avem n < 10 000 și k ≤ 1 000 000
pentru alte teste în valoare de 18 puncte avem k ≤ 2 000 000 000
pentru toate testele din fișierele de intrare există soluție
în concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1
partit.in

1
4
5
partit.out

2 1 1
Exemplul 2
partit.in

2
21
1 2 3 4 5 6
partit.out

375776

## Cod sursă C++

```cpp
/// prof. Szabo Zoltan
/// ISJ Mures Tg Mures 
#include <fstream>
using namespace std;
ifstream fin ("partit.in");
ofstream fout("partit.out");
int main()
{
    long long n,k,cazuri,t;
    int opt;
    fin>>opt;
    if(opt==1)
    {
        fin>>n>>k;
///        fout<<2<<" "<<n<<endl;
        t=1;
        while (n>63)
        {
            fout<<1<<" ";
            n--;
        }
        cazuri=1LL<<(n-1);
        while(cazuri>=1)
        {
            if (k==1)
            {
                fout<<t<<" ";
                while (cazuri>1)
                {
                    fout<<1<<" ";
                    cazuri=cazuri/2;
                }
                fout<<"\n";
            }
            else
                if (k<=cazuri/2)
                {
                    fout<<t<<" ";
                    t=1;
                }
                else
                {
                    t++;
                    k=k-cazuri/2;
                }
            cazuri=cazuri/2;
        }
    }
    else
    {
        fin>>n;
        k=0;
        while(fin>>t)
        {
            if(t>1)
            {
                cazuri=1LL<<(n-1);
                for(long long i=1;i<t;i++)
                {
                    cazuri/=2;
                    k+=cazuri;
                }
            }
            n-=t;
        }
        fout<<k+1;
    }
    return 0;
}
```

## Resurse

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