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

for _ in range(int(input())):
    input()
    V = input()
    nr = 0
    for d in V:
        if d == '1':
            nr += 1
    print( nr*(nr + 1)//2 )

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.

Zgjidhja 2

for _ in range(int(input())):
    input()
    V = input()
    nr = V.count('1')
    print( nr*(nr + 1)//2 )