Fişierul intrare/ieşire:inter.in, inter.outSursăad-hoc
AutorDin FolclorAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.175 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 ca 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
  • M ≤ N2

Exemplu

inter.ininter.out
5 4
1 2
1 3
2 3
1 4
3 2 4 1 5

Algoritmul BubbleSort

bool sortat = 0;
while(!sortat) {
    sortat = 1;
    for(int i = 1; i <= n - 1; ++i)
        if(v[i] > v[i + 1]) {
           swap(v[i], v[i + 1]);
           sortat = 0;
        }
     }
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content