Problemi 034

Kërkesa

Një sistem për menaxhimin e skedarëve të një projekti mban një listë të skedarëve të injoruar dhe një listë të skedarëve të gjurmuar (të ndjekur). Gjeni sa skedarë janë edhe të injoruar edhe të gjurmuar, dhe sa janë as të injoruar dhe as të gjurmuar.

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

Shembull

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

$ python3 prog.py < input.txt
4 1
1 1

Kemi 2 raste testimi. Në rastin e parë kemi N=7 numri total i skedarëve (të etiketuar nga 1 deri në 7), M=4 numri i skedarëve të injoruar, dhe K=6 numri i skedarëve të gjurmuar. Më poshtë kemi 1 4 6 7 lista e skedarëve të injoruar, dhe 1 2 3 4 6 7 lista e skedarëve të gjurmuar. Po ti krahasojmë, shohim se skedarët 1 4 6 7 (pra 4 skedarë) janë edhe të injoruar edhe të gjurmuar, kurse skedari 5 (pra 1 skedar) nuk është as i injoruar as i gjurmuar.

Në rastin e dytë kemi gjithsej 4 skedarë, 2 të injoruar dhe 2 të gjurmuar. Nga këta vetëm skedari 4 (pra 1 skedar) është edhe i injoruar edhe i gjurmuar, kurse skedari 2 (pra 1 skedar) nuk është as i injoruar dhe as i gjurmuar.

Zgjidhja 1

for _ in range(int(input())):
    N, M, K = map(int, input().split())
    l1 = input().split()
    l2 = input().split()
    l1.sort()
    l2.sort()
    bashkimi = []
    prerja = []
    i = 0
    j = 0
    while i < M and j < K:
        if l1[i] == l2[j]:
            prerja.append(l1[i])
            bashkimi.append(l1[i])
            i += 1
            j += 1
        elif l1[i] < l2[j]:
            bashkimi.append(l1[i])
            i += 1
        else:
            bashkimi.append(l2[j])
            j += 1
    while i < M:
        bashkimi.append(l1[i])
        i += 1
    while j < K:
        bashkimi.append(l2[j])
        j += 1
    print(len(prerja), N - len(bashkimi))

Sqarime

Për të gjetur ata skedarë që janë edhe të injoruar edhe të gjurmuar, duhet të gjejmë prerjen e dy listave të dhëna.

Për të gjetur ata skedarë që nuk janë as të injoruar dhe as të gjurmuar, fillimisht gjejmë ata që janë të injoruar OSE të gjurmuar (bashkimin e dy listave të dhëna).

Zgjidhja 2

for _ in range(int(input())):
    N, M, K = map(int, input().split())
    s1 = set(input().split())
    s2 = set(input().split())
    print(len(s1.intersection(s2)), N - len(s1.union(s2)))

Sqarime

Duke përdorur strukturën set të python-it dhe veprimet e saj (intersection(), union()) zgjidhja bëhet shumë e thjeshtë.

Bëni këto prova:

$ python3
>>> s1 = {2, 3, 4, 5}
>>> s1
{2, 3, 4, 5}
>>> s2 = {4, 5, 5, 6, 7}
>>> s2
{4, 5, 6, 7}
>>> s1.intersection(s2)
{4, 5}
>>> s1.union(s2)
{2, 3, 4, 5, 6, 7}
>>> 

Detyra

Në një lojë kemi N monedha të numëruara nga 1 në N, dhe fillimisht të gjitha monedhat janë nga e njëjta anë (H ose T). Loja luhet me N raunde, dhe në çdo raund k, lojtari kthen k monedhat e para (nga 1 deri në k) në anën tjetër. Duam të gjejmë se sa monedha do jenë në një anë të caktuar (H ose T) në fund të lojës.

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

Shembull

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

$ python3 prog.py < input.txt
2
3

Kemi 2 raste testimi. Në rastin e parë kemi I=1, N=5, Q=1, që do të thotë se fillimisht monedhat janë të gjitha në anën H, kemi 5 monedha dhe 5 raunde, dhe në fund të raundit të 5-të duam të dimë se sa monedha janë në anën H.

Në rastin e dytë është e njëjta gjë, vetëm se duam të dimë se sa monedha janë në anën T (Q=2).

Gjendja e monedhave pas çdo raundi do jetë e tillë: 1. T H H H H 2. H T H H H 3. T H T H H 4. H T H T H 5. T H T H T

Kështu që përgjigja për rastin e parë është 2, kurse për rastin e dytë është 3.