Fişierul intrare/ieşire:slide.in, slide.outSursăAlgoritmiada 2017 Runda 2
AutorEugenie Daniel PosdarascuAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.15 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Slide

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)!

Date de intrare

Fişierul de intrare slide.in conţine, pe singura linie, un şir de N caractere '#', '@' şi '.' reprezentând calendarul competiţional.

Date de ieşire

În fişierul de ieşire slide.out veţi afişa un singur număr natural S = T(1) + T(2) + ... + T(N).

Restricţii

  • 1 ≤ N ≤ 1 000 000
  • Pentru 30% din teste, N ≤ 1 000.

Exemplu

slide.inslide.outExplicaţ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
...
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?