问题3010--逆序对

3010: 逆序对

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

假设我们将序列中第i件物品的参数定义为Ai,那么排序就是指将A1,…,An从小到大排序。若iAj,则就为一个“逆序对”。SORT公司是一个专门为用户提供排序服务的公司,他们的收费标准就是被要求排序物品的“逆序对”的个数,简称“逆序数”。   Grant是这家公司的排序员,他想知道对于n个参数都不同的物品组成的序列集合中,逆序对数为t的物品有多少个,并试给出其中一个最小的物品序列。所谓最小,即若有两个物品序列(A1,A2,…,An),(B1,B2,…,Bn),存在1≤I≤n,使得(A1,A2,…,Ai-1)=(B1,B2,…,Bi-1)且Ai<Bi。

输入

即两个整数n和t ( 1≤n≤20,0≤t≤n*(n-1)/2 )。

输出

第一行表示n个参数都不同的物品组成的序列集合中,逆序数为t的序列个数; 第二行是所求物品参数序列。假设n个物品分别为1到n。

样例输入

4 3

样例输出

6
1 4 3 2

来源/分类

 

[提交] [状态]