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;
}