Problemi 141

Kërkesa

Jepet një varg me zero-njësha. Gjeni numrin e nënvargjeve që fillojnë dhe mbarojnë me 1.

Referenca: https://www.codechef.com/problems/CSUB

Shembull

$ cat input.txt
2
4
1111
5
10001

$ python3 prog.py < input.txt
10
3

Zgjidhja 1

Sqarime

Nqs numri i njëshave është n, atere numri i segmenteve që fillojnë dhe mbarojnë me 1 është n*(n + 1)/2. Vërtet, nqs marrim njëshin e parë si fillim të segmentit, si fund të segmentit mund të marrim secilin nga n njëshat. Nqs si fillim marrim njëshin e dytë, si fund mund të marrim n-1 njësha, duke filluar nga i dyti. E kështu me radhë, numri i segmenteve që mund të formohen është n + (n-1) + (n-2) + ... + 2 + 1.