Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP7_1E - Pozar |
W pewnym mieście znanym z zadań Demonstracja 2 i Metro płonie most. Strażacy podzielili most na n odcinków i dla każdego z nich określili siłę występującego na nim pożaru. Akcja gaśnicza będzie prowadzona z powietrza. Samolot będzie przelatywał wzdłuż mostu i zrzucał wodę na jeden wybrany odcinek. Po każdym takim zrzucie wody siła pożaru na wybranym odcinku maleje o w1 jednostek, zaś na wszystkich pozostałych odcinkach o w2 jednostek. Pożar zostanie ugaszony, w momencie kiedy na wszystkich odcinkach mostu jego siła będzie mniejsza bądź równa zeru.
Odpowiedz na pytanie ile minimalnie lotów będą musieli wykonać strażacy żeby ugasić pożar mostu?
Wejście
W pierwszej linii wejścia znajdują się trzy liczby całkowite n ∈ [1;105], w1 ∈ [1;109] i w2 ∈ [1;w1] opisane powyżej. W kolejnej linii znajduje się n liczb całkowitych z przedziału [1;109] oznaczających siłę pożaru na kolejnych odcinkach mostu.
Wyjście
Na wyjściu należy wypisać minimalną liczbę lotów jaką muszą wykonać strażacy, aby ugasić pożar.
Przykład
Wejście
4 2 1 1 2 3 2
Wyjście
2
Wyjaśnienie do przykładu
Przykładowy plan ugaszeniu pożaru może wyglądać następująco:
- Zrzucamy wodę na 2 odcinek z lewej. Siła pożaru po zrzucie: 0 0 2 1
- Zrzucamy wodę na 3 odcinek z lewej. Siła pożaru po zrzucie: 0 0 0 0
Dodane przez: | Maciej Boniecki |
Data dodania: | 2015-03-21 |
Limit czasu wykonania programu: | 0.5s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 JS-MONKEY SCM qobi |
Pochodzenie: | VII Mistrzostwa WWSI w Programowaniu |