2013
11-26

# Ignatius and the Princess II

Now our hero finds the door to the BEelzebub feng5166. He opens the door and finds feng5166 is about to kill our pretty Princess. But now the BEelzebub has to beat our hero first. feng5166 says, "I have three question for you, if you can work them out, I will release the Princess, or you will be my dinner, too." Ignatius says confidently, "OK, at last, I will save the Princess."

"Now I will show you the first problem." feng5166 says, "Given a sequence of number 1 to N, we define that 1,2,3…N-1,N is the smallest sequence among all the sequence which can be composed with number 1 to N(each number can be and should be use only once in this problem). So it’s easy to see the second smallest sequence is 1,2,3…N,N-1. Now I will give you two numbers, N and M. You should tell me the Mth smallest sequence which is composed with number 1 to N. It’s easy, isn’t is? Hahahahaha……"
Can you help Ignatius to solve this problem?

The input contains several test cases. Each test case consists of two numbers, N and M(1<=N<=1000, 1<=M<=10000). You may assume that there is always a sequence satisfied the BEelzebub’s demand. The input is terminated by the end of file.

For each test case, you only have to output the sequence satisfied the BEelzebub’s demand. When output a sequence, you should print a space between two numbers, but do not output any spaces after the last number.

6 4
11 8

1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10

pku1703，并查集的应用，比较常见的一种。

disscuss发现一种方法：用两个数组，一个存友f[]，一个存敌d[]。

else 输出 条件不足。代码就不贴了。。

1027 和2062是两道模拟题，以前都没有做，感觉太麻烦了。。

1027由于m最大只有10000  小于8的阶乘，所以只需要对n的后8位进行判断即可。。

2062 f[i]=i*(f[i-1]+1)，m可以用__int64 来存储，其余的都和1027差不多。。

# include<stdio.h>
# include<string.h>
int f[10],visit[1005];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,n,m,k,t,ans,flag;
f[0]=1;
for(i=1;i<=8;i++)
f[i]=f[i-1]*i;
while(scanf("%d%d",&n,&m)!=EOF)
{
flag=0;
memset(visit,0,sizeof(visit));
for(i=1;i<=n;i++)
{
ans=n-i+1;
if(ans>8)
{
visit[i]=1;
if(flag==0) {printf("%d",i);flag=1;}
else printf(" %d",i);
}
else
{
t=m/f[ans-1];
if(m%f[ans-1]!=0) t++;
k=0;
for(j=max(1,n-9);j<=n;j++)
{
if(visit[j]==0) k++;
if(k==t) break;
}
visit[j]=1;
if(flag==0) {printf("%d",j);flag=1;}
else printf(" %d",j);
m-=(t-1)*f[ans-1];
}
}
printf("\n");
}
return 0;
}

1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。