POJ 1715 Hexadecimal Numbers

Hexadecimal Numbers

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 1489	Accepted: 347

Description

The base of the hexadecimal system is 16. In order to write down numbers in this system one uses 16 digits 0,1,...,9,A,B,C,D,E,F. The capital letters A,..,F stands for 10,..,15, respectively. For instance the value of the hexadecimal number CF2 is 12 * 16 ^ 2 + 15 * 16 + 2 = 3314 in the decimal system. Let X be the set of all positive integers whose hexadecimal representations have at most 8 digits and do not contain repetitions of any digit. The most significant digit in such a representation is not zero. The largest element in X is the number with the hexadecimal representation FEDCBA98, the second largest is the number FEDCBA97, the third is FEDCBA96 and so forth. 

Write a program that: finds the n-th largest element of X;

Input

The first line of the file standard input contains integer n in the decimal representation. n does not exceed the number of elements of X.

Output

Your program should output the n-th largest element in X in the hexadecimal representation.

Sample Input

11
      

Sample Output

FEDCBA87
      

Source

CEOI 1997

 /*

挺難的一道數學題，一開始用搜尋未果,資料空間太大了,後來想到這種題肯定有數

學解法,接着寫了純數學題解法,WA了兩次才A,主要做法如下:

從高位往地位考慮,對于目前位p,從大到小考慮目前位的取值v,如果v在之前被使用

過則跳過v繼續考慮v-1;否則考慮目前位取v時後面的位能取到的數的總個數countv,

如果countv >= num,則表明目前位取v可以涵蓋num,然後跳出;否則num -= countv.

*/

#include <iostream>

#include <cstring>

#define MAX_N 350000

using namespace std;

char base[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

char res[16];

int num;

//計算排列數A(x, y)

int getAxy(int x, int y)

{

if(y == 0) return 1;

int res = 1;

while(y--)

{

res *= x;

x--;

}

return res;

}

void getRes()

{

int curPos;

bool v[MAX_N + 1];

memset(v, 0, sizeof(v));

int useFulLen = 0;

bool foundHead = false;

//從高位往地位考慮

for(curPos = 1; curPos <= 8; curPos++)

{

int curNum = 15;

int countv;

//一次周遊目前位所有可能的取值

while(curNum >= 1)

{

if(!v[curNum])

{

//countv是目前位取curNum時,可以涵蓋的數的個數

if((countv = getAxy(16 - 1 - useFulLen, 8 - curPos)) < num)

num -= countv; //不可以涵蓋,則num減去這個值

else //可以涵蓋

{

v[curNum] = true;

break;

}

}

curNum--;

}

res[curPos] = base[curNum];

//要注意統計目前有效位的長度

if(foundHead || res[curPos] != '0') useFulLen++;

if(res[curPos] != '0') foundHead = true;

}

}

int main()

{

while(scanf("%d", &num) != EOF)

{

getRes();

bool findHead = false;

for(int i = 1; i <= 8; i++)

{

if(findHead || res[i] != '0')

printf("%c", res[i]);

if(!findHead && res[i] != '0')

findHead = true;

}

if(!findHead) printf("0");

printf("/n");

}

return 0;

}