Problemi 076

Kërkesa

Kemi një përkëmbim të numrave 1, 2, …, N. Quajmë të kundërt një çift numrash A[i] dhe A[j] në këtë përkëmbim nëse 1 <= i < j <= N dhe A[i] > A[j]. Quajmë të kundërt fqinj një çift numrash A[i] dhe A[i+1] të tillë që A[i] > A[i+1], ku 1 <= i < N. Një përkëmbim quhet i mirë nëse numri i të kundërtave në të është i njëjtë me numrin e të kundërtave fqinje.

Gjeni nëse një përkëmbim i dhënë është i mirë ose jo.

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

Shembull

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

$ python3 prog.py < input.txt
YES
YES
NO
YES

Kemi vetëm 1 element, nuk ka çifte numrash të kundërta ose të kundërta fqinje, kështu që përkëmbimi është i mirë.
Kemi vetëm një çift të kundërt dhe 1 të kundërt fqinj. Përkëmbimi është i mirë.
Kemi 3 çifte të kundërta: (3,2), (3,1), (2,1) dhe 2 të kundërta fqinje: (3,2), (2,1). Përkëmbimi nuk është i mirë.
Kemi vetëm një çift të kundërt: (3,2), dhe një të kundërt fqinj: (3,2). Përkëmbimi është i mirë.

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    A = [int(i) for i in input().split()]
    nr1 = nr2 = 0
    for i in range(n-1):
        if A[i] > A[i+1]:
            nr2 += 1
        for j in range(i+1, n):
            if A[i] > A[j]:
                nr1 += 1
    print('YES') if nr1 == nr2 else print('NO')

Sqarime

Numërojmë çiftet e kundërta dhe çiftet e kundërta fqinje dhe i krahasojmë.

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    A = [int(i) for i in input().split()]
    m = True    # supozojme se perkembimi eshte i mire
    i = 0
    while m and i < n - 2:
        j = i + 2
        while m and j < n:
            if A[i] > A[j]:
                m = False
            j += 1
        i += 1
    print('YES') if m else print('NO')

Sqarime

Mund të vihet re kollaj se çiftet e kundërta fqinje janë njëkohësisht çifte të kundërta. Kështu që nqs gjejmë një çift të kundërt që nuk është fqinj, mund të konkludojmë që përkëmbimi nuk është i mirë.

Detyra

Babai ka shkuar të bëjë pazarin bashkë me të birin 5-vjeçar. Deri tani kanë blerë N gjëra, të cilat peshojnë \(W_i\) secila. Djali ngul këmbë që ta ndihmojë babanë për ti mbajtur sendet e blera. Por që babai mos t’ia bëjë “me hile” dhe ti japë gjëra shumë të lehta, djali kërkon që sendet të ndahen në dy grupe, ku njëri prej tyre ka K elementë, dhe pastaj njërin prej grupeve ta mbajë djali dhe tjetrin babai. Babai sigurisht që do ti japë djalit grupin që peshon më pak. Por si mund ti ndajë sendet në dy grupe në mënyrë të tillë që diferenca në peshë midis tyre të jetë sa më e madhe?

Bëni një program që gjen diferencën në peshë më të madhe, nqs N sende i ndajmë në dy grupe, ku njëri nga grupet ka K sende.

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

Shembull

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

$ python3 prog.py < input.txt
17
2

Në rastin e parë kemi N=5 dhe K=2. Diferenca më e madhe do jetë nëse djalit i jep sendet me peshë 2 dhe 4. Diferenca në këtë rast do jetë (8+5+10)-(4+2)=17.

Në rastin e dytë sido që të bëhet ndarja, diferenca do jetë gjithmonë 2.