Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | inter.in, inter.out | Sursă | ad-hoc |
| Autor | Din Folclor | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Inter
Fie P o permutare a primelor N numere naturale. Dacă se va aplica algoritmul Bubble Sort, se vor
interschimba elementele vecine ( P[i] şi P[i+1], dacă P[i] > P[i+1], pentru orice i, 1 ≤ i ≤ N)
până când p devine permutarea identitate (1, 2, 3, ... N). Pornind de permutarea identitate, date
fiind interschimbările făcute de algoritm, să se construiască permutarea originală P.
Date de intrare
Fişierul de intrare inter.in conţine două numere n şi m (numărul de elemente ale permutării,
respectiv numărul de interschimbări). Pe următoarele m linii se află câte două numere x şi y cu
semnificaţia „$x$ se va interschimba cu y atunci când vor fi vecini.”
Date de ieşire
În fişierul de ieşire inter.out se vor afla n numere separate prin spaţiu reprezentând permutarea originală.
Restricţii
- 3 ≤ n ≤ 1000
Exemplu
| inter.in | inter.out |
|---|---|
| 5 4 1 2 1 3 2 3 1 4 | 3 2 4 5 1 |
Explicaţie
...
