Numere 7

Fie un număr natural X format din maximum 20 cifre, toate nenule. Adrian doreşte să construiască pe rând, in ordine crescătoare a valorii lor, toate numerele distincte care se pot forma prin schimbarea poziţiei cifrelor numărului X. Pentru că n este numărul său norocos, el doreşte să afle al n-lea număr care se obţine în acest fel.

Scrieţi un program care determină al n-lea număr, cu numerotare de la 1, care se poate forma din cifrele lui X.

Date de intrare

Fişierul de intrare numere7.in conţine pe prima linie cele două numere naturale n şi X separate printr-un singur spaţiu.

Date de ieşire

Fişierul de ieşire numere7.out va conţine pe prima linie numărul natural Y, care reprezintă al n-lea număr care se poate forma cu toate cifrele numărului X. Dacă al n-lea număr generat în ordine crescătoare nu există, se va afişa -1.

Restricţii

  • Pentru 20% din teste n ≤ 200, iar X are cel mult 9 cifre
  • Pentru celelalte teste 200 ≤ n ≤ 3*1011

SOLUTIE

#include <fstream>
#include <cstring>

using namespace std;

ifstream cin("numere7.in");
ofstream cout("numere7.out");

long long n, v[22], k, i, j, c, f[11], cnt;
int cif;
char a[22];

int main()
{
    cin >> n;
    cin >> a;
    k = strlen(a);
    for (i = 0; i < k; i++)
    {
        cif = a[i] - '0';
        f[cif]++;
    }
    v[0] = v[1] = 1;
    for (i = 2; i <= 20; i++)
        v[i] = v[i-1] * i;
    cnt = v[k];
    for (c = 0; c <= 9; c++)
        cnt = cnt / v[f[c]];
    if (n > cnt)
    {
        cout << -1;
    }
    else
    {
        for (i = 1; i <= k; i++)
        {
            for (j = 0; j <= 9; j++)
            {
                if (f[j])
                {
                    f[j]--;
                    cnt = v[k-i];
                    for (c = 0; c <= 9; c++)
                        cnt = cnt / v[f[c]];
                    if (n > cnt) {
                        n -= cnt;
                        f[j]++;
                    }
                    else {
                        cout << j;
                        j = 11;
                    }
                }
            }
        }
    }
    return 0;
}