fbpx

Problema #323 – PartitiiNumar3 – Rezolvari PBInfo

de Mihai-Alexandru

Cerinţa

Se dă un număr natural n şi un interval [a,b]. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale din intervalul [a,b].

Date de intrare

Fişierul de intrare partitiinumar3.in conţine pe prima linie numerele n, a şi b.

Date de ieşire

Fişierul de ieşire partitiinumar3.out va conţine pe pe fiecare linie câte un şir de numere naturale din intervalul [a,b], ordonate crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n. Şirurile vor fi afişate în ordine lexicografică.

Restricţii şi precizări

  • 1 ≤ a < b < n ≤ 40

Exemplu

partitiinumar3.in

10 2 4

partitiinumar3.out

2 2 2 2 2 
2 2 2 4 
2 2 3 3 
2 4 4 
3 3 4 
#include <bits/stdc++.h>
using namespace std;

ifstream cin("partitiinumar3.in");
ofstream cout("partitiinumar3.out");

int n , x[50] , a , b;

void afisare(int k)
{
    for(int i = 1 ; i <= k ; i++)
        cout << x[i] << " ";
    cout << '\n';
}

void back(int k , int sp)
{
    for(int i = a ; i <= b ; i++)
    {
        x[k] = i;
        if(k == 1 || x[k] >= x[k - 1])
        {
            sp += x[k];
            if(sp <= n)
                if(sp == n) afisare(k);
                else back(k + 1 , sp);
            sp -= x[k];
        }
    }
}

int main()
{
    cin >> n >> a >> b;
    back(1 , 0);

}
Comentarii

S-ar putea sa iti placa