Problemi 078

Kërkesa

Babai ka shkuar të bëjë pazarin bashkë me të birin 5-vjeçar. Deri tani kanë blerë N gjëra, të cilat peshojnë \(W_i\) secila. Djali ngul këmbë që ta ndihmojë babanë për ti mbajtur sendet e blera. Por që babai mos t’ia bëjë “me hile” dhe ti japë gjëra shumë të lehta, djali kërkon që sendet të ndahen në dy grupe, ku njëri prej tyre ka K elementë, dhe pastaj njërin prej grupeve ta mbajë djali dhe tjetrin babai. Babai sigurisht që do ti japë djalit grupin që peshon më pak. Por si mund ti ndajë sendet në dy grupe në mënyrë të tillë që diferenca në peshë midis tyre të jetë sa më e madhe?

Bëni një program që gjen diferencën në peshë më të madhe, nqs N sende i ndajmë në dy grupe, ku njëri nga grupet ka K sende.

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

Shembull

$ cat input.txt
2
5 2
8 4 5 2 10
8 3
1 1 1 1 1 1 1 1

$ python3 prog.py < input.txt
17
2

Në rastin e parë kemi N=5 dhe K=2. Diferenca më e madhe do jetë nëse djalit i jep sendet me peshë 2 dhe 4. Diferenca në këtë rast do jetë (8+5+10)-(4+2)=17.

Në rastin e dytë sido që të bëhet ndarja, diferenca do jetë gjithmonë 2.

Zgjidhja 1

for _ in range(int(input())):
    n, k = map(int, input().split())
    W = [int(i) for i in input().split()]
    W.sort()
    s1 = s2 = 0
    for i in range(k):
        s1 += W[i]
        s2 += W[n-1-i]
    s = 0
    for i in range(n):
        s += W[i]
    print(max(abs(s1 - (s - s1)), abs(s2 - (s - s2))))

Sqarime

Nqs duam të gjejmë K numrat që kanë shumën më të madhe, mjafton që ti rendisim dhe të marrim K numrat e fundit. Gjithashtu (N-K) kanë shumën më të vogël të mundshme, kështu që diferenca midis këtyre dy grupeve është më e madhja e mundshme.

Nqs duam të gjejmë K numrat që kanë shumën më të vogël të mundshme, mjafton që ti rendisim dhe të marrim K numrat e parë. Atere (N-K) numrat që mbeten kanë shumën më të vogël të mundshme, kështu që përsëri diferenca është më e madhja e mundshme.

Programi i shqyrton të dyja këto raste dhe gjen diferencën më të madhe prej tyre.

Zgjidhja 2

for _ in range(int(input())):
    n, k = map(int, input().split())
    W = [int(i) for i in input().split()]
    W.sort()
    s = sum(W)
    s1 = sum(W[0:k])
    s2 = sum(W[-k:])
    print(max(abs(2*s1 - s), abs(2*s2 - s)))

Sqarime

E njëjta zgjidhje por pak më kompakte, ku W[0:k] jep nënlistën me k elementet e para, dhe W[-k:] jep nënlistën me k elementet e fundit.

Detyra

Në një listë me numra natyrorë bëjmë këtë veprim: Zgjedhim disa prej numrave të listës dhe i fshijmë nga lista. Si kosto të këtij veprimi përkufizojmë rezultatin e kryerjes së një Bitwise OR midis elementeve të fshira. Këtë veprim e përsërisim deri sa në listë të mos ngelet më asnjë element. Kostoja e përgjithshme është shuma e kostos së çdo veprimi. Gjeni vlerën më të vogël të mundshme të kostos së përgjithshme.

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

Shembull

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

$ python3 prog.py < input.txt
3
7