Problemi 050

Kërkesa

Një listë me numra A quhet e bukur nëse për çdo dy numra të listës \(a_i, a_j (i <> j)\), gjendet në listë një numër \(a_k\) i tillë që \(a_k = a_i * a_j\). Vini re që k mund të jetë edhe i ose j.

Gjeni nëse një listë e dhënë është e bukur ose jo.

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

Shembull

$ cat input.txt
3
2
0 1
2
1 2
2
5 6

$ python3 prog.py < input.txt
yes
yes
no

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if A[i]*A[j] not in A:
                print('no')
                break
        else:
            continue
        break
    else:
        print('yes')

Sqarime

Programi bën një cikël të dyfishtë për ti shqyrtuar të gjitha dyshet e mundshme të elementeve, por përjashton ato që kanë indeks të njëjtë (është i njëjti element). Nqs gjen dy numra prodhimi i të cilëve nuk ndodhet në listë, nxirret përgjigja “no” dhe ciklet ndërpriten. Përndryshe, nëse cikli i dyfishtë vazhdon deri në fund pa u ndërprerë, nxirret përgjigja “yes”.

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    b = True  # let's assume that it is beautiful
    i = 0
    while b and i < n:
        j = 0
        while b and j < n:
            if i != j and  A[i]*A[j] not in A:
                b = False
            j += 1
        i += 1
    print('yes') if b else print('no')

Sqarime

Llogjika është e ngjashme me zgjidhjen e parë, në kuptimin që shqyrtohen të gjitha dyshet e mundshme dhe prodhimi i tyre. Në fillim supozojmë se lista është e bukur dhe vazhdojmë kontrollin deri sa të gjejmë një dyshe numrash, prodhimi i të cilave nuk ndodhet në listë. Nëse gjejmë një dyshe të tillë, ndryshorja b bëhet False, çfarë bën që edhe të dyja ciklet të ndërpriten.

Kompleksiteti (ose ndërlikushmëria) e këtyre dy zgjidhjeve është \(O(n^3)\) (ose kubike), sepse janë dy cikle nga 1 në n brenda njëri-tjetrit, por gjithashtu edhe kur kërkojmë të dimë nëse një element ndodhet në listë, zakonisht na duhen \(O(n)\) veprime (mesatarisht \(n/2\)).

Nqs i testojmë këto dy zgjidhje te https://www.codechef.com/submit/ICPC16B ato nuk e kalojnë testin sepse ekzekutimi i programit zgjat mbi 10 sekonda, ndërkohë që limiti i kohës së ekzekutimit që ka problemi është vetëm 2 sekonda.

Zgjidhja 3

for _ in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))

    n0 = n1 = n_1 = n_other = 0
    for a in A:
        if a == 0:
            n0 += 1
        elif a == 1:
            n1 += 1
        elif a == -1:
            n_1 += 1
        else:
            n_other += 1

    if n == 1:
        print('yes')
    elif n_other > 1:
        print('no')
    elif n_1 == 0:
        print('yes')
    elif n_other == 1:
        print('no')
    elif n_1 == 1:
        print('yes')
    elif n1 > 0:
        print('yes')
    else:
        print('no')

Sqarime

Kjo zgjidhje duket pak më ndërlikuar se dy zgjidhjet e mëparshme, por në fakt është shumë më e shpejtë, me kompleksitet të rendit \(O(n)\). Si rrjedhojë kjo zgjidhje e kalon testin në https://www.codechef.com/submit/ICPC16B

Kjo zgjidhje bazohet në disa vëzhgime rreth cilësive të listave të bukura:

• Nëse një listë ka vetëm 1 element, është e bukur.
• Nëse në një listë janë 2 (ose më shumë) numra më të mëdhenj se 1, lista nuk mund të jetë e bukur.
• Nëse lista ka vetëm një numër më të madh se 1 dhe të tjerët janë 0 ose 1, është e bukur.
• Nëse lista ka më shumë se një -1, duhet të ketë edhe një 1 për të qenë e bukur.
• Nëse një listë ka një -1 dhe një numër më të madh se 1, nuk mund të jetë e bukur.

Ndryshorja n_1 mban sa -1 ka në listë, n1 sa 1, n0 sa 0, dhe n_other sa numra të tjerë (më të mëdhenj se 1 ose më të vegjël se -1).

Detyra

Sergei ka bërë N matje dhe do të gjejë vlerën mesatare të tyre. Por për të gjetur një mesatare sa më të mirë, ai mendon se duhet ti heqë nga lista e matjeve K vlerat më të vogla dhe K vlerat më të mëdha, para se të llogarisë mesataren. Sa del vlera mesatare në këtë mënyrë?

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

Shembull

$ cat input.txt
3
5 1
2 9 -10 25 1
5 0
2 9 -10 25 1
3 1
1 1 1

$ python3 prog.py < input.txt
4.000000
5.400000
1.000000