Problemi 014
Kërkesa
Në një varg me numra natyrorë a1,a2,...,an gjeni diferencën më të vogël të mundshme midis 2 prej tyre. Dmth gjeni vlerën minimale të |ai−aj| për çdo 1≤i<j≤n .
Referenca: https://www.codechef.com/problems/HORSES
Shembull
$ cat input.txt
1
5
4 9 1 32 13
$ python3 prog.py < input.txt
3
Zgjidhja 1
T = int(input())
for t in range(T):
n = int(input())
l = list(map(int, input().split()))
dmin = abs(l[0] - l[1])
i = 0
while i <= n-2:
j = i + 1
while j <= n-1:
d = abs(l[i] - l[j])
if d < dmin:
dmin = d
j += 1
i += 1
print(dmin)
Sqarime
Marrim të gjitha kombinimet e mundshme të i
dhe j
, gjejmë
diferencat midis tyre, dhe ndërkohë gjejmë edhe më të voglën e
diferencave.
P.sh. për numrin a1 bëjmë diferencën me a2,a3,...,an, për numrin a2 bëjmë diferencën me a3,...,an, e kështu me radhë.
Kjo zgjidhje nuk është dhe aq efiçente sepse për n numra duhet të bëjmë përafërsisht n2 veprime (zbritje, krahasime, etj.)
Zgjidhja më poshtë është më e shpejtë.
Zgjidhja 2
T = int(input())
for t in range(T):
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
dmin = l[0] - l[1]
i = 0
while i <= n-2:
d = l[i] - l[i+1]
if d < dmin:
dmin = d
i += 1
print(dmin)
Sqarime
Fillimisht i rendisim numrat në rendin zbritës. Pastaj, në vend që të bëjmë diferencën e numrit ai me të gjithë numrat pasardhës, mjafton që të bëjmë diferencën e tij vetëm me numrin ai+1, dhe dihet që diferenca me numrat e tjerë pasardhës nuk është më e vogël se kjo (sepse janë më të vegjël se ai+1).
Detyra
Kemi një varg me numra ku të gjithë numrat përsëriten një numër çift herësh, me përjashtim të njërit i cili përsëritet një numër tek herësh. Të gjendet ky numër.
Referenca: https://www.codechef.com/problems/MISSP
Shembull
$ cat input.txt
2
3
1
2
1
5
1
1
2
2
3
$ python3 prog.py < input.txt
2
3
Janë 2 raste testimi, i pari ka 3 numra (njëri nën tjetrin), dhe i dyti ka 5 numra.