島嶼渡假↘下殺$4900起工程師靠存股年領百萬股息法人:14檔今年本業虧定了不捨學生找「槌」 高中...
2012-06-09 12:27:31 人氣(146) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][Math] 941 - Permutations

0
收藏
0
推薦

A permutation of a string is the set of all possible ways to combine its characters. E.g., the permutation of "abc" is {"abc", "acb", "bac", "bca", "cab", "cba"}. The size of this set is the factorial of the initial string size.

Given a string S (with up to 20 characters, all lowercase letters) and a integer N (0²N<20!) find the (N+1)th smallest element of the permutation of S (consider the lexicographic order; the permutation of 'abc' above, for example, is represented in lexicographic order form left to right).

E.g., if S = "abc" and N=0, then the result would be "abc"

E.g., if S = "abc" and N=5, then the result would be "cba"

E.g., if S = "abc" and N=3, then the result would be "bca"

E.g., if S = "cba" and N=3, then the result would be "bca"

Notice that the string may not be initially sorted (check the last two examples).

Input

The input file contains one line with the number of samples and then each sample consists of two lines: one with string S and the next with number N.

Output

For each sample, a line with the required value.

Sample Input

2
abc
3
abcde
119

Sample Output

bca
edcba

一次過真喜悅啊

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main() {
int t, i, j, k;
long long f[21] = {1, 1}, p;
char str[30];
for(i = 2; i <= 20; i++)
f[i] = f[i-1]*i;
scanf("%d", &t);
while(t--) {
scanf("%s", str);
int n = strlen(str);
sort(str, str+n);
scanf("%lld", &p);
p++;
int used[21] = {};
for(i = 0; i < n; i++) {
for(j = 0; j <= n; j++) {
if(f[n-i-1]*j >= p)
break;
}
j--;
p -= f[n-i-1]*j;
for(k = 0; k < n; k++) {
if(used[k] == 0) {
if(j == 0) {
printf("%c", str[k]);
used[k] = 1;
break;
}
j--;
}
}
}
puts("");
}
return 0;
}
 

941Permutations
台長:Morris
人氣(146) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][幾何] 184 - Laser Lines
此分類上一篇:[UVA] 567 - Risk

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文