Problemi 086
Kërkesa
Një arë është e ndarë në parcela, të cilat formojnë N rreshta (nga 1 në N) dhe M shtylla (nga 1 në M). Nga këto, vetëm K parcela janë të mbjella, kurse të tjerat janë me barishte. Dy parcela quhen fqinje nëse kanë një anë të përbashkët. Duam të ndërtojmë një gardh që rrethon parcelat e mbjella, në mënyrë të tillë që të mos ketë gardh midis dy parcelave të mbjella por vetëm midis një parcele të mbjellë dhe një të pambjellë, ose midis një parcele të mbjellë dhe pjesës jashtë arës. Sa është numri më i vogël i anëve ku duhet ndërtuar gardh?
Referenca: https://www.codechef.com/APRIL19B/problems/FENCE
Shembull
$ cat input.txt
2
4 4 9
1 4
2 1
2 2
2 3
3 1
3 3
4 1
4 2
4 3
4 4 1
1 1
$ python3 prog.py < input.txt
20
4Për çdo rast testimi jepen N, M dhe K. Më pas vijnë K rreshta me nga dy numra r dhe s, që janë rreshti dhe shtylla e një parcele të mbjellë.
Në rastin e parë fusha duket e tillë (ku me x është shënuar një parcelë e mbjellë dhe me - një parcelë e pambjellë:
---x
xxx-
x-x-
xxx-Një zgjidhje optimale është që të ndërtohet gardh rreth parcelës lart në cep (4 anë), pastaj rreth grupit të parcelave të mbjella poshtë (12 anë), si dhe rreth parcelës së pambjellë në qendër (4 anë). Gjithsej 4 + 12 + 4 = 20 anë.
Zgjidhja 1
for _ in range(int(input())):
n, m, k = map(int, input().split())
F = [[False for j in range(m+2)] for i in range(n+2)]
while k > 0:
r, c = map(int, input().split())
F[r][c] = True
k -= 1
nr = 0
for i in range(n+1):
for j in range(m+1):
if F[i][j]:
if not F[i-1][j]:
nr += 1
if not F[i+1][j]:
nr += 1
if not F[i][j-1]:
nr += 1
if not F[i][j+1]:
nr += 1
print(nr)Sqarime
Në këtë zgjidhje ne ndërtojmë një matricë si një listë me N+2
lista, ku secila listë ka M+2 vlera. Elementët e kësaj matrice
fillimisht janë False për të treguar një parcelë të pambjellë, dhe
pastaj i bëjmë True për parcelat e mbjella.
Përmasat e matricës i kemi zgjedhur pak më të mëdhaja se madhësia e fushës për dy arsye. E para na ndihmon që ti kapim parcelat direkt, pa qenë nevoja të konvertojmë nga indekset me bazë 1 (që na jep problemi) në indekset me bazë 0 (siç i ka Python-i). Arsyeja e dytë është se na lehtëson edhe kontrollin për parcelat që janë në kufi të arës.
Për të gjetur numrin e gardheve, i marrim me radhë parcelat, dhe për çdo parcelë të mbjellë shikojmë parcelat fqinje me të (majtas, djathtas, lartë, poshtë). Për secilën nga këto parcela që është e pambjellë duhet të ndërtojmë një gardh.
Koha e kësaj zgjidhje është e rendit \(O(N*M)\), dhe po kështu edhe hapësira është e rendit \(O(N*M)\). Për të dhëna me përmasa të mëdha kjo zgjidhje nuk është dhe aq efiçente.
Zgjidhja 2
for _ in range(int(input())):
n, m, k = map(int, input().split())
F = []
while k > 0:
r, c = map(int, input().split())
F.append((r, c))
k -= 1
nr = 0
for x in F:
r, c = x
if (r+1, c) not in F:
nr += 1
if (r-1, c) not in F:
nr += 1
if (r, c+1) not in F:
nr += 1
if (r, c-1) not in F:
nr += 1
print(nr)Sqarime
Në këtë zgjidhje, në vend që të ndërtojmë një matricë, e mbajmë informacionin për parcelat e mbjella në një listë. Për parcelat fqinje shikojmë nëse ndodhen në këtë listë ose jo. Nëse nuk ndodhen atere janë të pambjella.
Koha e kësaj zgjidhje është e rendit \(O(K*K)\) dhe hapësira e rendit \(O(K)\). Nëse matrica është e rrallë (nuk ka shumë parcela të mbjella, K është shumë e vogël në krahasim me **N*M**), kjo zgjidhje mund të jetë më efiçente se zgjidhja e parë. Por në përgjithësi edhe kjo zgjidhje nuk është mjaft e shpejtë.
Zgjidhja 3
for _ in range(int(input())):
n, m, k = map(int, input().split())
F = {}
while k > 0:
r, c = map(int, input().split())
F[(r, c)] = True
k -= 1
nr = 0
for x in F:
r, c = x
if not F.get((r+1, c), False):
nr += 1
if not F.get((r-1, c), False):
nr += 1
if not F.get((r, c+1), False):
nr += 1
if not F.get((r, c-1), False):
nr += 1
print(nr)Sqarime
Në këtë zgjidhje listën e kemi zëvendësuar me një fjalor (dictionary). Kjo strukturë është shumë më e shpejtë se lista kur kërkon nëse një element ndodhet në të ose jo (listës i duhet një kohë e rendit \(O(K)\) për këtë veprim, kurse fjalori e bën në kohë konstante). Si rezultat, koha e kësaj zgjidhje është e rendit \(O(K)\) dhe hapësira e rendit \(O(K)\). Pra në përgjithësi është më e mirë se zgjidhja e dytë (kur K është shumë më e vogël se **N*M**).
Detyra
Fituesit të një olimpiade programimi i takon të marrë si shpërblim një çek me vlerën N. Mirëpo të paktën një nga shifrat e numrit N është 4, ndërkohë që tastiera e makinës që shkruan çekun e ka të prishur tastin me numrin 4. Megjithatë organizatorët e gjetën zgjidhjen duke shkruar dy çeqe, shuma e të cilëve është N, dhe asnjëri prej të cilëve nuk e përmban shifrën 4. Gjeni dy numra të tillë.
Referenca: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231
Shembull
$ cat input.txt
3
4
940
4444
$ python3 prog.py < input.txt
Case #1: 2 2
Case #2: 852 88
Case #3: 667 3777