== 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ţînâ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 necesar 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$
* Numărul total de runde nu depăşeşte 100 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 |
| #@#.@
| 5
| 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) = 0, T(5) = 1. |
| #@.####@#@
| 23
| ... |
== include(page="template/taskfooter" task_id="slide") ==
