Problemi 062

Kërkesa

Kemi një listë me N numra natyrorë. Gjejmë shumën S të numrave të listës dhe pastaj shtojmë në listë një numër më të madh se S. Këtë veprim e përsërisim K herë, kështu që në fund lista do ketë N+K numra. Gjeni vlerën më të vogël të mundshme të numrit që do shtohet i fundit në listë, dhe printoni nëse është çift apo tek.

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

Shembull

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

$ python3 prog.py < input.txt
even
odd

Dy numrat e parë janë N dhe K, pastaj vijnë numrat e listës.

Zgjidhja 1

for _ in range(int(input())):
    n, k = map(int, input().split())
    L = list(map(int, input().split()))
    while k > 0:
        s = sum(L)
        L.append(s + 1)
        k -= 1
    print('even') if L[-1] % 2 == 0 else print('odd')

Sqarime

Vlera më e vogël e mundshme është kur elementi i ri që shtohet në listë është gjithmonë 1 më i madh se shuma.

Kjo zgjidhje duket e thjeshtë por nuk është shumë e shpejtë. Në fakt ajo nuk e kalon testin te https://www.codechef.com/submit/UTMOPR sepse nuk përfundon brenda kohës së lejuar. Kompleksiteti i saj është i rendit \(O(K*N)\), sepse kemi një cikël që përsëritet K herë, dhe brenda tij bëjmë shumën e N elementeve të listës.

Zgjidhja 2

for _ in range(int(input())):
    n, k = map(int, input().split())
    L = list(map(int, input().split()))
    s = sum(L)
    while k > 0:
        a = s + 1
        s += a
        k -= 1
    print('even') if a % 2 == 0 else print('odd')

Sqarime

Kjo zgjidhje është pak më e shpejtë se e para, sepse shumën nuk e llogarisim nga e para, por e llogarisim në mënyrë progresive (duke shtuar në shumë vetëm elementin e ri). Kompleksiteti i saj është i rendit \(O(N+K)\), meqenëse gjejmë në fillim shumën e N elementëve të listës dhe pastaj kemi një cikël që përsëritet K herë. Megjithatë as kjo zgjidhje nuk e kalon testin sepse nuk është e shpejtë sa duhet.

Zgjidhja 3

for _ in range(int(input())):
    n, k = map(int, input().split())
    L = list(map(int, input().split()))
    if k > 1:
        print('even')
    else:
        print('odd') if sum(L) % 2 == 0 else print('even')

Sqarime

Po ta shikojmë problemin me kujdes dhe të bëjmë disa prova, mund të vërejmë dhe të vërtetojmë që elementi i ri që shtohet në listë është gjithmonë çift, me përjashtim të rastit kur shuma e elementeve fillestare të listës është çift dhe K është 1.

Kjo zgjidhje është shumë e shpejtë dhe e kalon testin. Kompleksiteti i saj në rastin më të keq është \(O(N)\) sepse gjejmë vetëm një herë shumën e elementëve të listës.

Detyra

Një bashkësi me numra natyrorë quhet e mirë nëse nuk ekzistojnë në të tre elemente të ndryshëm a, b, c të tillë që a + b = c.

Bëni një program që merr një numër n (nga 1 deri në 100) dhe nxjerr një bashkësi të mirë me n elementë, ku çdo element i bashkësisë mund të jetë një numër nga 1 deri në 500.

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

Shembull

$ cat input.txt
5
1
2
3
4
5

$ python3 prog.py < input.txt
7
1 2
1 2 4
1 2 4 16
3 2 15 6 10