Rezolvare PBinfo #3086

Cristi, deja familiarizat cu noțiunea de densitate de la orele de fizică, își propune să o studieze și din perspectiva informaticii. Astfel, el alege un șir de N numere naturale A[1], A[2], …, A[N] și își dorește să experimenteze.

Cerința

Să se calculeze câte secvențe nevide au proprietatea că raportul dintre numărul elementelor pare din cadrul secvenței și lungimea secvenței este exact D.

Date de intrare

În fișierul de intrare densitate.in, pe prima linie se află numărul N, ce reprezintă lungimea șirului de numere. Pe a doua linie se află, separate prin câte un spațiu, N numere naturale. Pe a treia linie se află densitatea D, reprezentată cu două zecimale exacte sub forma 0.ab.

Date de ieșire

Fișierul de ieșire densitate.out va conține o singură linie pe care se va afla numărul secvențelor ce respectă proprietatea din enunț.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 0 ≤ A[i] ≤ 1.000.000, 1 ≤ i ≤ N.
• 0 ≤ D ≤ 0.99
• Prin secvență a șirului A se înțelege orice succesiune de elemente aflate pe poziții consecutive A[j], A[j+1], A[j+2], …, A[k], cu 1 ≤ j ≤ k ≤ N.

Exemplu:

densitate.in

6
1 0 3 5 2 7
0.50

densitate.out

5

Explicație

Sunt 5 secvențe cu densitate 0.50: 1 0; 0 3; 5 2; 2 7; 0 3 5 2.