Problemă de concurs certificată de InfoAs: Soluțiile tale trimise la această problemă sunt evaluate în exact același mediu ca și la concurs.
OJI 2020, clasele XI-XII · Clasa a XI-aMetoda de rezolvare GreedyProbleme ce se rezolvă folosind metoda Greedy
Problema Partit
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.
| Număr ordine | Partiție |
|---|---|
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ță
Cunoscând valoarea numărului natural n:
- pentru un număr
kdat, să se tipărească partiția de pe pozițiakdin tabelul lexicografic; - 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 linia3se găsește un număr naturalk, reprezentând un număr de ordine; - dacă
c = 2, pe linia3se găsesc numere naturale separate prin câte un spațiu, reprezentând o partiție a număruluin.
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ărulkî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 ordinekal partiției citite.
Restricții și precizări
1 < n < 10.0000 < k < 1017(indiferent dacă este cazulc = 1sauc = 2)- pentru teste în valoare de aproximativ 18 puncte avem
n ≤ 20 - pentru alte teste în valoare de aproximativ 36 puncte avem
n < 10.000șik ≤ 1.000.000 - pentru alte teste în valoare de aproximativ 18 puncte avem
k ≤ 2.000.000.000 - pentru toate testele din fișierele de intrare există soluție
Exemple
1 4 5
2 1 1
2 21 1 2 3 4 5 6
375776
Explicația exemplelor
Primul exemplu corespunde exemplului din enunț: a cincea partiție este 2 1 1.
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;