Problemi 088

Kërkesa

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.

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    M = input().split()
    s = 0
    j = 0
    for i in range(n):
        if M[i] == '1':
            if i > j:
                s += 100
            j += 1
    while j < n:
        s += 1000 + 100
        j += 1
    print(s)

Sqarime

Në fillim gjejmë (te ndryshorja j) se sa muaj ka paguar. Nqs këta muaj të paguar kanë qenë me vonesë, llogarisim edhe gjobën. Pastaj, muajt që kanë mbetur pa paguar janë të gjithë të vonuar, kështu që llogarisim për ta edhe pagesën edhe gjobën.

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    M = input().split()
    s = 0
    for i in range(n):
        if M[i] == '0':
            s += 1000
    j = 0
    while j < n and M[j] == '1':
        j += 1
    while j < n:
        s += 100
        j += 1
    print(s)

Sqarime

Në fillim llogarisim pagesën për çdo muaj të pa paguar ('0'). Pastaj gjemë muajin e parë që nuk është paguar, dhe që aty e deri në fund llogarisim gjobat.

Zgjidhja 3

for _ in range(int(input())):
    n = int(input())
    M = input().split()
    s = M.count('0') * 1000
    try:
        i = M.index('0')
        s += (n - i) * 100
    except:
        pass
    print(s)

Sqarime

Numrin e muajve të pa paguar mund ta gjejmë edhe me funksionin count('0'). Kurse muajin e parë të pa paguar mund ta gjejmë edhe me funksionin index('0'). Vetëm se ky funksion jep një kundërshtim në rast se nuk ka asnjë '0' në listë, prandaj kemi përdorur try...except.

Zgjidhja 4

for _ in range(int(input())):
    n = int(input())
    M = input().split()
    s = M.count('0') * 1000
    i = (M + ['0']).index('0')
    s += (n - i) * 100
    print(s)

Sqarime

Në këtë variant e kemi shmangur nevojën për try...except duke shtuar artificialisht një '0' në fund të listës. Kjo zero nuk na prish punë dhe siguron që funksioni index() nuk do jap kundërshtim.

Detyra

Kemi një pemë me N nyje (të shënuara me numrat 1 deri në N), ku rrënja është nyja 1. Çdo nyje i ka një vlerë \(A_i\) (që mund të jetë edhe numër negativ).

Mund të zgjedhim një nyje çfarëdo të pemës dhe të fshijmë gjithë nënpemën (degën) poshtë saj, përfshirë edhe vetë nyjen. Këtë veprim mund ta përsërisim disa ose asnjë herë.

Le të përkufizojmë si përfitim shumën e të gjitha vlerave të nyjeve të mbetura në pemë, minus \(X * k\), ku X është një numër i dhënë paraprakisht, dhe k është numri i herëve që është kryer veprimi i përshkruar më sipër. Gjeni vlerën më të madhe të mundshme të përfitimit.

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

Shembull

$ cat input.txt
1
3 5
1 -5 -10
1 2
2 3

$ python3 prog.py < input.txt
-4

Kemi një rast testimi. Në rreshtin e parë jepen numrat N dhe X. Në rreshtin e dytë jepen N vlerat \(A_i\). Në N-1 rreshtat pasardhës jepen dy numra u dhe v, që tregojnë se ka një brinjë midis dy nyjeve të shënuara me u dhe v.

Në rastin e dhënë pema është e tillë: (1)–>(2)–>(3). Duke shënuar edhe vlerat përkatëse të çdo nyje mund ta paraqesim kështu: (1,1)–>(2,-5)–>(3,-10).

Nqs nuk fshijmë asnjë nyje/degë përfitimi do jetë: 1 + -5 + -10 = -14. Nqs fshijmë nyjen 3, do jetë: 1 + -5 - 15 = -9. Nqs fshijmë nyjen 3 dhe pastaj fshijmë nyjen 2, do jetë: 1 - 25 = -9. Nqs fshijmë vetëm nyjen 2 do jetë: 1 - 15 = -4. Nqs fshijmë nyjen 3, pastaj 2, pastaj 1, do jetë: 0 - 35 = -15. Nqs fshijmë nyjen 2 pastaj nyjen 1, do jetë: 0 - 25 = -10. Nqs fshijmë vetëm nyjen 1, përfitimi do jetë: 0 - 15 = -5.

Nga të gjitha këto vlera të përfitimeve, vlera më e madhe është -4, e cila është edhe përgjigja.