BBB
Limit pamięci: 32 MB
Bajtazar ma konto w Bajtockim Banku Bitowym (w skrócie BBB).
Na początku na koncie było a na końcu bajtalarów.
Wszystkie transakcje polegały na wpłacie bądź wypłacie jednego bajtalara.
Bilans konta nigdy nie zszedł poniżej zera.
Kasjer przygotował wyciąg z konta: pasek papieru z ciągiem plusów i minusów
(plus oznacza wpłatę a minus wypłatę jednego bajtalara).
Okazało się, że operacje wykonywane na koncie nie zawsze były poprawnie księgowane.
Kasjer nie może wydrukować nowego wyciągu, lecz musi poprawić ten już wydrukowany.
Wyciąg nie musi być zgodny z rzeczywistością, wystarczy, że ciąg operacji na wyciągu
będzie spełniał następujące dwa warunki:
-
saldo końcowe będzie się zgadzać z saldem początkowym i ciągiem operacji na wyciągu,
-
zgodnie z ciągiem operacji na wyciągu, saldo konta nigdy nie spadło poniżej zera.
Twoim zadaniem jest policzenie minimalnego czasu, jaki kasjer potrzebuje na korektę wyciągu.
Kasjer może:
-
w ciągu sekund zmienić wybraną operację na wyciągu na przeciwną, lub
-
w ciągu sekund przenieść ostatnią operację na początek wyciągu.
Jeśli to na przykład --++-+-++-+-+ jest poprawnym wyciągiem.
Natomiast wyciąg ---++++++ nie jest poprawny,
gdyż po trzeciej operacji saldo konta spadłoby poniżej zera, a ponadto saldo końcowe
powinno wynosić 3, a nie 5.
Możemy go jednak poprawić, zmieniając przedostatni symbol na przeciwny
i następnie przenosząc ostatnią operację na początek wyciągu.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia aktualny wygląd wyciągu
z konta Bajtazara (ciąg plusów i minusów) oraz liczby , , i ,
-
wypisze na standardowe wyjście minimalną ilość czasu, potrzebną na taką korektę
wyciągu, żeby początkowy i końcowy bilans się zgadzały oraz żeby
saldo konta w żadnym momencie nie spadło poniżej zera.
Wejście
Pierwszy wiersz zawiera 5 liczb całkowitych , , , oraz
(, , ),
pooddzielanych pojedynczymi odstępami i oznaczających odpowiednio:
liczbę transakcji wykonanych przez Bajtazara, początkowe i końcowe saldo konta
oraz liczby sekund potrzebne na wykonanie pojedynczej zamiany i przesunięcia operacji na wyciągu.
Drugi wiersz zawiera ciąg plusów i/lub minusów, niezawierający odstępów.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą,
równą minimalnemu czasowi potrzebnemu do poprawienia wyciągu. Jeśli wyciąg nie wymaga poprawek, tą liczbą powinno być zero.
Możesz założyć, że odpowiedni ciąg modyfikacji wyciągu będzie istniał dla każdych danych testowych.
Przykład
Dla danych wejściowych:
9 2 3 2 1
---++++++
poprawną odpowiedzią jest:
3
Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.