GDUFE ACM-1020

The Rascal Triangle

Time Limit: 1000ms

Problem Description:

  The Rascal Triangle definition is similar to that of the Pascal Triangle. The rows are numbered from the top starting with 0. Each row n contains n+1 numbers indexed from 0 to n. Using R(n,m) to indicte the index m item in the index n row:
  
R(n,m) = 0 for n < 0 OR m < 0 OR m > n

The first and last numbers in each row(which are the same in the top row) are 1:
  
R(n,0) = R(n,n) = 1

The interior values are determined by (UpLeftEntry*UpRightEntry+1)/UpEntry(see the parallelogram in the array below):
  
R(n+1, m+1) = (R(n,m) * R(n,m+1) + 1)/R(n-1,m)

Write a program which computes R(n,m) the

 element of the

 row of the Rascal Triangle.

Input:

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 <= 50,000).

Output:

For each data set there is onr line of output. It contains the data set number, N, followed by a single space which is then followed by thr Rascal Triangle entry R(n,m) accurate to the integer value.

Sample Input:

5
1 4 0
2 4 2
3 45678 12345
4 12345 9876
5 34567 11398

Sample Output:

1 1
2 5
3 411495886
4 24383845
5 264080263

Source:

2011 Greater New York Regional 



这道题就是找规律：
写成这样就可以发现规律了

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     long long  n,m,k,b,j,c,i,t,a[50005];
 7     scanf("%lld",&t);
 8     while(t--)
 9     {
10         scanf("%lld%lld%lld",&k,&n,&m);
11         if(m==0||m==n)
12             printf("%lld 1
",k);
13         else
14         {
15             b=n-3;
16             a[0]=1;
17             a[1]=n;
18             for(i=2;b>0;i++)
19             {
20                 a[i]=a[i-1]+b;
21                 b=b-2;
22             }
23             if(n%2==1)
24             {
25                 if(m<=n/2)
26                     printf("%lld %lld
",k,a[m]);
27                 else
28                 {
29                     j=(n+1)/2;
30                     c=(m+1)%j;
31                     m=j-c;//后半部分,比如n=7时,a[4]=a[3],a[5]=a[2],a[6]=a[1];
32                     printf("%lld %lld
",k,a[m]);
33                 }
34             }
35             else
36             {
37                 if(m<=n/2)
38                     printf("%lld %lld
",k,a[m]);
39                 else
40                 {
41                     j=n/2;
42                     c=m%j;
43                     m=j-c;//类似上面
44                     printf("%lld %lld
",k,a[m]);
45                 }
46             }
47         }
48     }
49     return 0;
50 }

另附上高人的代码（我没有想到这个思路）：

 1 #include <stdio.h>
 2 //规律：（n-m）*m+1
 3 int main(){
 4     int t,N,n,m;
 5     scanf("%d",&t);
 6     while(t--){
 7         scanf("%d %d %d",&N,&n,&m);
 8         printf("%d %d
",N,1+(n-m)*m);
 9     }
10     return 0;
11 }