Problemi 044

Kërkesa

Një listë me numra quhet jo-zbritëse nqs çdo numër i listës është <= se numri pasardhës. Një nën-listë e një liste me numra përbëhet nga një ose disa numra të njëpasnjëshëm të listës.

Bëni një program që gjen se sa nën-lista jo-zbritëse ka në një listë të dhënë.

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

Shembull

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

$ python3 prog.py < input.txt
6
1

Në rastin e parë kemi 6 nën-lista jo-zbritëse: [1], [1, 4], [4], [2], [2, 3], [3]. Në rastin e dytë kemi vetëm 1: [5].

Zgjidhja

T = int(input())
for t in range(T):
    n = int(input())
    L = list(map(int, input().split()))
    L.append(L[-1] - 1)
    ans = 0
    nr = 1
    for i in range(n):
        if L[i] <= L[i+1]:
            nr +=1
        else:
            ans += nr*(nr+1)//2
            nr = 1
    print(ans)

Sqarime

Mund të vihet re lehtë se të gjitha nën-listat e një liste jo-zbritëse janë edhe ato jo-zbritëse. Po ashtu mund të vërtetohet lehtë se listë me n numra ka n*(n+1)//2 nën-lista.

Zgjidhja gjen segmentet jo-zbritëse të listës së dhënë dhe gjatësinë nr të secilit prej tyre. Çdo segment i tillë i shton përgjigjes nr*(nr+1)//2 nën-lista jo-zbritëse.

Detyra

Dejvi shkoi në pazar dhe pa fshatarët që po shisnin kosha me rrush. Mirëpo numrat e kileve që kishin koshat nuk i pëlqyen se iu dukën pa lidhje. Dejvi do të donte që pjesëtuesi më i madh i përbashkët i të gjithë numrave të ishte i plotpjesëtueshëm me K. Bëni një program që gjen numrin më të vogël të kileve që duhen shtuar ose hequr nëpër kosha, që të plotësohet ky kusht dhe asnjë kosh të mos ngelet bosh.

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

Shembull

$ cat input.txt
2
2 2
3 5
3 7
10 16 18

$ python3 prog.py < input.txt
2
8

Në rastin e parë kemi 2 kosha dhe numrat e kileve duhet të plotpjesëtohen me 2. Mjafton të shtojmë ose të heqim 1 kile nga secili prej koshave, që të plotësohet ky kusht.

Në rastin e dytë kemi 3 kosha dhe numrat e kileve duhet të plotpjesëtohen me 7. Mund të heqim 3 kile në koshin e parë, të heqim 2 kile koshin e dytë, dhe të shtojmë 3 kile në koshin e tretë. Gjithsej, 3 + 2 + 3 = 8.