Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Zagadka Jędrzeja (A) Limit pamięci: 64 MB Limit czasu: 1.00 s Jędrzej poszedł do sklepu kupić sobie wymarzony napis złożony z liter a oraz b. W sklepie każda litera a kosztuje bajtalara, zaś każda litera b kosztuje dwa bajtalary. Możliwe jest jednak zakupienie pakietu czterech liter a za trzy bajtalary lub pakietu pięciu liter b za osiem bajtalarów, ale tylko wtedy, gdy te litery stanowią spójny fragment kupowanego napisu. Jędrzej zastanawia się za ile może zakupić swój wymarzony napis. Pomóż mu! Napisz program, który wczyta wymarzony napis Jędrzeja, wyznaczy jego koszt i wypisze wynik na standardowe wyjście. Wejście W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter a lub b, bez żadnych odstępów. Jest to wymarzony napis Jędrzeja. Wyjście W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalny koszt napisu z wejścia według zasad panujących w sklepie. Ograniczenia Długość napisu nie przekracza 1 000 000 znaków. Gwarantowane jest, że w testach wartych łącznie 50% punktów w napisie na wejściu nie występują cztery lub więcej liter a obok siebie ani pięć lub więcej liter b obok siebie. Przykład Wejście Wyjście Wyjaśnienie aabaaaaabba 13 Możliwe jest zakupienie jednego pakietu trzech liter a. Pozostałe znaki trzeba zakupić indywidualnie. Koszt wyniesie więc: 1 + 1 + 2 + 3 + 1 + 2 + 2 + 1 = 13 bajtalarów.

Wejście	Wyjście	Wyjaśnienie
`aabaaaaabba`	`13`	Możliwe jest zakupienie jednego pakietu trzech liter `a`. Pozostałe znaki trzeba zakupić indywidualnie. Koszt wyniesie więc: 1 + 1 + 2 + 3 + 1 + 2 + 2 + 1 = 13 bajtalarów.