0400 - Pachete

Cerinţa

Într-un depozit există un raft cu n+1 spații de depozitare, numerotate de la 1 la n+1. Primele n spatii de depozitare sunt ocupate cu n pachete numerotate cu valori între 1 și n, iar spațiul de depozitare n+1 este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice i, pachetul numerotat cu i să se afle în spațiul de depozitare i. Pentru aceasta se va folosi spațiul de depozitare suplimentar, n+1, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

Date de intrare

Fişierul de intrare pacheteIN.txt conţine pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spaţii. Al i-lea număr reprezintă numărul pachetului aflat în spațiul de depozitare i.

Date de ieşire

Fişierul de ieşire pacheteOUT.txt va conţine pe prima linie numărul M, reprezentând numărul de manevre efectuate. Pe fiecare dintre următoarele M linii se descrie o manevră, prin două numere i j, cu semnificația: se ia pachetul din spațiul i și se mută în spațiul j.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricţii şi precizări

• 1 ≤ n ≤ 100
• pentru fiecare manevră i j efectuată, 1 ≤ i,j ≤ n+1, i ≠ j, iar spațiul j trebuie să fie gol
• numărul de manevre realizate nu trebuie să fie minim

Exemplul 1:

pacheteIN.txt

5
2 5 4 3 1 

pacheteOUT.txt

7
1 6
5 1
2 5
6 2
3 6
4 3
6 4

Explicație

Pachetele se vor muta în felul urmator.

2	5	4	3	1	_
_	5	4	3	1	2
1	5	4	3	_	2
1	_	4	3	5	2
1	2	4	3	5	_
1	2	_	3	5	4
1	2	3	_	5	4
1	2	3	4	5	_

Exemplul 2:

pacheteIN.txt

101
2 5 4 3 1 

pacheteOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

INFILE = "pacheteIN.txt"
OUTFILE = "pacheteOUT.txt"

NMAX = 1000 * 100 + 1

v = [0] * NMAX
p = [0] * NMAX
sol = [[0] * (NMAX * 2) for _ in range(2)]

def check_constraints(n):
    if 1 <= n <= 100:
        return True
    else:
        with open(OUTFILE, "w") as outfile:
            outfile.write("Datele nu corespund restrictiilor impuse\n")
        return False

def main():
    global v, p, sol
    
    with open(INFILE, "r") as infile:
        n = int(infile.readline())
        
        if not check_constraints(n):
            return

        v[1:n+1] = map(int, infile.readline().split())
        p = [0] * (n+1)
        
        p[0] = n + 1
        nr = 0
        
        for i in range(1, n+1):
            p[v[i]] = i
        
        for i in range(1, n+1):
            if v[i] == i:
                continue
            
            if p[0] != i:
                nr += 1
                sol[0][nr] = i
                sol[1][nr] = p[0]
                v[p[0]] = v[i]
                p[v[i]] = p[0]
                v[i] = 0
                p[0] = i
            
            nr += 1
            sol[0][nr] = p[i]
            sol[1][nr] = i
            v[i] = i
            v[p[i]] = 0
            p[0] = p[i]
            p[i] = i
        
        with open(OUTFILE, "w") as outfile:
            outfile.write(f"{nr}\n")
            for i in range(1, nr+1):
                outfile.write(f"{sol[0][i]} {sol[1][i]}\n")

if __name__ == "__main__":
    main()