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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema permutari3:

#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]--;

    }



//    fout<<poz;

    poz;

    fin>>Q;

    for (;Q;Q--) {

        fin>>x;

        x += poz;

        // construim a x-a permutare

        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;

            // caut al j-lea element marcat in v

            nr = 0;

            for (k=1;k<=n;k++) {

                nr += v[k];

                if (nr == j)

                    break;

            }

            fout<<k<<" ";

            v[k] = 0;

        }

        fout<<"
";

    }

    return 0;

}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #143 permutari3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #143 permutari3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #143 permutari3