BAEKJOON 2676 - The Rascal Triangle

출처: https://www.acmicpc.net/problem/2676

문제

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 indicate 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 m-th element of the n-th row of the Rascal Triangle.

입력

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 spaces 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.

예제 입력 

5
4 0
4 2
45678 12345
12345 9876
34567 11398

예제 출력 

1
5
411495886
24383845
264080263

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2011 Greater New York Programming Contest B번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: newton08

링크

• ACM-ICPC Live Archive
• HDU Online Judge

파스칼의 삼각형과 같이 규칙에 따라 숫자를 직접 나열해보면 쉽게 규칙을 찾을 수 있는 문제입니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <string>
using namespace std;
 
 
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int n, m;
        cin >> n >> m;
        cout << (1 + (n - m) * m) << endl;
    }
    return 0;
}