Fișierul intrare/ieșire | sir11.in, sir11.out | Sursă | ad-hoc |
---|---|---|---|
Autor | din folclor | Adăugată de | Victor Manz • vmanz |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 512 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Sir11
Se dau n și s, două numere naturale nenule și un multiset A = {a(1), a(2),..., a(n)} de n numere naturale nenule, nu neapărat distincte. Scrieți un program care generează și afișează toate șirurile crescătoare formate cu elemente ale lui A a caror suma este mai mica sau egala cu s. Șirurile vor fi afișate în ordine crescătoare din punct de vedere lexicografic.
În general, spunem că șirul , x(2), ..., x(m)) este mai mic decât șirul , y(2), ..., y(n)) din punct de vedere lexicografic dacă:
- există k, 1 ≤ k ≤ min(m, n), astfel încât x(1) = y(1), x(2) = y(2), ..., x(k-1) = y(k-1) și x(k) < y(k)
sau
- m < n și x(i) = y(i) pentru orice 1 ≤ i ≤ m (șirul x este un prefix al lui y).
Date de intrare
Fișierul de intrare sir11.in va conține pe prima linie separate printr-un spațiu numerele n și s. Pe fiecare dintre următoarele n linii se va afla câte un element al multisetului A: pe linia i+1 se va afla a(i).
Date de ieșire
În fișierul de ieșire sir11.out vor fi scrise pe linii separate toate șirurile cerute. Elementele fiecărui șir vor fi separate prin câte un spațiu.
Restricții
- 1 ≤ n ≤ 20
- 1 ≤ s ≤ 30
- 1 ≤ a(i) ≤ 100 pentru orice 1 ≤ i ≤ n
Exemplu
sir11.in | sir11.out |
---|---|
5 10 3 8 11 3 6 |
3 3 3 3 3 3 3 6 6 8 |
Explicație
Șirurile afișate au sumele 3, 6, 9, 9, 6 și respectiv 8, sunt crescătoare și sunt afișate în ordine lexicografică. Acestea sunt singurele șiruri care respectă condițiile din enunț.