Papryczki logarytmiczne [B]
Limit pamięci: 64 MB
Hitem sezonu w bajtockim warzywniaku są papryczki logarytmiczne.
Jak sama nazwa wskazuje, wagi papryczek, wyrażone w gramach, są wyłącznie
potęgami dwójki między a .
Typowy przebieg transakcji w warzywniaku wygląda tak, że klient prosi
o
gramów papryczek i sprzedawca wydaje mu dokładnie taką ich masę,
posługując się wyłącznie całymi papryczkami.
Może się niestety tak zdarzyć, że zamówienie klienta będzie niemożliwe
do spełnienia.
Pomóż sprzedawcy sprawdzić, na ile jest on zabezpieczony przed taką feralną
sytuacją, czyli wyznaczyć najmniejszą taką liczbę naturalną
z zamówienia
nie do zrealizowania.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis aktualnego stanu warzywniaka,
- wyznaczy wartość z najgorszych koszmarów sprzedawcy,
- wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(), oznaczającą, że masy papryczek znajdujących się na stanie
warzywniaka to .
Drugi wiersz zawiera liczb całkowitych dodatnich
nie większych niż , pooddzielanych pojedynczymi odstępami
i oznaczających dokładny stan sklepu: papryczek o wadze , -
o wadze , ..., - o wadze .
Wyjście
Pierwszy i jedyny wiersz wejścia powinien zawierać jedną liczbę całkowitą
dodatnią - najmniejszą wartość zamówienia, której sprzedawca nie
będzie w stanie zrealizować.
Przykład
Dla danych wejściowych:
2
2 1 1
poprawną odpowiedzią jest:
9
Wyjaśnienie do przykładu: Wszystkie wartości od do
można osiągnąć przy aktualnym stanie sklepu; oto przykładowe takie
przedstawienia:
, , , , , , , .
Wartości oczywiście nie da się wyrazić.
Autor zadania: Jakub Radoszewski.