Problemi 071

Kërkesa

Në një rrugë të drejtë dhe të ngushtë po lëvizin disa makina, të cilat kanë shpejtësi maksimale të ndryshme. Nqs rrugën përpara do ta kishin bosh, makinat do preferonin që të ecnin me shpejtësinë e tyre maksimale. Por nqs kanë përpara një makinë më të ngadaltë, makinat janë të detyruara ta ulin shpejtësinë, meqenëse nuk mund të parakalojnë, dhe të ecin njëra-pas-tjetrës vargan.

Bëni një program që merr shpejtësitë e makinave dhe gjen se sa prej tyre po ecin me shpejtësi maksimale. Mund të supozojmë se rruga është shumë e gjatë dhe makinat kanë qenë duke ecur në të për një kohë të gjatë.

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

Shembull

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

$ python3 prog.py < input.txt
1
2
2

Makinat po lëvizin nga e djathta në të majtë.

Në rastin e dytë, makina me shpejtësi 6 ndodhet pas asaj me shpejtësi 3, kështu që nuk mund të ecë me shpejtësi maksimale.

Në rastin e tretë, makina me shpejtësi 5 ndodhet pas asaj me shpejtësi 4, kështu që nuk mund të ecë me shpejtësi maksimale. Po ashtu, makinat 2 dhe 3 ndodhen pas asaj me shpejtësi 1, kështu janë futur në vargan. Me shpejtësinë e tyre maksimale ecin vetëm makinat 4 dhe 1.

Zgjidhja

for _ in range(int(input())):
    n = int(input())
    M = [int(m) for m in input().split()]
    nr = 1
    for i in range(1, n):
        if M[i] > M[i-1]:
            M[i] = M[i-1]
        else:
            nr += 1
    print(nr)

Sqarime

Makina e parë gjithmonë ecën me shpejtësinë e vetë maksimale, sepse nuk ka makina të tjera përpara që ta pengojnë.

Nqs një makinë e ka shpejtësinë shpejtësinë maksimale më të madhe se shpejtësia me të cilën po ecën makina përpara saj, atere është e detyruar ta ulë shpejtësinë dhe të ecë me të njëjtën shpejtësi si makina para saj.

Përndryshe (kur e ka shpejtësinë maksimale më të vogël ose të barabartë me shpejtësinë e makinës përpara saj), mund të ecë me shpejtësinë e vetë maksimale.

Detyra

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ë.