Problemi 085

Kërkesa

Na jepet një varg S me gjatësi N dhe një shkronjë X. Gjeni numrin e nënvargjeve të S që e përmbajnë shkronjën X të paktën një herë.

Referenca: https://www.codechef.com/APRIL19B/problems/STRCH

Shembull

$ cat input.txt
2
3
abb b
6
abcabc c

$ python3 prog.py < input.txt
5
15

Në rastin e parë, vargu abb ka gjashtë nënvargje: a, b, b, ab, bb, abb. Nënvargjet që përmbajnë b janë: b, b, ab, bb, abb.

Zgjidhja

for _ in range(int(input())):
    n = int(input())
    S, x = input().split()
    nr = n*(n + 1)//2
    m = 0
    for c in S+x:
        if c == x:
            nr -= m*(m + 1)//2
            m = 0
        else:
            m += 1
    print(nr)

Sqarime

Nqs një nënvarg fillon te shkronja e parë, mund ta ketë fundin te secila nga n shkronjat. Nqs fillon te shkronja e dytë mund ta ketë fundin te secila nga (n-1) shkronjat nga e dyta deri në fund. Kështu që gjithsej, një varg me gjatësi n ka \(n + (n-1) + (n-2) + ... + 2 + 1\) nënvargje. Vlera e kësaj shume mund të llogaritet me formulën: n*(n + 1)//2.

Nqs nga të gjitha nënvargjet e mundshme heqim ato që nuk përmbajnë X, na ngelen ato që përmbajnë të paktën një X. Për të gjetur numrin e nënvargjeve që nuk përmbajnë X, gjejmë segmentet që nuk përmbajnë X. Nqs një segment i tillë e ka gjatësinë m, atere ka m*(m + 1)//2 nënvargje brenda tij.

Detyra

Cufi duhet të paguajë për qiranë e shtëpisë 1000 lekë çdo muaj. Por nqs pagesën e bën me vonesë (nuk ka rëndësi se sa vonë) duhet të paguajë edhe 100 lekë gjobë. Ai ka jetuar për N muaj në këtë shtëpi dhe tani duhet të shkojë diku tjetër, kështu që i duhet të shlyejë të gjitha pagesat e prapambetura (bashkë me gjobat).

Nga veprimet që ka bërë në llogarinë bankare ai mund të shikojë se disa muaj ka bërë pagesa 1000 lekëshe për qiranë, por asnjëherë nuk ka shlyer ndonjë gjobë. Ky informacion (se në cilin muaj ka paguar dhe në cilin jo) na jepet në formën e një vargu me N zero dhe njësha (zero kur nuk ka paguar dhe njësh kur ka paguar). Por nqs nuk ka paguar muajin e parë dhe ka paguar muajin e dytë, kjo pagesë i shkon si pagesë e muajit të parë, dhe është pagesë e vonuar, kështu që prapë i ngelet për të paguar gjobën e muajit të parë. Po kështu edhe muaji i dytë konsiderohet si pagesë e vonuar, kështu që edhe për muajin e dytë duhet të paguajë gjobë.

Gjeni se sa duhet paguar për ti shlyer të gjitha detyrimet.

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

Shembull

$ cat input.txt
4
2
1 1
2
0 0
3
0 1 0
2
0 1

$ python3 prog.py < input.txt
0
2200
2300
1200

S’ka lënë asnjë pagesë pa paguar.
S’ka paguar asnjë nga 2 muajt. Bashkë me gjobat duhet të paguajë 2200.
Ka bërë një pagesë muajin e dytë. Ka për të paguar edhe muajin e parë dhe të tretë, si dhe 3 gjoba. Gjithsej 2300.
Ka bërë një pagesë muajin e dytë. Ka për të paguar muajin e parë dhe 2 gjoba, gjithsej 1200.