Fișierul intrare/ieșire	partit.in, partit.out	Sursă	OJI 2020, clasele 11-12
Autor	Zoltan Szabo	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.15 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Partit (clasele 11-12)

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.

Cerințe

Cunoscând valoarea numărului natural n:

1. pentru un număr k dat, să se tipărească partiția de pe poziția k din tabelul lexicografic.
2. 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 linie 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 < 10¹⁷ (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; Nerdarena acordă 10 puncte pentru exemple.

Exemplu