Problemi 030

Kërkesa

Një përkëmbim i numrave nga 1 deri në n është një renditje e këtyre numrave, kështu që mënyra më e natyrshme për të paraqitur një përkëmbim është që të rreshtosh numrat sipas kësaj radhe. P.sh. një përkëmbim i numrave nga 1 deri në 5 mund të jetë kështu: 2 3 4 5 1.

Por është edhe një mënyrë tjetër për të paraqitur një përkëmbim, duke krijuar një listë me numra, ku numri në pozicionin i tregon pozicionin e numrit i në përkëmbim. Le ta quajmë këtë përkëmbim i anasjelltë. Përkëmbimi i anasjelltë për vargun e mësipërm është: 5 1 2 3 4.

Një përkëmbim i dykuptimtë është ai i cili nuk mund të dallohet prej përkëmbimit të tij të anasjelltë. P.sh. përkëmbimi 1 4 3 2 është i dykuptimtë sepse është i njëjtë me përkëmbimin e tij të anasjelltë.

Bëni një program i cili gjen nëse një përkëmbim i dhënë është i dykuptimtë ose jo.

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

Shembull

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

$ python3 prog.py < input.txt
ambiguous
not ambiguous
ambiguous

Zgjidhja 1

for _ in range(int(input())):
    P = list(map(int, input().split()))
    for i in range(len(P)):
        if P[P[i]-1] != i+1:
            print('not ambiguous')
            break
    else:
        print('ambiguous')

Sqarime

Meqenëse përkëmbimet janë nga 1 deri në n, kurse treguesit (indekset) e listës janë nga 0 në n-1, duhet të kemi kujdes që ti zbresim dhe ti shtojmë 1 treguesit sipas nevojës.

Zgjidhja 2

for _ in range(int(input())):
    P = list(map(int, input().split()))
    P = [0] + P
    for i in range(len(P)):
        if P[P[i]] != i:
            print('not ambiguous')
            break
    else:
        print('ambiguous')

Sqarime

Nqs një përkëmbimi të dykuptimtë i shtojmë një 0 përpara dhe e fillojmë treguesin nga 0, ai mbetet përsëri një përkëmbim i dykuptimtë. E njëjta gjë ndodh edhe me një përkëmbim jo të dykuptimtë. Kështu që përkëmbimit të dhënë i shtojmë një zero përpara, dhe treguesit të listës nuk është nevoja ti shtojmë ose ti zbresim 1.

Detyra

Në një listë me këngë, secila prej këngëve e ka gjatësinë një numër të plotë minutash, dhe secila këngë e ka gjatësinë të ndryshme nga të tjerat. Kënga juaj e preferuar ndodhet në pozicionin K. Më pas ju i rendisni këngët sipas gjatësisë së tyre. Në cilin pozicion ndodhet tani kënga juaj e preferuar?

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

Shembull

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

$ python3 prog.py < input.txt
3
4
1

1. Në rastin e parë kemi: N = 4, L = [1, 3, 4, 2], K = 2. Kënga e preferuar është 3. Pas renditjes kemi L = [1, 2, 3, 4], kështu që përgjigja është 3.

2. Në rastin e dytë: N = 5, L = [1, 2, 3, 9, 4], K = 5. Kënga e preferuar është 4. Pas renditjes do jetë në pozicionin 4.

3. Në rastin e tretë: N = 5, L = [1, 2, 3, 9, 4], K = 1. Kënga e preferuar është 1. Pas renditjes do jetë prapë në pozicionin 1.