Problemi 145

Kërkesa

Një klasë ka N nxënës dhe pikët e secilit prej tyre na jepen në një listë L. Gjeni të gjitha prerjet e mundshme \(P = (x, y)\) që mund ti bëhen kësaj liste, të tilla që shuma e pikëve brenda prerjes të jetë e barabartë me shumën e pikëve jashtë prerjes. Dmth \(L_x + L_{x+1} + ... + L_{y-1} + L_y = (L_0 + L_1 + ... + L_{x-1}) + (L_{y+1} + L_{y+2} + ... + L_{N-1})\).

Nëse nuk ka asnjë prerje të tillë printoni -1, përndryshe printoni numrin e prerjeve dhe shumën e indekseve x dhe y për të gjitha prerjet. Këto indekse janë me bazë 0, dhe \(0 < x <= y < N-1\). Gjithashtu \(3 <= N <= 10^5\) dhe \(1 <= L_i <= 10^5\).

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

Shembull

$ cat input.txt
2
10
7 8 12 8 13 9 5 7 12 3
5
32 36 34 20 28

$ python3 prog.py < input.txt
2 17
-1

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    L = [int(i) for i in input().split()]

    nr = 0
    idx_sum = 0
    for i in range(1, n - 1):
        for j in range(i, n - 1):
            if sum(L[:i]) + sum(L[j+1:]) == sum(L[i:j+1]):
                nr += 1
                idx_sum += i + j

    if nr == 0:
        print(-1)
    else:
        print(nr, idx_sum)

Sqarime

Koha e zgjidhjes është e rendit \(O(N^3)\).

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    L = [int(i) for i in input().split()]

    S = [0 for i in range(n)]
    S[0] = L[0]
    for i in range(1, n):
        S[i] = S[i-1] + L[i]

    nr = 0
    idx_sum = 0
    scores = sum(L) // 2
    for i in range(1, n - 1):
        for j in range(i, n - 1):
            if S[j] - S[i-1] == scores:
                nr += 1
                idx_sum += i + j

    if nr == 0:
        print(-1)
    else:
        print(nr, idx_sum)

Sqarime

Në listën S mbajmë shumat e pjesëshme nga fillimi deri në atë pozicion ku jemi. Këto mund të gjenden shumë kollaj me një bredhje nga fillimi deri në fund, dhe ndihmojnë që të gjendet në mënyrë efiçente shuma e numrave të një prerje.

Koha e kësaj zgjidhje është e rendit \(O(N^2)\).

Zgjidhja 3

for _ in range(int(input())):
    n = int(input())
    L = [int(i) for i in input().split()]
    if sum(L) % 2 == 1:
        print(-1)
    else:
        idx_sum = 0
        scores = sum(L) // 2
        nr = 0
        i = j = 1
        s = L[1]
        while True:
            while s < scores and j < n - 1:
                j += 1
                s += L[j]
            if s < scores:
                break
            if s == scores:
                nr += 1
                idx_sum += i + j
                if j < n - 1:
                    j += 1
                    s += L[j]
            while s > scores:
                s -= L[i]
                i += 1
            if s == scores:
                nr += 1
                idx_sum += i + j
                s -= L[i]
                i += 1
        if nr == 0:
            print(-1)
        else:
            print(nr, idx_sum)

Sqarime

Së pari vërejmë që shuma e pikëve brenda segmentit duhet të jetë sa gjysma e pikëve totale. Nqs pikët totale janë numër tek, atere nuk mund të ketë asnjë prerje që plotëson kushtet.

Mbajmë dy indekse i dhe j që shënojnë numrin e parë dhe të fundit të segmentit. Vazhdojmë të rrisim indeksin j, duke llogaritur edhe shumën brenda segmentit, deri sa ta kalojë gjysmën e pikëve, pastaj vazhdojmë të lëvizim indeksin i deri sa shuma të bëhet më pak se gjysma e pikëve. Gjatë kësaj kohe kontrollojmë edhe nëse shuma bëhet e barabartë me gjysmën e pikëve, e cila do ishte një prerje që plotëson kushtet.

Koha e kësaj zgjidhje është e rendit \(O(N)\), që është shumë më e mirë se zgjidhja e parë.

Detyra