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

1 < S < 701
0 < N < numărul total de posibilităţi cu suma S
Se acordă punctaj parţial pentru fiecare test: 5 puncte pentru determinarea corectă a numărului de posibilităţi de împărţire a lui S şi 5 puncte 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 = (x1, x2 …, xm) şi y = (y1, y2, …, yp) două şiruri. Spunem că x precedă pe y din punct de vedere lexicografic, dacă există k≥1, astfel încât xi=yi, pentru orice i=1, k-1 şi xk<yk.
Exemplu: 4 2 1 precedă secvenţa 4 3 deoarece (4=4, 2<3), iar 6 1 precedă 7 deoarece 6<7.

Exemple

avere.in	avere.out
7 2	5 4 3
12 5	15 6 5 1
700 912345678912345678	962056220379782044 175 68 63 58 54 45 40 36 34 32 20 18 17 14 11 9 3 2 1

autor: Emilian Miron

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com