Se consideră vectorul ordonat strict crescător a = (a[1], a[2], ..., a[k]) ce memorează o submulțime de k elemente a mulțimii {1, 2, ..., n}. Trebuie determinată următoarea submulțime din punct de vedere lexicografic. De exemplu, dacă n=4 și k=3, atunci submulțimile de trei elemente, în ordine lexicografică, sunt: {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.

Cerința

Scrieți funcția având următorul antet:

void Succesor(int a[], int n, int k)

Vectorul a memorează, în ordine strict crescătoare, k numere naturale din mulțimea {1,2,...,n}. Funcția va trebui să obțină tot în vectorul a următoarea submulțime de k elemente din punct de vedere lexicografic.

Restricții și precizări

• 1 < k < n ≤ 30.000
• Elementele vectorului sunt indexate de la 1 la k.
• Se garantează că va exista succesorul submulțimii memorate inițial în vectorul a.

Exemplu

Dacă n=9, k=5 și a=(2,4,5,8,9), atunci apelul Succesor(a, n,k) va avea ca rezultat a=(2,4,6,7,8)

Important

Soluția propusă va conține definiția funcției cerute. Prezența în soluție a altor instrucțiuni poate duce erori de compilare sau de execuție care vor avea ca efect depunctarea soluției.

void Succesor(int a[], int n, int k)
{
    int f[30001]={0};
    for(int i = 1 ; i <= k ; ++i)
        f[a[i]] = 1;
    bool ok = true;
    int indice=0;
    for(int i = k ; i >= 1 && ok ; --i)
    {
        for(int j = a[i] ; j <= n && ok ; ++j)
        {
            if(f[j]!=1)
            {
                a[i]=j;
                indice = i;
                ok=false;
            }
        }
    }
    for(int i = indice + 1 ; i <= k ; ++i)
        f[a[i]]=0;
    for(int i = indice + 1 ; i <= k ; ++i)
    {
        bool ok = true;
        for(int j = a[i-1] + 1 ; j <= n && ok ; ++j)
        {
            if(f[j]==0)
            {
                a[i]=j;
                ok=false;
            }
        }
    }
}