Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Premia (premia) Limit pamięci: 32 MB Limit czasu: 1.50 s Firma Januszex S.A. po udanej modernizacji linii produkcyjnej kolejek chce wynagrodzić swoich pracowników za zaangażowanie. Pan Janusz (prezes firmy) przewidział premie pieniężne dla najlepszych pracowników i chciałby wiedzieć ilu z nich i jaką premią może obdarować. Jak to w takich firmach bywa, jeśli premie będą różne, to współpracownicy będą sobie zazdrościć, więc należy przyznać jednakowe sumy dla wszystkich zasłużonych osób. W sejfie są schowane banknoty o nominałach 1, 2 i 3 JND (januszodolary), które przeznaczono na ten szczytny cel i należy je wydać wszystkie. Ponadto są one złożone w jeden wysoki stos. Chcąc przeprowadzić wypłaty szybko i sprawnie, należy kolejnym przychodzącym pracownikom wydawać pewną liczbę banknotów z góry stosu znajdującego się w sejfie. Napisz program, który wczyta ułożenie kolejnych banknotów na stosie i obliczy wszystkie możliwe podziały pieniędzy pomiędzy pracowników. Wejście W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę banknotów w sejfie. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych Ai pooddzielanych pojedynczymi odstępami określających nominały kolejnych banknotów. Wyjście Twój program powinien wypisać na wyjście rosnący ciąg liczb pooddzielanych pojedynczymi odstępami oznaczających kolejne propozycje wartości premii dla jednego pracownika. Ograniczenia 1 ≤ N ≤ 500 000, Ai ∈ {1, 2, 3}. Przykład Wejście Wyjście Wyjaśnienie 8 3 1 1 3 2 2 1 3 4 8 16 Pieniądze można dać czterem pracownikom, wówczas każdy otrzyma po 4 JND. Można także rozdzielić tę sumę między dwóch pracowników – wtedy premia dla każdego wyniesie 8 JND. Inne rozwiązanie to przyznać premię tylko jednemu pracownikowi (na przykład prezesowi) w kwocie 16 JND.

Wejście	Wyjście	Wyjaśnienie
`8 3 1 1 3 2 2 1 3`	`4 8 16`	Pieniądze można dać czterem pracownikom, wówczas każdy otrzyma po 4 JND. Można także rozdzielić tę sumę między dwóch pracowników – wtedy premia dla każdego wyniesie 8 JND. Inne rozwiązanie to przyznać premię tylko jednemu pracownikowi (na przykład prezesowi) w kwocie 16 JND.