avere

Italag a fost toată viaţa pasionat de speculaţii bursiere reuşind să adune o avere considerabilă. Fiind un tip original şi pasionat de matematică a scris un testament inedit. Testamentul conţine două numere naturale: $S$ reprezentând averea ce trebuie împărţită moştenitorilor şi $N$ reprezentând alegerea sa pentru împărţirea averii. Italag decide să-şi împartă toată averea, iar sumele pe care le acordă moştenitorilor să fie în ordine strict descrescătoare.

De exemplu dacă averea ar fi $7$ unităţi monetare, ar putea fi împărţită astfel:

• $4$ (unităţi primului moştenitor) $3$ (unităţi celui de-al doilea), sau
• $6$ (unităţi primului moştenitor) $1$ (unitate celui de-al doilea), sau
• $7$ (doar primului moştenitor), sau
• $5$ (unităţi primului moştenitor) $2$ (unităţi celui de-al doilea), sau
• $4$ (unităţi primului moştenitor) $2$ (unităţi celui de-al doilea) $1$ (unitate celui de-al treilea).

Văzând că îi este foarte greu să verifice dacă nu cumva a omis vreo variantă de împărţire, Italag le-a scris în ordine lexicografică. Pentru exemplul de mai sus: $4 \ 2 \ 1$; $4 \ 3$; $5 \ 2$; $6 \ 1$; $7$.

A hotărât ca banii să fie distribuiţi conform celei de-a $N$-a posibilităţi din ordinea lexicografică.

Cerinţă

Scrieţi un program care pentru numerele $S$, $N$ date să calculeze şi să afişeze numărul total de posibilităţi de împărţire a averii, precum şi modul în care se face această împărţire conform cu a $N$–a posibilitate din ordinea lexicografică.

Date de intrare

Fişierul de intrare avere.in conţine o singură linie pe care se află două numere naturale separate printr-un singur spaţiu:

• primul număr ($S$) reprezintă suma totală
• cel de-al doilea ($N$) reprezintă numărul de ordine al poziţiei căutate

Date de ieșire

Fişierul de ieşire avere.out va conţine două linii:

• pe prima linie va fi afişat numărul total de modalităţi de împărţire a averii;
• pe cea de-a doua linie va fi afişată a $N$-a posibilitate de împărţire a lui $S$ conform cerinţei în ordine lexicografică. Elementele sale vor fi separate prin câte un spaţiu.

Restricții și precizări

• $1 < S < 701$
• $0 < N <$ numărul total de posibilităţi cu suma $S$
• Se acordă punctaj parţial pentru fiecare test: $50\%$ pentru determinarea corectă a numărului de posibilităţi de împărţire a lui $S$ şi $50\%$ pentru determinarea corectă a posibilităţii $N$, din ordinea lexicografică.
• Posibilităţile de împărţire a averii sunt numerotate începând cu $1$.
• Fie $x = (x_1, x_2 \dots, x_m)$ şi $y = (y_1, y_2, \dots, y_p)$ două şiruri. Spunem că $x$ precedă pe $y$ din punct de vedere lexicografic, dacă există $k \geq 1$, astfel încât $x_i = y_i$, pentru orice $i$ de la $1$ la $k-1$ şi $x_k < y_k$. Exemplu: $4 \ 2 \ 1$ precedă secvenţa $4 \ 3$ deoarece ($4=4, 2<3$), iar $6 \ 1$ precedă $7$ deoarece $6 < 7$.

Exemplul 1

avere.in

7 2

avere.out

5
4 3

Exemplul 2

avere.in

12 5

avere.out

15
6 5 1 

Exemplul 3

avere.in

700 912345678912345678

avere.out

962056220379782044
175 68 63 58 54 45 40 36 34 32 20 18 17 14 11 9 3 2 1