Most
Limit pamięci: 16 MB
W środku nocy grupa turystów chce przejść przez stary, zniszczony,
dziurawy most.
Turyści mają jedną latarkę.
Światło latarki umożliwia przejście przez most maksymalnie
dwóm turystom na raz.
Turyści nie mogą przechodzić przez most bez latarki, ani w większych
niż dwuosobowe grupach, gdyż grozi to wpadnięciem do rzeki.
Każdemu turyście przejście przez most zajmuje określony czas.
Dwóch turystów idących razem potrzebuje na przejście przez most tyle
czasu, co wolniejszy z nich.
Jaki jest najkrótszy czas, w którym wszyscy turyści mogą przejść
przez most?
Przykład
Przypuśćmy, że grupa liczy czterech turystów.
Pierwszy z nich potrzebuje na przejście przez most 6 minut,
drugi 7 minut, trzeci 10 minut, a czwarty 15 minut.
Poniższy rysunek przedstawia, w jaki sposób turyści mogą przejść
przez most w 44 minuty.
Mogą to jednak zrobić szybciej.
Jak?
Przykładowy sposób przejścia mostu w 44 minuty.
Liczby w kółeczkach oznaczają liczbę minut, jaką turysta
potrzebuje na przejście mostu.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis grupy turystów,
- znajdzie najkrótszy czas wystarczający do przejścia przez most,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia
liczba całkowita - liczba turystów, .
W kolejnych wierszach zapisany jest niemalejący ciąg dodatnich liczb
całkowitych nie większych niż , po jednej w każdym wierszu.
Liczba w -szym wierszu (), określa czas potrzebny -temu
turyście na przejście przez most. Suma tych czasów nie przekracza .
Wyjście
Twój program powinien wypisać na standardowe wyjście,
w pierwszym wierszu, jedną liczbę całkowitą - najkrótszy czas
wystarczający, aby wszyscy turyści przeszli na drugą stronę mostu.
Przykład
Dla danych wejściowych:
4
6
7
10
15
poprawną odpowiedzią jest:
42
Autor zadania: Jakub Pawlewicz.