POJ 2085 Inversion

Inversion
Time Limit: 1000MS
 
Memory Limit: 30000K
Total Submissions: 2631
 
Accepted: 1143
Description
The inversion number of an integer sequence a1, a2, . . . , an is the number of pairs (ai, aj) that satisfy i < j and ai > aj . Given n and the inversion number m, your task is to find the smallest permutation of the set { 1, 2, . . . , n }, whose inversion number is exactly m. 
A permutation a1, a2, . . . , an is smaller than b1, b2, . . . , bn if and only if there exists an integer k such that aj = bj for 1 <= j < k but ak < bk.
Input
The input consists of several test cases. Each line of the input contains two integers n and m. Both of the integers at the last line of the input is −1, which should not be processed. You may assume that 1 <= n <= 50000 and 0 <= m <= n(n − 1)/2.
Output
For each test case, print a line containing the smallest permutation as described above, separates the numbers by single spaces.
Sample Input

5 9
7 3
-1 -1

Sample Output

4 5 3 2 1
1 2 3 4 7 6 5

Source
Shanghai 2004 Preliminary
 
 
/*오랫동안 규칙을 찾았는데 여러 번 기절했다. 고치고 또 썼고 또 고쳤다. 마침내 찾아냈다. 이 문제는 주로 다음과 같은 고려를 바탕으로 한다. 임의의 서열 i, i+1,...j의 가장 큰 inversion number는 모든 역순의 상황, 즉 j, j-1,...i+1,i,값은 in(i,j)=(j-i+1)*(j-i)/2로 기재되어 있기 때문에 이 문제의 해결 절차는 다음과 같다. (1) n,seq를 입력하고 뒤에서 seq값을 포괄할 수 있는 i, 즉 in(i,n)>=seq(2)는 (1)에서 알 수 있듯이 i->n은 seq값을 나타내는 insersion number로 충분하기 때문에 1->i-1은 오름차순으로 인쇄하면 된다. (3) 나머지 i->n은 어떻게 seq의 역수를 나타냅니까?몇 가지 예를 고찰하면 발견하기 어렵지 않다.나머지 i->n의 형식은 반드시 k, v1, v2,...,vn-1, 그중 k는 i->n 중의 임의의 수이며, {v1, v2, v3,..., vn-1}은 k를 제외한 나머지 수의 완전한 역순 형식이다.예를 들어 i=5, n=10, {7, 10, 9, 8, 6, 5}를 넣는 것이 바로 이런 형식이다.그럼 남은 임무는 이 k를 찾아내면 돼요.상기 분석을 통해 우리는 방정식을 열거하기 어렵지 않다. k-i+(n-i)*(n-i-1)/2=seq, 그 중에서 k-i는 큰 부분의 k가 이 수열의 역순에 대한 공헌도를 나타내고, (n-i)*(n-i-1)/2는 나머지 k를 제외한 i->n의 완전 역순 수열의 공헌도를 나타낸다. 이렇게 k를 풀면 된다. */#include using namespace std; int main() { int n, seq, i, j; while(scanf("%d%d", &n, &seq) && (n + seq) != -2) { int total = 0; for(i = n; i >= 1; i--) { total += n - i; if(total >= seq) break; } for(j = 1; j < i; j++) printf("%d ", j); int k = seq + i - (n - i) * (n - i - 1)/2; printf("%d ", k); for(j = n; j >= i; j--) if(j != k) printf("%d ", j); printf("/n"); } return 0; }