Problemi 084

Kërkesa

Në një varg numrash natyrorë \(A_1, A_2, ..., A_n\) gjeni vlerën më të madhe të shprehjes \(A_i mod A_j\) (mbetja e pjesëtimit të \(A_i\) me \(A_j\)) për çdo vlerë të i dhe j.

Referenca: https://www.codechef.com/APRIL19B/problems/MAXREM

Shembull

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

$ python3 prog.py < input.txt
4
5

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    L = [int(i) for i in input().split()]
    m = 0
    for i in range(n):
        for j in range(n):
            if L[i] % L[j] > m:
                m = L[i] % L[j]
    print(m)

Sqarime

Zgjidhja naive, duke i gjetur të gjitha mbetjet e mundshme dhe duke marrë maksimumin e tyre, është me kohë të rendit \(O(N^2)\), dhe shumë e ngadalshme për vlera të mëdhaja të N.

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    m = 0
    for i in range(n-1, 0, -1):
        m = L[i-1] % L[i]
        if m > 0:
            break
    print(m)

Sqarime

Vëmë re që nëse \(a < b\), atere a % b = a. Kështu që për të gjetur mbetjen më të madhe mjafton që ti rendisim numrat dhe të marrin numrin e parafundit. Vetëm se kjo nuk funksionon nëse dy numrat e fundit qëllon të jenë të barabartë. Në këtë rast duhet marrë numri i parë që nuk është i barabartë me numrin e fundit. Gjithashtu duhet të kemi parasysh edhe rastin që të gjithë numrat mund të jenë të barabartë.

Koha mbizotëruese në këtë zgjidhje është koha që duhet për të renditur numrat, e cila zakonisht është e rendit \(O(N*log(N))\), pra më e mirë se zgjidhja e parë.

Zgjidhja 3

for _ in range(int(input())):
    n = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    i = n - 2
    while i > 0 and L[i] == L[i+1]:
        i -= 1
    print(L[i] % L[i+1])

Sqarime

E njëjtë si zgjidhja 2, vetëm se e shkruar pak më ndryshe.

Detyra

Regjistrimi në shkollën e lartë bëhet me anë të konkursit. Gjithsej zhvillohen E provime, ku pikët maksimale në çdo provim janë M, dhe merret shuma e pikëve të tyre. Nga N studentë që hyjnë në provime, vetëm K prej tyre që kanë marrë në total më shumë pikë se të tjerët mund të regjistrohen.

Ju i dini pikët që kanë marrë konkurrentët e tjerë në E-1 provimet e mëparshme. Gjithashtu, me një program të inteligjencës artificiale keni parashikuar edhe pikët që do marrin konkurrentët e tjerë në provimin e fundit. Gjeni se sa janë pikët minimale që duhet të merrni në provimin e fundit, në mënyrë që të hyni në shkollë të lartë. Nëse kjo është e pamundur programi duhet të nxjerrë ‘Impossible’.

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

Shembull

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

$ python3 prog.py < input.txt
4

Kemi 1 rast testimi. Rreshti i parë na jep numrat N=4, K=2, E=3, M=10. Katër rreshtat e tjerë na japin pikët që kanë marrë studentët e tjerë në E=3 provimet që janë zhvilluar, me përjashtim të rreshtit të fundit, i cili jep pikët tuaja në E-1 provimet e kaluara. Pikët totale të konkurentëve të tjerë janë 7+7+7=21, 4+6+10=20, dhe 7+10+9=26. Meqenëse vetëm K=2 veta do jenë fitues, juve ju duhen të paktën 22 pikë për të fituar. Deri tani keni marrë 9+9=18 pikë, kështu që në provimin e fundit duhet të merrni të paktën 4 pikë.