Problem partit


O partiție a unui număr natural n se definește ca o mulțime ordonată de numere naturale nenule \((p_1, p_2, … , p_k)\) ce conține cel puțin două elemente, îndeplinind condiția: \(p_1+p_2+...+p_k=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ția
1 1 1 1 1
2 1 1 2
3 1 2 1
4 1 3
5 2 1 1
6 2 2
7 3 1

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 < 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
  • se acordă 10 puncte din oficiu.

Exemple

partit.in

1
4
5

partit.out

2 1 1

partit.in

2
21
1 2 3 4 5 6

partit.out

375776

General info

ID: 18

Upload: liviu

Input: partit.in/partit.out

Memory limit: 32MB/32MB

Time limit: 0.1s

Author: Zoltan Szabo

Source: OJI 2020 XI-XII: Problema 2

Points by default: 10p

Submissions

Special Submissions