== include(page="template/taskheader" task_id="slide") ==
Poveste şi cerinţă...
_We're not letting it slide this time!_
Datele în care se ţin rundele de Algoritmiada alunecă mai uşor prin timp decât un copil pe gheaţă (drept dovadă, acest enunţ a fost scris în iarnă când comparaţia era de sezon), de obicei -datorită- din cauza multor evenimente complet neprevăzute precum competiţii naţionale şi internaţionale, sesiuni de examene şi internship-uri. Dar gata, de la anul totul va fi planificat din timp, iar evenimentele neprevăzute vor avea loc toate într-o singură oră!
Calendarul competiţional al Algoritmiadei are $N$ ore şi este reprezentat printr-un şir format din $N$ caractere de tipurile $'#'$, $'@'$ şi $'.'$. Poziţiile marcate cu $'#'$ şi $'@'$ în şir reprezintă ore în care se ţin rundele de Algoritmiada, o rundă fiind reprezentată printr-o subsecvenţă de lungime maximală de caractere de acelaşi tip. Poziţiile marcate cu $'.'$ reprezintă ore libere. De exemplu, şirul $"###..@@#..##"$ reprezintă un calendar cu $12$ ore şi $4$ runde de concurs (în intervalele $[1, 3], [6, 7], [8, 8], [11, 12)]$).
Vechea interfaţă infoarena permite decalarea rundelor; din nefericire, o decalare reprezintă mutarea unei runde cu o oră în plus sau în minus (aceasta păstrându-şi lungimea), cu condiţia ca după decalare să nu se suprapună cu o altă rundă. De notat că începutul şi/sau sfârşitul unei runde *pot să se afle în afara celor $N$ ore din reprezentarea iniţială* după una sau mai multe decalări. De exemplu, pentru calendarul $"##..@."$, prima rundă poate fi decalată cu două ore în plus, obţinând calendarul $"..##@."$, dar şi cu două ore în minus, obţinând calendarul $"##....@"$. Pentru calendarul $"##@"$ nu putem decala prima rundă cu o oră în plus, *decât dacă întâi decalăm a doua rundă* cu o oră în plus.
Notăm cu $T(i)$ numărul minim de decalări necesare pentru ca ora $i$ din reprezentarea iniţială să devină liberă. Calculaţi $S = T(1) + T(2) + ... + T(N)$!
h2. Date de intrare
Fişierul de intrare $slide.in$ ...
Fişierul de intrare $slide.in$ conţine, pe singura linie, un şir de $N$ caractere $'#'$, $'@'$ şi $'.'$ reprezentând calendarul competiţional.
h2. Date de ieşire
În fişierul de ieşire $slide.out$ ...
În fişierul de ieşire $slide.out$ veţi afişa un singur număr natural $S = T(1) + T(2) + ... + T(N)$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1 000 000$
* Pentru $30%$ din teste, $N ≤ 1 000$.
h2. Exemplu
table(example). |_. slide.in |_. slide.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. slide.in |_. slide.out |_. Explicaţie |
| #@##..@
| 7
| T(1) = 1 (decalăm prima rundă cu o oră în minus), T(2) = 2 (decalăm prima rundă cu o
oră în minus şi apoi a doua rundă cu o oră în minus), T(3) = 1, T(4) = 2 (decalăm a treia
rundă cu două ore în plus), T(5) = 0, T(6) = 0, T(7) = 1. |
| #@.####@#@
| 23
| ... |
== include(page="template/taskfooter" task_id="slide") ==
