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; } Olimpiada Informatyczna (olimpiada-inf) Memory limit: 32 MB Time limit: 0.50 s Jak wiadomo, co roku odbywa się Olimpiada Informatyczna i jest to centralne wydarzenie dla wszystkich uczniów szkół ponadpodstawowych (i młodszych) zainteresowanych prawdziwą informatyką. Andrzej zbzikował na punkcie Olimpiady. Zapisał długi napis i poszukuje w nim podciągów OI. Dokładniej, Andrzej zastanawia się na ile sposobów może zakryć wszystkie litery napisu poza dokładnie dwoma, żeby pozostawione litery tworzyły napis OI. Czy pomożesz mu, żeby mógł w końcu skupić się na czymś poważniejszym? Napisz program, który wczyta napis Andrzeja, wyznaczy liczbę sposobów, na jaki można wybrać z tego napisu podciąg OI i wypisze wynik na standardowe wyjście. Wejście W pierwszym (jedynym) wierszu wejścia znajduje się niepusty napis Andrzeja złożony jedynie z wielkich liter alfabetu angielskiego. Wyjście Twój program powinien wypisać na wyjście dokładnie jedną nieujemną liczbę całkowitą – liczbę sposobów wybrania podciągu OI. Ograniczenia Długość napisu nie przekracza 500 000 znaków. Przykład Input Output Explanation AOAIOII 5 Aby uzyskać podciąg OI, można pozostawić w napisie litery: drugą i czwartą, drugą i szóstą, drugą i siódmą, piątą i szóstą lub piątą i siódmą.

Input	Output	Explanation
`AOAIOII`	`5`	Aby uzyskać podciąg `OI`, można pozostawić w napisie litery: drugą i czwartą, drugą i szóstą, drugą i siódmą, piątą i szóstą lub piątą i siódmą.