﻿ Fuzhou University OnlineJudge ﻿
Problem 1609 In a queue

Problem Description

In the barrack, the soldiers are training hard. As we all known, they must queue in line and it is the basic skills. As the total number of soldiers in a queue is N, each soldier is not as high as any other one. So ordering from low to high or from high to low, it will look very neat. One day, company commander thinks a problem. If these N soldiers are numbered 1,2,3,4… N, and the high of the No. i soldier is h (i).We define the number of soldiers who stand to the left of soldier i, but they are higher than soldier No. i as a formulation D (N, i).That is shown as follow:
D (N, i) is the number of solider whose number is smaller than i , but is higher than No. i. So in the queue of N soldiers, the sums of the soldiers who stand to the left of each soldier but higher than him is M. That is shown as follows:
For example, if there are three soldiers and they are No. 1, 2, 3, their height is h (1), h (2), h (3) respectively, and we define h (1) < h (2) < h (3), So when the queue is 213,then D (3,1) = 1,there are only one solider to the left of No.1 soldier and higher than him; D (3,2) = 0, there are not any solider to the left of No. 2 soldier and higher than him; D (3,3) = 0, there are not any solider to the left of No. 3 soldier and higher than him. So in this queue, the value of M is 1. In permutation of the three soldiers’s queue there is another permutation that the value of M is 1, and that is 132.

Input

The first line is a number C (C <= 2000), C is the number of tests. The following C lines, each line has two integer N (1<=N <=20) and X (0 <= X <= (N-1)*N/2), N is the number of soldiers and X is the value of M that is said above.

Output

For each test, output a number P, which is the number of permutation of a queue and its value of M is X.

3 3 1 3 2 3 3

2 2 1

Source

FOJ月赛-2008年5月

Submit  Back  Status  Discuss
﻿