Problemi 060

Kërkesa

Alisa është zënë me Blertën këto kohët e fundit dhe s’do të ketë më punë me të. Ato kanë secila një grup me numra natyrorë. Numrat e Alisës janë \(A_1, A_2, ... , A_N\), kurse numrat e Blertës janë \(B_1, B_2, ..., B_M\). Tani Alisa do që të fshijë të gjithë numrat në grupin e saj që janë të përbashkët me numrat e Blertës. Sa është numri më i vogël i numrave që duhet të fshijë Alisa?

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

Shembull

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

$ python3 prog.py < input.txt
1
0

Zgjidhja 1

for _ in range(int(input())):
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    nr = 0
    for a in A:
        if a in B:
            nr += 1
    print(nr)

Sqarime

Kjo zgjidhje është llogjikisht e thjeshtë: për çdo element të listës A kontrollojmë nëse ndodhet edhe në B. Kompleksiteti është i rendit \(O(N*M)\), meqenëse kemi një cikël që përsëritet N herë, dhe brenda tij kërkojmë në një listë që ka M elementë.

Po ta testojmë: https://www.codechef.com/submit/NOTINCOM kjo zgjidhje kalon vetëm testin e vogël dhe merr vetëm gjysmat e pikëve.

Zgjidhja 2

for _ in range(int(input())):
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    A.sort()
    B.sort()
    nr = 0
    i = 0
    j = 0
    while i < n and j < m:
        if A[i] == B[j]:
            nr += 1
            i += 1
        elif A[i] < B[j]:
            i += 1
        else:
            j += 1
    print(nr)

Sqarime

Kjo zgjidhje duket pak më e ndërlikuar se e para, por është më e shpejtë. Kjo zgjidhje i kalon të dyja grupet e testimit: https://www.codechef.com/submit/NOTINCOM

Fillimisht renditen të dyja listat dhe pastaj kontrollohet për të parë se sa elemente janë të barabarta midis tyre. Renditjen e listave ne e bëjmë me funksione të gatshme, por një renditje e shpejtë zakonisht merr një kohë të rendit \(O(N*ln(N))\). Kështu që në total, koha që i duhet programit është përafërsisht: \(O(N*ln(N)) + O(M*ln(M) + N + M)\), ose përafërsisht \(O(N*ln(N))\) (nqs supozojmë që \(N \approx M\)). Kjo kohë është më e mirë se koha e zgjidhjes së mëparshme \(O(N^2)\) (nqs supozojmë që \(N \approx M\)).

Detyra

Nga rezultatet e një olimpiade mund të hamendësojmë nivelin e aftësive për secilin pjesëmarrës. Pjesëmarrësit mund të klasifikohen bazuar në numrin e problemave të zgjidhura në këtë mënyrë:

• 0 problema të zgjidhura: Beginner
• 1 problem të zgjidhur: Junnior Developper
• 2 problema të zgjidhura: Middle Developer
• 3 problema të zgjidhura: Senior Developer
• 4 problema të zgjidhura: Hacker
• 5 problema të zgjidhura: Jeff Dean

Bëni një program që merr rezultatet e pjesëmarrësve dhe nxjerr klasifikimin e tyre.

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

Shembull

$ cat input.txt
7
0 0 0 0 0
0 1 0 1 0
0 0 1 0 0
1 1 1 1 1
0 1 1 1 0
0 1 1 1 1
1 1 1 1 0

$ python3 prog.py < input.txt
Beginner
Middle Developer
Junior Developer
Jeff Dean
Senior Developer
Hacker
Hacker