The Rascal Triangle
#描述#
<p class="MsoNormal">
<b><span lang="en-us" style="font-family:"">The <i>Rascal Triangle</i> definition is similar to that of the Pascal
Triangle. The rows are numbered from the top starting with 0. Each row </span lang="en-us" style="font-family:""></b><span lang="en-us" style="font-family:"">n<b> contains </b>n + 1<b> numbers
indexed from </b>0<b> to </b>n<b>. Using </b>R(n, m)<b> to indicate the index </b>m<b> item in the index </b>n<b> row:<o:p>/o:p</b> </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal" style="text-indent:21.0pt;">
<span lang="en-us" style="font-family:"">R(n, m) = 0<b> for </b>n < 0<b> OR </b>m <
0<b> OR </b>m > n<b><o:p>/o:p</b> </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal">
<b><span lang="en-us" style="font-family:"">The first and last numbers in
each row (which are the same in the top row) are 1:<o:p>/o:p</span lang="en-us" style="font-family:""></b>
</p>
<p class="MsoNormal" style="text-indent:21.0pt;">
<span lang="en-us" style="font-family:"">R(n, 0) = R(n, n) = 1<o:p>/o:p </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal">
<b><span lang="en-us" style="font-family:"">The interior values are
determined by (</span lang="en-us" style="font-family:""></b><i><span lang="en-us" style="font-family:"">UpLeftEntry </span lang="en-us" style="font-family:""></i><span lang="en-us" style="font-family:"">* <i>UpRightEntry<b> </b></i><b>+ 1) / </b><i>UpEntry</i><b><o:p>/o:p</b> </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal">
<b><span lang="en-us" style="font-family:"">(See the parallelogram in the
array below):<o:p>/o:p</span lang="en-us" style="font-family:""></b>
</p>
<p class="MsoNormal">
<span lang="en-us" style="font-family:""><o:p> /o:p </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal">
<span lang="en-us" style="font-family:"">R(n
+ 1, m + 1) = (R(n, m) * R(n, m + 1) + 1) / R(n – 1, m)<o:p>/o:p </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal" align="center" style="text-align:center;">
<span lang="en-us" style="font-family:""><span style="font-family:'Courier New';line-height:1;">1</span></span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal" align="center" style="text-align:center;">
<span lang="en-us" style="font-family:""><span style="font-family:'Courier New';line-height:1;">1 </span><span> </span><span style="font-family:'Courier New';line-height:1;">1</span></span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal" align="center" style="text-align:center;">
<span lang="en-us" style="font-family:""><span style="font-family:'Courier New';line-height:1;">1</span><span style="line-height:1;"><span style="text-align:center;white-space:normal;font-family:'Courier New';line-height:1;"> </span><span style="text-align:center;white-space:normal;"> </span></span><span style="font-family:'Courier New';line-height:1;">2<span style="text-align:center;white-space:normal;font-family:'Courier New';line-height:1;"> </span><span style="text-align:center;white-space:normal;"> </span></span><span></span><span style="font-family:'Courier New';line-height:1;">1</span></span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal" align="center" style="text-align:center;">
<span style="font-family:'Courier New';line-height:1;">/<span style="text-align:center;white-space:normal;"> </span></span><span style="font-family:'Courier New';line-height:1;"></span>
</p>
<p class="MsoNormal" align="center" style="text-align:center;">
<span style="font-family:'Courier New';line-height:1;">1</span><span style="line-height:1;"><span style="text-align:center;white-space:normal;font-family:'Courier New';line-height:1;"> </span><span style="text-align:center;white-space:normal;line-height:1;"> </span></span><span style="font-family:'Courier New';line-height:1;">3<span style="text-align:center;white-space:normal;font-family:'Courier New';line-height:1;"> </span><span style="text-align:center;white-space:normal;"> </span></span><span style="font-family:'Courier New';line-height:1;">3<span style="text-align:center;white-space:normal;font-family:'Courier New';line-height:1;"> </span><span style="text-align:center;white-space:normal;"> </span></span><span style="font-family:'Courier New';line-height:1;">1</span>
</p>
<p class="MsoNormal" align="center" style="text-align:center;">
<span lang="en-us" style="font-family:""><span style="font-family:'Courier New';line-height:1;"></span><span> </span><span style="font-family:'Courier New';line-height:1;">/</span><o:p>/o:p </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal" align="center" style="text-align:center;">
<span lang="en-us" style="font-family:""><span style="font-family:'Courier New';line-height:1;">1</span><span style="line-height:1;"> </span><span style="font-family:'Courier New';line-height:1;">4 </span><span> </span><span style="font-family:'Courier New';line-height:1;">5 </span><span> </span><span style="font-family:Courier New;"><span style="line-height:1;">4 </span><span style="line-height:1;"></span></span><span> </span><span style="font-family:'Courier New';line-height:1;">1</span><o:p>/o:p </span lang="en-us" style="font-family:"">
</p>
<p class="MsoNormal">
<b><span lang="en-us" style="font-family:"">Write a program which computes </span lang="en-us" style="font-family:""></b><span lang="en-us" style="font-family:"">R(n, m)<b> the </b>m<sup>th</sup><b> element of the </b>n<sup>th</sup><b> row of the <i>Rascal Triangle</i>.<o:p>/o:p</b> </span lang="en-us" style="font-family:"">
</p>
#格式#
##输入格式##
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line of input consisting of 3 space separated decimal integers. The first integer is data set number, N. The second integer is row number n, and the third integer is the index m within the row of the entry for which you are to find R(n, m) the Rascal Triangle entry (0 ≤ m ≤ n ≤ 50000).
##输出格式##
For each data set there is one line of output. It contains the data set number, N, followed by a single space which is then followed by the Rascal Triangle entry R(n, m) accurate to the nearest integer value.
#样例1#
##样例输入1##
5
1 4 0
2 4 2
3 45678 12345
4 12345 9876
5 34567 11398
##样例输出1##
1 1
2 5
3 411495886
4 24383845
5 264080263
#限制#
1000ms
32768KB
#提示#
#来源#
