Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-12-05 00:30:28.
Revizia anterioară Revizia următoare

Fsb

Se da un sire de 0 si 1. Se cere numarul de subsecvente care au numar egal de 0 si 1.

Date de intrare

Fişierul de intrare fsb.in contine pe prima linie N, lungimea sirului. Pe a doua linie se afla un sir de N caractere, reprezentand sirul.

În fişierul de ieşire fsb.out se afla un singur interg, reprezentand numarul de subsecvente cerut.

1 ≤ N ≤ 500.000
Se considera subsecventa a unui sir a₁, a₂, ..., a_N sirul a_i₁, a_i₂, ... a_{i_k}, cu proprietatea ca 1 ≤ i₁ ≤ i₂ ≤ ... ≤ i_k ≤ N
Doua subsecvente a_i₁, a_i₂, ... a_{i_k} si a_j₁, a_j₂, a_{j_l} se considera distincte, daca l ≠ k, sau exista t ≤ k, astfel incat a_{i_t} ≠ a_{j_t}

fsb.in	fsb.out
6 110001	4

Subsecventele cerute sunt: 1100, 10, 01, 110001

Trebuie sa te autentifici pentru a trimite solutii. Click aici