Viki nosí rôzne kusy oblečenia, ktoré majú veľa záhybov. A na čo sú dobré záhyby? Tam sa predsa plošticiam dobre schováva. Ploštica Cyprián takto raz naskočil na Viki a prešiel dokola po celom jej Kabáte, aby našiel všetky záhyby. Cyprián je iba ploštica, takže nevníma tretí rozmer a svoju trasu si vie zakresliť na papier. Ciprián navyše ide stále dopredu, až kým sa nevráti na pôvodné miesto. Zvládne si prí tom zapisovať iba to, aké kroky robí. Teda, či ide rovno, alebo sa otáča doprava, alebo doľava. Teraz by potreboval vašu pomoc, aby zistil, koľko miesta je v záhyboch.
Úloha
Na vstupe dostanete popis Cypriánovej trasy. Táto trasa sa nikde nepretína (nekrižuje samú seba) a končí tam, kde začala. Vašou úlohou je zistiť, koľko miesta je v záhyboch. Záhyb je každá obdĺžniková oblasť, ktorá je aspoň z dvoch protiľahlých strán ohraničená trasou (teda napríklad hore a aj dole).
Na nasledovnom obrázku sú miesta v záhyboch vyznačené sivou.
Formát vstupu
Na jedinom riadku vstupu sa nachádza reťazec písmen R
L
P
ktoré postupne znamenajú rovno
, doľava
, doprava
.
Dĺžka reťazca nepresiahne \(10^5\). Ak si počiatočnú pozíciu označíme ako \((0,0)\) tak súradnice bodov na trase v absolútnej hodnote nepresiahnu \(3\,000\). V reťazci sa nikdy nanachádzajú za sebou dve otočenia (teda L
alebo P
).
Formát výstupu
Vypíš jeden riadok a v ňom jedno celé číslo – celkovú plochu záhybov.
Príklady
Input:
RRRPRRRPRRRPRRRP
Output:
0
Trasa na vstupe vyzerá ako štvorec.
Input:
RRRRRRPRRRRPRRPRRLRRLRRRPRRPRRRRR
Output:
4
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.