Здраствуйте!

Очередная задача. Дана строка s(|s| = 10^5), которая содержит только нули и единицы, и некое число k(10^5). Далее дается число N(10^5) - количество запросов. После следуют числа l , r(1 <= l <= r <= |s|). Для каждого запроса необходимо вывести количество подстрок отрезка [l,r] количество нулей и единиц которого не превышает числа k. 

Пример:

1
8 2 3
01110000
1 4
2 4
5 8

Ответ:

8
5
7

Пояснение:

Первый запрос: Рассмотрим подстроку P = S[1, 4] = “0111”. Из 10 подстрок строки P, только
подстроки P[1, 4] и P[2, 4] не удовлетворяют заданным условиям, так как они содержат более
чем 2 единицы. Остальные подстроки содержат не более 2 нулей и не более 2 единиц,
следовательно, ответ на запрос – 8.

Второй запрос: Рассмотрим подстроку P = S[2, 4] = “111”. Среди 6 подстрок строки P,
подстрока P[1, 3] содержит более чем 2 единицы.

Третий запрос: Рассмотрим строку P = S[5, 8] = “0000”.
Среди 10 подстрок строки P, подстроки P[1, 3] , P[1, 4] и P[2, 4] не удовлетворяют заданным
условиям, потому что в них содержатся более чем 2 нуля.

P.s. язык - С++

Это сообщение отредактировал(а) altairaimenov - 11.3.2015, 18:35

Если вы хотите помощи приведите код, что у вас не получается.
Решать задачи мы и сами можем  projecteuler, uvaonlinejudge и другие сайты, я думаю, большинству известны.

Вот кстати оригинал
http://www.codechef.com/MARCH15/problems/STRSUB

А решение кстати гуглится
http://stackoverflow.com/questions/2892022...ost-k-1s-and-0s

Это сообщение отредактировал(а) sQu1rr - 18.3.2015, 17:46

Ух ты:Теперь так же на вопросы отвечать буду  

altairaimenov, так решение годится или нет?