Problemi 029

Kërkesa

Në fund të ditës, para se kuzhina e restorantit të mbyllet, është një listë me n punë (nga 1 në n) që duhen bërë. Kuzhinierët kanë bërë disa prej tyre dhe janë larguar, dhe tani ka mbetur vetëm shefi dhe ndihmësi i tij. Ata i marrin punët e mbetura me radhë: të parën shefi, të dytën ndihmësi, të tretën shefi, e kështu me radhë (një po një jo).

Bëni një program që nxjerr punët që bën shefi dhe ato që bën ndihmësi, kur jepet numri n i punëve, numri m i punëve që janë bërë deri tani, dhe numrat e punëve që janë bërë deri tani.

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

Shembull

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

$ python3 prog.py < input.txt
3 6
5
1

1 4 6
2 5 7

1. Në rastin e parë janë 6 punë dhe janë bërë punët 2 4 1. Kanë mbetur pa bërë punët 3 5 6, kështu që shefi bën punët 3 6 kurse ndihmësi bën punën 5.

2. Në rastin e dytë janë 3 punë dhe janë bërë punët 3 2. Ka mbetur pa bërë vetëm puna 1, kështu që këtë e bën shefi kurse ndihmësi nuk bën asgjë (rreshti bosh).

3. Në rastin e tretë janë 8 punë dhe janë bërë punët 3 8. Kanë mbetur pa bërë punët 1 2 4 5 6 7, kështu që shefi bën punët 1 4 6, kurse ndihmësi bën punët 2 5 7.

Zgjidhja 1

def print_punet(punet):
    if len(punet) == 0:
        print()
    else:
        for p in punet[:-1]:
            print(p, end=' ')
        print(punet[-1])

for _ in range(int(input())):
    n, m = map(int, input().split())
    punet = [1] + [0]*n    # liste me 1 njesh dhe n zero
    punet_e_bera = list(map(int, input().split()))
    for p in punet_e_bera:
        punet[p] = 1
    punet1 = []    # punet e shefit
    punet2 = []    # punet e ndihmesit
    radha = 'shefi'
    for p in range(1, n+1):
        if punet[p] == 0:
            if radha == 'shefi':
                punet1 += [p]
                radha = 'ndihmesi'
            else:
                punet2 += [p]
                radha = 'shefi'
    print_punet(punet1)
    print_punet(punet2)

Sqarime

Mbajmë një listë me të gjitha punët, ku punët e pabëra shënohen me 0, punët e bëra me 1, kurse indeksi në listë është numri i punës. Pastaj punët e pabëra i ndajmë në dy lista të tjera.

Zgjidhja 2

for _ in range(int(input())):
    n, m = map(int, input().split())
    punet = []    # te gjitha punet
    for i in range(n):
        punet += [i+1]
    punet_e_bera = list(map(int, input().split()))
    for p in punet_e_bera:
        punet[p-1] = -1
    punet1 = []    # punet e shefit
    punet2 = []    # punet e ndihmesit
    radha = 'shefi'
    for p in punet:
        if p != -1:
            if radha == 'shefi':
                punet1 += [p]
                radha = 'ndihmesi'
            else:
                punet2 += [p]
                radha = 'shefi'
    print(*punet1)
    print(*punet2)

Sqarime

E ngjashme me zgjidhjen e parë, por punët i ruajmë në listë sipas numrit të tyre, kurse punët e bëra i shënojmë me -1.

Kur themi print(*list), i tregojmë funksionit print() që të printojë gjithë elementët e listës, jo vetë listën.

Zgjidhja 3

for _ in range(int(input())):
    n, m = map(int, input().split())
    punet = []    # te gjitha punet
    for i in range(n):
        punet += [i+1]
    punet_e_bera = list(map(int, input().split()))
    for p in punet_e_bera:
        punet.remove(p)
    punet1 = []    # punet e shefit
    punet2 = []    # punet e ndihmesit
    radha = 'shefi'
    for p in punet:
        if radha == 'shefi':
            punet1 += [p]
            radha = 'ndihmesi'
        else:
            punet2 += [p]
            radha = 'shefi'
    print(*punet1)
    print(*punet2)

Sqarime

E ngjashme me zgjidhjen e dytë, por punët e bëra, në vend që ti shënojmë me -1, i fshijmë fare nga lista (me funksionin remove()). Punët që mbeten i ndajmë një andej një këtej.

Zgjidhja 4

for _ in range(int(input())):
    n, m = map(int, input().split())
    punet = []    # te gjitha punet
    for i in range(n): punet += [i+1]
    punet_e_bera = list(map(int, input().split()))
    for p in punet_e_bera: punet.remove(p)
    punet1 = [punet[i] for i in range(len(punet)) if i % 2 == 0]
    punet2 = [punet[i] for i in range(len(punet)) if i % 2 == 1]
    print(*punet1)
    print(*punet2)

Sqarime

E ngjashme me zgjidhjen e tretë, vetëm se kodi për ndarjen e punëve të mbetura është pak më kompakt.

Detyra

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