# PBinfo #3358 – gama – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Se dă o permutare a mulțimii {1, 2, ..., n} adică un șir cu n numere distincte cuprinse între 1 și n. Se mai dă și o valoare k. Fiind permise maximum k interschimbări de elemente aflate pe poziții consecutive, se cere determinarea permutării minime din punct de vedere lexicografic.

Date de intrare
Fișierul gama.in conține pe prima linie numerele naturale n și k separate printr-un spațiu. Pe linia a doua se află elementele șirului dat, separate printr-un spațiu.

Date de ieșire
Fișierul gama.out conține pe primul rând n numere naturale, distincte de la 1 la n, separate prin câte un spațiu, reprezentând permutarea obținută.

Restricții și precizări

1 ≤ n ≤ 1000
1 ≤ k ≤ n•(n-1)/2
Rezultatul comparării lexicografice a două șiruri de numere este dat de rezultatul comparării elementelor aflate pe cea mai mică poziție unde nu sunt valori egale.

Exemplu:
gama.in

4 2
3 2 1 4
gama.out

1 3 2 4

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
int v[1010];
int n, minim, pMinim, i, j, k;
int main () {
    ifstream fin ("gama.in");
    ofstream fout("gama.out");
    fin>>n>>k;
    for (i=1;i<=n;i++)
        fin>>v[i];
    for (i=1;i<=n;i++) {
        minim = n+1;
        for (j=i;j<=n&&j-i<=k;j++)
            if (v[j] < minim) {
                minim = v[j];
                pMinim = j;
            }
        k-=(pMinim-i);
        for (j=pMinim-1;j>=i;j--)
            swap(v[j], v[j+1]);
    }
    for (i=1;i<=n;i++)
        fout<<v[i]<<" ";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3358)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3358/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3358/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)