Problem description
Być może znany jest Ci problem plecakowy. W jednym z najprostszych wariantów można go opisać następująco: dany jest zbiór przedmiotów, znana jest masa każdego z przedmiotów, celem jest zapakować plecak przedmiotami o sumarycznej masie K kilogramów.
Być może znasz też rozwiązanie tego zadania oparte o programowanie dynamiczne, w którym zaczynamy od sytuacji świata bez przedmiotów, w którym da się tylko zapakować plecak o pojemności 0 kilogramów. Następnie każdy krok programu to przejście do świata, w którym jest już kolejny przedmiot. Program w każdym kroku oblicza więc pojemności plecaków, które można zapakować podzbiorem prefiksu ciągu przedmiotów.
Tym razem nie będzie jednak tak łatwo, bo zadanie będzie odwrotne. Otrzymujesz informację o pojemnościach plecaków, które można upakować przedmiotami o nieznanych masach. Twoim zadaniem jest wyznaczyć masy przedmiotów, które były wejściem dla algorytmu rozwiązującego problem plecakowy. Innymi słowy, nieco precyzyjniej, wybrano ciąg liczb (masy przedmiotów) T, i na wejściu znajdzie się tyle kopii liczby S, ile wynosi liczba podzbiorów T sumujących się do S. Przedmioty są parami różne, nawet jeśli mają te same masy.
Napisz program, który: wczyta masy plecaków możliwych do zapakowania nieznanymi przedmiotami, wyznaczy masy przedmiotów i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę podzbiorów przedmiotów. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych Ai pooddzielanych pojedynczymi odstępami: sumaryczne masy podzbiorów przedmiotów.
Wyjście
W pierwszym wierszu wyjścia należy wypisać jedną nieujemną liczbę całkowitą R: liczbę przedmiotów, które były wejściem do algorytmu plecakowego. W drugim wierszu wyjścia należy wypisać niemalejący ciąg R liczb naturalnych pooddzielanych pojedynczymi odstępami: masy przedmiotów, które były wejściem do algorytmu plecakowego.
Ograniczenia
1 ≤ N ≤ 1 000 000, 0 ≤ Si ≤ 1018.
Przykład
| Input | Output | |
|
|