Problemi 080

Kërkesa

Trajneri i futbollit të një shkolle duhet të zgjedhë P nxënës për të përfaqësuar shkollën në kampionat. Shkolla ka N nxënës dhe aftësitë e secilit në futboll shënohen me një numër natyror \(S_i\).

Trajneri mendon se skuadra duhet të jetë e niveluar, dmth të ketë P nxënës me të njëjtin nivel aftësish, sepse kështu do të luajnë të gjithë si skuadër. Në fillim mund të mos jetë e mundur që të gjenden P nxënës me aftësi të barabarta, kështu që trajnerit do ti duhet ti stërvitë individualisht disa nxënës, për të rritur aftësitë e tyre. Me një orë stërvitje aftësia e një nxënësi mund të ngrihet me 1 pikë.

Sa është minimumi i orëve të stërvitjes që duhen për të krijuar një skuadër të niveluar.

Referenca: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e01/00000000000698d6

Shembull

$ cat input.txt
3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7

$ python3 prog.py < input.txt
Case #1: 14
Case #2: 0
Case #3: 6

Jepen N dhe P, dhe më pas aftësitë e çdo nxënësi.

Në rastin e parë mund të trajnohet për 6 orë nxënësi i parë dhe për 8 orë nxënësi i dytë, dhe atere tre nxënësit e parë do kenë të njëjtin nivel aftësish.

Në rastin e dytë, dy nxënësit e parë kanë të njëjtin nivel aftësish, kështu që nuk është nevoja për trajnime shtesë.

Në rastin e tretë, nxënësi i tretë duhet trajnuar për 6 orë, dhe kështu të 5 nxënësit do kenë të njëjtin nivel.

Zgjidhja 1

for t in range(int(input())):
    n, p = map(int, input().split())
    L = [int(i) for i in input().split()]
    L.sort()
    c = 0
    for i in range(p):
        c += L[p-1] - L[i]
    c_min = c
    for j in range(p, n):
        c = 0
        for i in range(j-p+1, j):
            c += L[j] - L[i]
        if c < c_min:
            c_min = c
    print('Case #{}: {}'.format(t+1, c_min))

Sqarime

Në fillim i rendisim nxënësit sipas aftësive dhe pastaj gjejmë ata P nxënës të njëpasnjëshëm që kanë nevojë për më pak trajnim. Këtë e bëjmë duke i kontrolluar të gjitha nënvargjet e njëpasnjëshme me P elementë. Meqenëse kemi dy cikle brenda njëri-tjetrit, koha e kësaj zgjidhje është e rendit \(O(N*P)\).

Zgjidhja 2

for t in range(int(input())):
    n, p = map(int, input().split())
    L = [int(i) for i in input().split()]
    L.sort()
    s = 0
    for i in range(p):
        s += L[i]
    c_min = p*L[p-1] - s
    for i in range(p, n):
        s += L[i]
        s -= L[i-p]
        c = p*L[i] - s
        if c < c_min:
            c_min = c
    print('Case #{}: {}'.format(t+1, c_min))

Sqarime

Koha e trajnimit për një nënvarg nga i-p+1 në i është (L[i] - L[i-1]) + (L[i] - L[i-2]) + . . . + (L[i] - L[i-p+1]) ose p*L[i] - (L[i-p+1] + L[i-p+2] + . . . + L[i-1] + L[i]). Shumën në kllapa mund ta llogarisim në mënyrë hap-pas-hapi, kështu që nuk është nevoja të bëjmë një cikël tjetër për të llogaritur koston e një nënvargu. Kjo bën që koha e kësaj zgjidhje të jetë e rendit \(O(N)\), që është më e mirë se zgjidhja e parë.

Detyra

Jepet një varg me zero-njësha. Gjeni numrin e nënvargjeve që fillojnë dhe mbarojnë me 1.

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

Shembull

$ cat input.txt
2
4
1111
5
10001

$ python3 prog.py < input.txt
10
3