W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Bajtazar od dziecka marzył o sięgnięciu chmur. Teraz jego marzenie może się wreszcie spełnić.
Aby osiągnąć swój cel, Bajtazar kupił pustaków ponumerowanych liczbami od do . Pustaki mają taką samą wysokość, lecz mogą różnić się szerokościami. Planuje zbudować z nich wielopoziomową wieżę w taki sposób, aby na każdy poziom składało się kilka pustaków, a sumaryczna szerokość każdego poziomu była nie większa niż sumaryczna szerokość poziomu znajdującego się bezpośrednio pod nim (o ile taki istnieje). Bajtazar jest także głęboko przekonany, że wieża zawali się, jeśli pewien pustak znajdzie się na wyższym poziomie niż pustak o większym numerze. Kawalerka Bajtazara jest za mała do przechowywania pustaków, więc do zbudowania wieży musi on użyć wszystkich pustaków będących w jego posiadaniu.
Przed zabraniem się do pracy, Bajtzar poprosił Cię o obliczenie, jaka jest największa możliwa wysokość wieży, którą jest w stanie zbudować, zachowując wymienione warunki.
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę kupionych przez Bajtazara pustaków. W drugim wierszu wejścia znajduje się liczb całkowitych (); liczba oznacza szerokość pustaka o numerze .
Dla danych wejściowych:
3 1 2 3
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu: Na najniższym poziomie wieży Bajtazar może ułożyć pustaki o numerach i , natomiast na drugim poziomie - pustak o numerze .
Autor zadania: Brian Dean (zapożyczenie z USACO: Adam Karczmarz).