Problemi 149

Kërkesa

Në një varg S me shkronja të vogla të alfabetit (anglisht), gjeni se sa nënvargje përmbajnë N bashkëtingëllore të njëpasnjëshme.

Referenca: https://code.google.com/codejam/contest/2437488/dashboard#s=p0&a=0

Shembull

$ cat input.txt
4
quartz 3
straight 3
gcj 2
tsetse 2

$ python3 prog.py < input.txt
4
quartz 3
straight 3
gcj 2
tsetse 2

Për çdo rast testimi jepet vargu S dhe numri N.

Zgjidhja 1

for t in range(int(input())):
    S, n = input().split()
    n = int(n)
    
    L = len(S)
    cnt = 0
    for i in range(L):
        for j in range(i+1, L+1):
            c = 0
            for k in range(i, j):
                if S[k] not in "aeiou":
                    c += 1
                else:
                    c = 0
                if c >= n:
                    cnt += 1
                    break

    print('Case #{}: {}'.format(t+1, cnt))

Sqarime

Shqyrtojmë të gjitha nënvargjet e mundshme, dhe për çdo nënvarg kontrollojmë nëse përmban n bashkëtingëllore të njëpasnjëshme.

Koha e kësaj zgjidhje është e rendit \(O(L^3)\).

Zgjidhja 2

for t in range(int(input())):
    S, n = input().split()
    n = int(n)

    L = len(S)
    cnt = 0
    for i in range(L):
        c = 0
        for j in range(i, L):
            if S[j] not in "aeiou":
                c += 1
            else:
                c = 0
            if c >= n:
                cnt += L - j
                break

    print('Case #{}: {}'.format(t+1, cnt))

Sqarime

Kjo zgjidhje shfrytëzon faktin që nqs një nënvarg që fillon te i dhe mbaron te j përmban n bashkëtingëllore të njëpasnjëshme, atere edhe të gjitha nënvargjet e tjera që fillojnë në i dhe mbarojnë në j+1, j+2, e deri në L do përmbajnë të paktën n bashkëtingëllore të njëpasnjëshme.

Kjo zgjidhje është e rendit \(O(L^2)\).

Zgjidhja 3

for t in range(int(input())):
    S, n = input().split()
    n = int(n)

    L = len(S)
    cnt, r, c = 0, 0, 0
    for i in range(L):
        if S[i] not in "aeiou":
            c += 1
        else:
            c = 0
        if c >= n:
            cnt += (i - n - r + 2) * (L - i)
            r = i - n + 2

    print('Case #{}: {}'.format(t+1, cnt))

Sqarime

Kjo zgjidhje është e rendit \(O(L)\). Për një analizë të hollësishme dhe për më shumë sqarime shikoni: https://code.google.com/codejam/contest/2437488/dashboard#s=a&a=0