The Rascal Triangle
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 64Accepted Submission(s): 61
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.
5
1 4 0
2 4 2
3 45678 12345
4 12345 9876
5 34567 11398
输出
5
1 4 0
2 4 2
3 45678 12345
4 12345 9876
5 34567 11398
题意
R(n+1, m+1) = (R(n,m) * R(n,m+1) + 1)/R(n-1,m)
R(n,0) = R(n,n) = 1
数塔从第0层开始 每层也是从0 开始
根据上面的2个式子推出来所有的
问输入 a b 输出第a行第b个数字
0 1
1 1 1
212 1
3 1 3 3 1
4 14 54 1
5 1 5 77 5 1
61 6 9 10 96 1
可以看出第i行第j个满足 (i-j)*j+1;
规律找了好久 最终还是看人家的 看着我的队友10几分钟就看出来了 我真的感到好丢人啊
哎 只有努力了 抓紧时间搞下规律题
#include<stdio.h>
int main()
{
int a,i,j,T,k;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&a,&i,&j);
if(i==j||j==0)
printf("%d %d\n",a,1);
else
{
k= (i-j)*j+1;
printf("%d %d\n", a, k);
}
}
return 0;
}
分享到:
相关推荐
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
离线OJ题库(HDU ZJU等,部分有答案),需联网。
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
HDU的一题........HDU DP动态规
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU 动态规划(46道题目
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
这是HDU acm 其中一部分题的代码,后续代码会继续上传。
100道 acm C语言 hdu 解题报告
hdu 1005.比较简单的一道题,有兴趣的可以看看。
我写的hdu上的一些题AC的题的代码 也许你会有用
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码