0401 - Pachete Multe - Revision history

Aurelia Raluca: Pagină nouă: = Cerinţa = Într-un depozit foarte mare 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
2024-03-22T23:54:12Z

Pagină nouă: = Cerinţa = Într-un depozit foarte mare există un raft cu <code>n+1</code> spații de depozitare, numerotate de la <code>1</code> la <code>n+1</code>. Primele <code>n</code> spatii de depozitare sunt ocupate cu <code>n</code> pachete numerotate cu valori între <code>1</code> și <code>n</code>, iar spațiul de depozitare <code>n+1</code> este gol. Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice <code>i</code>, pachetul numerotat cu <cod...

New page
= Cerinţa =
Într-un depozit foarte mare există un raft cu <code>n+1</code> spații de depozitare, numerotate de la <code>1</code> la <code>n+1</code>. Primele <code>n</code> spatii de depozitare sunt ocupate cu <code>n</code> pachete numerotate cu valori între <code>1</code> și <code>n</code>, iar spațiul de depozitare <code>n+1</code> este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice <code>i</code>, pachetul numerotat cu <code>i</code> să se afle în spațiul de depozitare <code>i</code>. Pentru aceasta se va folosi spațiul de depozitare suplimentar, <code>n+1</code>, 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 <code>pachete_multeIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale separate prin spaţii. Al <code>i</code>-lea număr reprezintă numărul pachetului aflat în spațiul de depozitare <code>i</code>.

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

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100000</code> <— ATENȚIE AICI
* pentru fiecare manevră <code>i j</code> efectuată, <code>1 ≤ i,j ≤ n+1</code>, <code>i ≠ j</code>, iar spațiul <code>j</code> trebuie să fie gol
* numărul de manevre realizate nu trebuie să fie minim

= Exemplul 1: =
<code>pachete_multeIN.txt</code>
5
2 5 4 3 1
<code>pachete_multeOUt.txt</code>
7
1 6
5 1
2 5
6 2
3 6
4 3
6 4

= Exemplul 2: =
<code>pachete_multeIN.txt</code>
100001
2 5 4 3 1
<code>pachete_multeOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restricțiile(n, sol):
if n < 1 or n > 100000:
return False

for i in range(1, n + 1):
if sol[0][i] < 1 or sol[0][i] > n + 1 or sol[1][i] < 1 or sol[1][i] > n + 1 or sol[0][i] == sol[1][i]:
return False

return True

def main():
INTRARE = "pachete_multeIN.txt"
IESIRE = "pachete_multeOUT.txt"

NMAX = 1000 * 100 + 1

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

with open(INTRARE, 'r') as intrare, open(IESIRE, 'w') as iesire:
n = int(intrare.readline())
data = list(map(int, intrare.readline().split()))

if len(data) != n:
iesire.write("Datele nu corespund restrictiilor impuse\n")
return

for i in range(1, n + 1):
v[i] = data[i - 1]
p[data[i - 1]] = i

p[0] = n + 1
nr = 0
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

if not verifica_restricțiile(n, sol):
iesire.write("Datele nu corespund restrictiilor impuse\n")
return

iesire.write(str(nr) + '\n')
for i in range(1, nr + 1):
iesire.write(str(sol[0][i]) + ' ' + str(sol[1][i]) + '\n')

if name == "main":
main()

</syntaxhighlight>