Problemi 033

Kërkesa

Në një rrugë ndodhen 100 shtëpi dhe dyqane, me numra nga 1 në 100. Në M prej tyre banojnë policë të veprimit të shpejtë. Në rast se në ndonjë nga shtëpitë ose dyqanet ndodh ndonjë vjedhje ose incident, pronari mund të shtypë butonin e alarmit dhe policët më të afërt vrapojnë për në vendngjarje. Nëse arrijnë brenda një kohe të caktuar, të quajtur koha kritike, mund ta kapin hajdutin me presh në dorë.

Çdo polic mund të arrijë K shtëpi (ose dyqane) brenda kohës kritike, në të dyja anët e shtëpisë së tij. Nëse te një shtëpi nuk mund të arrijë asnjë polic brenda kohës kritike, thuhet që kjo shtëpi nuk ka mbrojtje të mjaftueshme. Nëse mund të arrijnë disa policë (më shumë se një), thuhet që ka mbrojtje të shumëfishtë.

Na jepet numri K dhe vendbanimi i çdo polici. Bëni një program që gjen sa shtëpi nuk kanë mbrojtje të mjaftueshme dhe sa kanë mbrojtje të shumëfishtë.

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

Shembull

$ cat input.txt
3
4 56
12 52 56 8
2 20
21 75
2 40
10 51

$ python3 prog.py < input.txt
0 100
18 0
9 40

Zgjidhja

for _ in range(int(input())):
    n, k = map(int, input().split())
    policat = list(map(int, input().split()))
    mbrojtja = [0 for i in range(101)]
    mbrojtja[0] = 1
    for p in policat:
        mbrojtja[p] += 1
        for i in range(1, k + 1):
            if p - i >= 1:
                mbrojtja[p - i] += 1
            if p + i <= 100:
                mbrojtja[p + i] += 1
    nr1 = 0
    nr2 = 0
    for m in mbrojtja:
        if m == 0:
            nr1 += 1
        if m > 1:
            nr2 += 1
    print(nr1, nr2)

Sqarime

Në listën mbrojtja mbajmë shënim për çdo shtëpi se nga sa polica mund të mbrohet (fillimisht 0). Pastaj për çdo polic të dhënë shtojmë 1 te secila shtëpi që mund të mbrojë (shtëpinë e vet dhe k në të majtë e k në të djathtë). Përfundimisht numërojmë shtëpitë me mbrojtje 0 dhe ato me mbrojtje më shumë se 1.

Detyra

Colit i pëlqen të luaj me numrat dhe sot po bën një lojë të tillë:

Në një listë me numra A zgjedh dy numra të njëpasnjëshëm. Më të madhin prej tyre e heq nga lista, dhe kështu gjatësia e listës zvogëlohet me 1. Kostoja e këtij veprimi është sa më i vogli prej tyre. Këtë veprim e përsërit deri sa në listë të ketë mbetur vetëm 1 numër, dhe gjen shumën e kostove për të gjitha veprimet.

Sa është vlera më e vogël e kësaj shume?

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

Shembull

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

$ python3 prog.py < input.txt
3
4

Në rastin e parë mund të kryejmë vetëm një veprim. Ky veprim fshin numrin 4 nga lista dhe e ka koston 3 (që është edhe kostoja e përgjithshme).

Në rastin e dytë mund të zgjedhim në fillim dyshen 4 2, ku fshihet numri 4 dhe kostoja e veprimit është 2, pastaj mund të zgjedhim dyshen 2 5, ku fshihet numri 5 dhe kostoja e veprimit është 2. Kostoja e përgjithshme është 4.