Problemi 073

Kërkesa

Përpara zgjedhjeve është e rëndësishme që listat e votuesve të jenë sa më të sakta. Kryetari i komisionit të zgjedhjeve ka ngarkuar tre punonjës që të përpilojnë listat e votuesve të qytetit në mënyrë të pavarur nga njëri-tjetri. Në këto lista secili votues shënohet me një numër që është identiteti i tij. Pastaj ai i merr këto lista dhe harton një listë tjetër që përmban vetëm ata persona që ndodhen në të paktën dy prej listave të mësipërme. Bëni një program që mund të ndihmojë kryetarin në hartimin e kësaj liste.

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

Shembull

$ cat input.txt
1
23 30 42 57 90
21 23 35 57 90 92
21 23 30 57 90 

$ python3 prog.py < input.txt
21 23 30 57 90

Për çdo rast testimi kemi tre listat e punonjësve. Numri 21 ndodhet në listën e dytë dhe të tretë, kështu që është edhe në listën përfundimtare. Numri 23 ndodhet në të treja listat. Numri 30 ndodhet në të parën dhe të tretën. Numrat 35 dhe 42 ndodhen vetëm në një listë, kështu që nuk janë hedhur në listën përfundimtare. Numrat 57 dhe 90 ndodhen në të treja listat, kurse numri 92 ndodhet vetëm në një prej tyre.

Zgjidhja 1

for _ in range(int(input())):
    L1 = [int(i) for i in input().split()]
    L2 = [int(i) for i in input().split()]
    L3 = [int(i) for i in input().split()]
    L4 = []
    for v in L1:
        if v in L2 or v in L3:
            L4.append(v)
    for v in L2:
        if v not in L1 and v in L3:
            L4.append(v)
    print(*L4)

Sqarime

Llogjika e kësaj zgjidhje është e thjeshtë, por koha e ekzekutimit është kuadratike (\(O(N^2)\)).

Zgjidhja 2

def union(l1, l2):
    l = []
    i = j = 0
    while i < len(l1) and j < len(l2):
        if l1[i] < l2[j]:
            l.append(l1[i])
            i += 1
        elif l2[j] < l1[i]:
            l.append(l2[j])
            j += 1
        else:    # l1[i] == l2[j]
            l.append(l1[i])
            i += 1
            j += 1
    while i < len(l1):
        l.append(l1[i])
        i += 1
    while j < len(l2):
        l.append(l2[j])
        j += 1
    return l
    
for _ in range(int(input())):
    L1 = [int(i) for i in input().split()]
    L2 = [int(i) for i in input().split()]
    L3 = [int(i) for i in input().split()]
    L1.sort()
    L2.sort()
    L3.sort()
    I1 = intersection(L1, L2)
    I2 = intersection(L1, L3)
    I3 = intersection(L2, L3)
    U1 = union(I1, I2)
    U2 = union(U1, I3)
    print(*U2)

Sqarime

Kjo zgjidhje është pak më e gjatë dhe më e vështirë, por koha e saj është më e mirë se koha e zgjidhjes së parë. Funksionet intersection() dhe union() kanë kohë lineare (\(O(N)\)), por renditja zakonisht ka kohë të rendit \(O(N*ln(N))\), kështu që kjo e fundit mbizotëron. Por \(O(N*ln(N))\) është më e mirë se \(O(N^2)\).

Zgjidhja 3

for _ in range(int(input())):
    L1 = set(int(i) for i in input().split())
    L2 = set(int(i) for i in input().split())
    L3 = set(int(i) for i in input().split())
    L4 = L1.intersection(L2).union(L2.intersection(L3)).union(L1.intersection(L3))
    print(*L4)

Sqarime

Duke përdorur bashkësitë (set()) dhe funksionet e gatshme të tyre zgjidhja është shumë më e shkurtër. Por veprimet në bashkësi janë të rendit \(O(N*ln(N))\), kështu që koha e kësaj zgjidhje është njëlloj si koha e zgjidhjes së dytë.

Detyra

Ada ka N lapsa me ngjyra, disa me majën poshtë dhe disa me majën lart. Ada mendon se do ishte më mirë sikur të gjithë lapsat të ishin në të njëjtin drejtim. Ajo mund të kthejë njëherësh një segment të tërë me lapsa të njëpasnjëshëm. Pas një kthimi, ata që ishin me majë poshtë do kthehen me majën lart, dhe anasjelltas. Sa është numri më i vogël i kthimeve për të bërë të gjithë lapsat me të njëjtin drejtim?

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

Shembull

$ cat input.txt
1
UUDDDUUU

$ python3 prog.py < input.txt
1

Me U shënohet një laps me majën lart dhe me D një laps që e ka majën poshtë. Në rastin e dhënë, mjafton vetëm një kthim për ti vendosur me majën lart të gjithë lapsat që janë me majën poshtë.