# PBinfo #143 – permutari3 – Rezolvare C++

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

## Enunț

Se dă o permutare P a mulțimii {1,2, … ,N}. Se mai dau Q întrebări specificate prin câte un număr D. 

Cerință
Dacă D este pozitiv trebuie să determinăm a D-a permutare care succede lexicografic P iar dacă D este negativ, a D-a permutare care precede lexicografic P.

Date de intrare
Fișierul permutari3.in are pe prima linie un număr natural N. Pe linia a 2-a sunt N numere distincte din mulțimea {1,2, ... ,N}, separate prin câte un spațiu, reprezentând permutarea dată, P. Pe linia a 3-a este numărul Q. Pe următoarele Q linii se găsește câte un număr D cu semnificația de mai sus.

Date de ieșire
Fișierul permutari3.out conține Q linii. Pe fiecare linie este un șir de N numere, distincte, din mulțimea {1,2, ... ,N}, reprezentând răspunsul la o întrebare, în ordinea în care acestea apar în fișierul de intrare.

Restricții

3 ≤ N ≤ 15
1 ≤ Q ≤ 10000
valorile D indică o permutare validă;
șirul a1, a2, ..., an precede lexicografic șirul b1, b2, ..., bn dacă există o poziție k așa încât ak < bk și ai = bi pentru orice i de la 1 la k-1;
pentru 30% dintre teste, N<=6;
pentru 20% dintre teste, se garantează că toate valorile D sunt pozitive.

Exemplu
permutari3.in

4
2 1 4 3
2
1
-2
permutari3.out

2 3 1 4 
1 4 3 2
Explicaţie

Permutarea 2 3 1 4 urmează lexicografic imediat după permutarea 2 1 4 3.

Înaintea permutării 2 1 4 3 se află permutarea 2 1 3 4 şi apoi permutarea 1 4 3 2.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
long long F[30], poz, x, sum;
long long P[30];
long long i, n, j, k, Q, nr;
long long v[30];
int main() {
    F[1] = F[0] = 1;
    for (i = 2; i <= 19; i++)
        F[i] = i * F[i - 1];
    ifstream fin("permutari3.in");
    ofstream fout("permutari3.out");
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> P[i];
    for (i = 1; i < n; i++) {
        poz = poz + (P[i] - 1) * F[n - i];
        for (j = i + 1; j <= n; j++)
            if (P[j] > P[i])
                P[j]--;
    }
    fin >> Q;
    for (; Q; Q--) {
        fin >> x;
        x += poz;
        // Construct the x-th permutation
        for (i = 1; i <= n; i++)
            v[i] = 1;
        for (i = 1; i <= n; i++) {
            sum = 0;
            j = 0;
            while (sum <= x) {
                sum += F[n - i];
                j++;
            }
            sum -= F[n - i];
            x -= sum;
            // Find the j-th marked element in v
            nr = 0;
            for (k = 1; k <= n; k++) {
                nr += v[k];
                if (nr == j)
                    break;
            }
            fout << k << " ";
            v[k] = 0;
        }
        fout << "\n";
    }
    return 0;
}
```

## Resurse

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